归并排序算法

归并排序（Merging Sort），是利用归并技术进行的排序。所谓归并，是指将两个或两个以上的有序表合并成一个新的有序表。在内部排序中，通常采用的是2-路归并排序

2-路归并排序的思想是：将一个具有 $n$ 个待排序的序列看成 $n$ 个长度为1有序序列，然后对相邻的子序列进行两两归并，得到 $\lceil n/2\rceil$ 个长度为2的有序子序列，继续对相邻子序列纪念性两两归并，得到 $\lceil n/4\rceil$ 个长度为4的有序序列，重复归并过程，直至得到一个长度为 $n$ 的有序序列为止

归并排序是一种稳定的排序算法

算法步骤

1. 需要一个与原始序列一样大小的空间，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动该指针到下一位置
4. 直到某一指针超出对应序列尾部，将另一序列剩下的所有元素直接复制到合并序列的尾部

测试用例： 使用归并排序算法将数组 { 36，80，66，45，22，9，16，36 } 进行升序排序

归并过程

代码实现

    /**
     * 用于归并两个有序子序列
     * @param nums 需要排列的数组
     * @param temp 用于临时存放的数组,与nums等大小
     * @param low 低位点(相邻序列的前指针)
     * @param mid 中位点(相邻序列的后指针)
     * @param high 高位点
     * @return 返回合并后的数组
     */
    public int[] merge(int[] nums, int[] temp, int low, int mid, int high) {
        int i = low, j = mid, k = 0;
        // 循环比较大小,归并两个有序序列
        while (i < mid && j <= high){
            if (nums[i] < nums[j]) temp[k++] = nums[i++];   // 将两个有序序列比较,选取其中最小的放入temp[]临时数组中
            else temp[k++] = nums[j++];
        }
        // 循环左序列剩余的元素,并添加到temp中
        while (i < mid) temp[k++] = nums[i++];
        // 循环右序列剩余的元素,并添加到temp中
        while (j <= high) temp[k++] = nums[j++];

        // 由于temp数组是从下标0开始赋值的,而在变动的数组是nums
        // 将临时存放好的元素替换nums数组对应的元素
        for (i = 0, k = low; k <= high;){
            nums[k++] = temp[i++];
        }
        return nums;
    }

    /**
     * 归并排序
     * 将所序列中的元素对半分组之后,直至子序列中只存在1个元素时,进行两两子序列的比较再合并
     * @param nums 需要排列的数组
     * @param temp 用于临时存放的数组,与nums等大小
     * @param low 低位点
     * @param high 高位点
     * @return 返回归并好的序列
     */
    public int[] mergeSort(int[] nums, int[] temp, int low, int high) {
        if (low == high) return nums;   // 当子序列中只存在一个元素时,直接返回
        int mid = low + (high - low) / 2;     // 递归对半分组
        nums = mergeSort(nums, temp, low, mid);     // low ~ mid 区域
        nums = mergeSort(nums, temp, mid+1, high);  // mid+1 ~ high 区域
        return merge(nums, temp, low, mid + 1, high);   // low ~ high 区域
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

时间复杂度：

2-路归并排序进行第1趟排序后，有序子序列长度为2；进行第 $i$ 趟排序后，有序子序列长度小于等于 $2^i$。因此，当排序元素数量为 $n$ 时，需进行 $\lceil logn\rceil$ 趟归并。每趟归并所需时间与元素个数成正比，每次归并的时间复杂度为 $O(n)$，故 2-路归并排序的时间复杂度为 $O(nlogn)$

由于2-路归并排序每次划分的两个子序列的长度基本一致，因此其最好、最差和平均复杂度都是 $O(nlogn)$

空间复杂度
在归并排序的过程中，借助了一个与初始序列相同大小的辅助数组，因此空间复杂度为 $O(n)$