一文读懂『归并排序』算法（Merge Sort）

一文读懂『归并排序』算法（Merge Sort）

引用

CSDN

1.

https://blog.csdn.net/lovedingd/article/details/136689315

归并排序算法（Merge Sort）是一种基于归并操作的高效、稳定的排序算法，它采用分治法（Divide and Conquer）的思想。归并排序的基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后将两个已排序的子数组合并成一个有序数组。

归并排序算法简介

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

与快速排序（Quick Sort）相比，快速排序是将序列划分成两个子序列，再递归使子序列有序；而归并排序是先使子序列有序，再进行合并。

算法基本思想和流程（时间复杂度O(nlogn)）

• Step1——确定分界点
  mid
  （三种常用的方法）：
  q[l]
  、
  q[(l+r)/2]
  、
  q[r]
  ，或者随机确定；
• Step2——将待排序列调整成
  left
  和
  right
  两个子序列，递归排序
  left
  和
  right
  ；
• Step3——归并（合二为一），Finish！

难点/关键点：步骤三的归并方法（双指针算法，O ( n ) O(n)O(n) ）

步骤二结束后会得到两个排好序的子序列 list1 和 list2 ，采用 双指针算法 将其合二为一：

• 定义两个指针：i 和 j，分别指向两个子序列的起始元素，另外定义一个新序列 temp 用来存储归并结果；
• 两指针指向的元素进行比较：
• 若 *i <= *j ，将该元素放入到 temp 中，并且 i++ ；
• 若 *i > *j ，将该元素放入到 temp 中，并且 j++ ；
• 不断循环进行上述比较操作，直到某一个指针指向了该子序列的末尾，则将另一个序列的剩余部分全部按顺序放入 temp 中即可，所得的 temp 序列为归并排序的结果。

举个例子如下，易于理解：

代码实现

Java代码：

/**
 * 归并排序
 *
 * @param array
 * @return
 */
public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
/**
 * 归并排序——将两段排序好的数组结合成一个排序数组
 *
 * @param left
 * @param right
 * @return
 */
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        if (i >= left.length)
            result[index] = right[j++];
        else if (j >= right.length)
            result[index] = left[i++];
        else if (left[i] > right[j])
            result[index] = right[j++];
        else
            result[index] = left[i++];
    }
    return result;
}

Python代码：

def merge_sort(array):
    if len(array) < 2:
        return array
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    
    return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
    result = [0] * (len(left) + len(right))
    i = j = index = 0
    while index < len(result):
        if i >= len(left):
            result[index] = right[j]
            j += 1
        elif j >= len(right):
            result[index] = left[i]
            i += 1
        elif left[i] > right[j]:
            result[index] = right[j]
            j += 1
        else:
            result[index] = left[i]
            i += 1
        index += 1
    return result

归并排序模板（背诵）

模板一：

void merge_sort(int q[], int l, int r)
{
    // 1.判边界
    if (l >= r) return;
    
    // 2.定分界点
    int mid = l + r >> 1;
    // 递归排序子序列
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    // 3.归并排序（双指针法）
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    // 某个子序列走到最后了，将另一个序列剩余部分加入到 tmp 中
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    
    // 将排序结果 tmp 重新覆盖掉 q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

模板二：

void merge_sort(int q[], int l, int r)
{
    // 1.判边界
    if (l >= r) return;
    
    // 2.定分界点
    int mid = l + r + 1 >> 1;
    // 递归排序子序列
    merge_sort(q, l, mid - 1), merge_sort(q, mid, r);
    // 3.归并排序（双指针法）
    int k = 0, i = l, j = mid;
    while (i <= mid - 1 && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    // 某个子序列走到最后了，将另一个序列剩余部分加入到 tmp 中
    while (i <= mid - 1) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
    
    // 将排序结果 tmp 重新覆盖掉 q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

【分析避免边界问题】

• 当递归取的 merge_sort(q, l, mid), merge_sort(q, mid + 1, r);，则为了避免陷入死循环，取中间值需要下取整 x = q[l + r >> 1]
• 当递归取的 merge_sort(q, l, mid - 1), merge_sort(q, mid, r);，则为了避免陷入死循环，取中间值需要上取整 x = q[l + r + 1 >> 1]