zhengrenzhe's blog   About

归并排序

前几篇讲述的排序算法都基于遍历操作,而归并排序不同,它基于递归,是分治法的经典体现,也就是“分而治之”。将一个大问题分成两个或多个相同或相似小问题,直到最后子问题可以简单求解,原问题的解即子问题解的合并,同使用分治法的排序算法还有快速排序。

归并排序的核心思想是将序列分成两部分,先将左半部分排序,然后将右半部分排序,最后归并两部分。而排序这一部分就是调用自身的递归过程,直到该部分只剩2个元素,这样就可以进行简单的比较。

首先来看下归并操作,它接受两个已经排好序的子序列,返回两个子序列合并后的结果。

function merge<T>(
    items: T[], // 完整序列
    start: number, // 待归并的子序列a的起始下标
    mid: number, // 待归并的子序列a的终点下标
    end: number, // 待归并的子序列b的终点下标
    cmp: (a: T, b: T) => boolean, // 子序列的排序方式
) {
    // 创建一个临时数组,保存待归并的元素
    const tmp = items.slice(start, end + 1);

    // 子序列a在临时数组内的起始下标
    let aIndex = 0;
    // 子序列b在临时数组内的起始下标
    let bIndex = mid - start + 1;

    // 子序列a在临时数组内的终点下标
    mid = bIndex - 1;

    for (let i = start; i <= end; i++) {
        // 若子序列a已经结束,则直接把子序列b跟在后面。
        if (aIndex > mid) items[i] = tmp[bIndex++];
        // 若子序列b已经结束,则直接把子序列a跟在后面。
        else if (bIndex > end) items[i] = tmp[aIndex++];
        // 根据当前遍历到的子序列a和子序列b中的元素的大小关系来决定谁先进入原始序列items中
        else if (!cmp(tmp[aIndex], tmp[bIndex])) items[i] = tmp[aIndex++];
        else items[i] = tmp[bIndex++];
    }
}

以序列 [1, 3, 6, 2, 5, 7, 9] 为例,我们要对它进行归并操作。

const arr = [1, 3, 6, 2, 5, 7, 9];
merge(arr, 0, 2, 6, (a, b) => a > b);
console.log(arr); // [ 1, 2, 3, 5, 6, 7, 9 ]

接着我们要完成这归并排序的分治递归过程,可以先写个伪代码来思考下递归过程:

def sort(items, start, end, cmp):

    // 当某一子序列的长度为 3 时,将它分成两部分,必然有一部分只有一个元素,此时不排序直接返回
    if(end == start):
        return

    // end 比 start 大 1,说明序列中只剩两个,已经到底了,可以直接比大小
    if(end-start == 1):
        if(cmp(items[start], items[end])):
            swap(items, start, end)

    
    sort(items, start, (end-start)/2) // 排序左半边
    sort(items, (end-start) / 2 + 1, end) // 排序右半边

    merge(items, start, (end-start)/2, end) // 归并左右两部分排序后的结果

接着我们把它转化成实际代码:

import { swap } from "./tools";

export default function sort<T>(
    items: T[],
    cmp = (a: T, b: T) => a > b,
    start = 0,
    end = items.length - 1,
) {
    if (end - start === 0) return;

    if (end - start === 1 && cmp(items[start], items[end])) {
        swap(items, start, end);
        return;
    }

    const mid = Math.floor((end - start) / 2) + start;
    const left = [start, mid];
    const right = [mid + 1, end];

    sort(items, cmp, left[0], left[1]);
    sort(items, cmp, right[0], right[1]);

    // 如果左右两个子序列的交汇处不满足交换条件,说明整个序列已经是排好序的了,此时无须进行归并操作
    if (cmp(items[mid], items[mid + 1])) merge(items, start, mid, end, cmp);

    return items;
}

← 希尔排序  优先队列 →