归并排序

Bertha 。 2023-07-03 08:23 3阅读 0赞

**目录**

一、基本原理

二、代码实现

1、归并排序的基本实现

2、迭代版本的归并排序

3、空间复杂度为O(1)的归并排序

4、最好情况的时间复杂度为O(n)的归并排序（Tim排序）

--------------------

## 一、基本原理 ##

**归并排序的基本原理**为：将序列平分为两个子序列（如果序列为奇数2\*i+1个，则第一个子序列为i+1个，第二个子序列为i个），分别对子序列进行排序，再将已经有序的子序列合并，得到完全有序的序列。此算法有两个基本操作，一个是**递归地划分**序列直到子序列只有一个元素，此时各个子序列自然都是有序的（采用分治法，通过递归实现）；另一个是**合并操作**，将由同一个父序列划分出来的子序列重新合并（建立在归并操作的基础之上，并且由于合并操作不改变相同元素的先后次序，归并排序是稳定排序）。

**合并操作的具体流程**为：1） 申请辅助空间，其大小为两个已经排好序的子序列之和，该空间用来存放合并后的序列；2） 设定两个指针，分别初始化为两个子序列的起始位置；3） 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复此步骤直到某一子序列遍历完；4）如果有一个子序列还没遍历完，则将其剩余的元素都添加到辅助空间的末尾；5）将原数组两个子序列的父序列按辅助空间的顺序重新赋值。

归并排序的速度仅次于快速排序，用于总体无序，但各子项相对有序的序列比较有优势。归并排序比较占用内存，如果不用考虑内存问题，可以考虑使用。

## 二、代码实现 ##

### 1、归并排序的基本实现 ###

具体实现如下，这里我在合并操作中先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(*n*)。

public class Sort {
    
        //归并排序
        public static void mergeSort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
    
            //空间复杂度为O(nlogn)
            mergeSortRange1(arr, 0, arr.length-1);
            //
            //空间复杂度为O(n)
            //int[] tempArr = new int[arr.length];
            //mergeSortRange(arr, 0, arr.length-1, tempArr);
        }
    
        private static void mergeSortRange(int[] arr, int start, int end, int[] tempArr) {
            //出口：当区间只有一个元素时，说明子区间已经有序
            if (start == end) {
                return;
            }
    
            //子问题：继续划分，缩小数据规模
            int mid = (end - start) / 2 + start;
            mergeSortRange(arr, start, mid, tempArr);
            mergeSortRange(arr, mid+1, end, tempArr);
    
            //合并操作
            int i = start, j = mid + 1, k = start;
            while (i <= mid && j <= end) {
                tempArr[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= mid) {
                tempArr[k++] = arr[i++];
            }
            while (j <= end) {
                tempArr[k++] = arr[j++];
            }
            for (k=start; k<=end; k++) {
                arr[k] = tempArr[k];
            }
        }
    
        //对数组的[start, end]区间进行归并排序
        private static void mergeSortRange(int[] arr, int start, int end) {
            //出口：当区间只有一个元素时，说明子区间已经有序
            if (start == end) {
                return;
            }
    
            //子问题：继续划分，缩小数据规模
            //int len = end - start + 1;
            //int mid = (len % 2 == 1) ? start + len/2 : start + len/2 - 1;   //划分点，第一个子序列的右边界
            //
            int mid = (end - start) / 2 + start;
            mergeSortRange(arr, start, mid);
            mergeSortRange(arr, mid+1, end);
    
            //合并操作
            merge(arr, start, mid, end);
        }
    
        private static void merge(int[] arr, int start, int mid, int end) {
            //改进，将归并排序最好情况下的时间复杂度由O(nlogn)降为O(n)
            if (arr[mid] <= arr[mid + 1]) {
                return;
            }
    
            int[] tempArr = new int[end - start + 1];
            int i = start, j = mid + 1, k = 0;
            while (i <= mid && j <= end) {
                tempArr[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= mid) {
                tempArr[k++] = arr[i++];
            }
            while (j <= end) {
                tempArr[k++] = arr[j++];
            }
            for (k=0; k<tempArr.length; k++) {
                arr[start + k] = tempArr[k];
            }
        }
    
    }

递归函数也可以这么写：

public class Sort {
    
        //对数组的[start, end]区间进行归并排序，第二种写法
        private static void mergeSortRange1(int[] arr, int start, int end) {
            if (start < end) {
                //子问题：继续划分，缩小数据规模
                int mid = (end - start) / 2 + start;
                mergeSortRange(arr, start, mid);
                mergeSortRange(arr, mid+1, end);
    
                //合并操作
                merge(arr, start, mid, end);
            }
        }
    
    }

### 2、迭代版本的归并排序 ###

public class Sort {
    
        //归并排序的迭代版本
        public static void mergeSort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
    
            int step = 1;   //步长，当前要合并的子数组的长度大小， 1, 2, ..., floor(n-1 / 2)
            int n = arr.length;
            //while (step < n) {
            while (step <= n-1) {
                //将相邻的两个长度为step的子序列合并，i为一对子数组的左边界（第一个子数组的开端），i+step为第二个子数组的开端
                for (int i=0; i<arr.length; i=i+2*step) {
                    merge1(arr, i, i+step, step);
                }
    
                step *= 2;
            }
        }
    
        public static void merge(int[] arr, int leftStart, int rightStart, int step) {
            //特殊情况
            if (rightStart >= arr.length) { //第二组实际不存在，无需合并
                return;
            }
    
            //存在两个子序列，[leftStart, leftStart+step-1]  [rightStart, rightEnd]
            int leftEnd = leftStart + step - 1;
            int rightEnd = Math.min(rightStart+step-1, arr.length-1);
            //将它们合并
            int[] tempArr = new int[rightEnd - leftStart + 1];
            int i = leftStart, j = rightStart, k = 0;
            while (i <= leftEnd && j <= rightEnd) {
                tempArr[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= leftEnd) {
                tempArr[k++] = arr[i++];
            }
            while (j <= rightEnd) {
                tempArr[k++] = arr[j++];
            }
            for (k=0; k<tempArr.length; k++) {
                arr[k + leftStart] = tempArr[k];
            }
        }
    
    }

### 3、空间复杂度为O(1)的归并排序 ###

归并排序的基本实现的空间复杂度为O(nlogn)或O(n)，现在将其优化成O(1)。其时间复杂度为O(n^2\*logn)。

public class Sort {
    
        //空间复杂度为O(1)的归并排序
        public static void mergeSortInPlace(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
    
            mergeSortRangeInPlace(arr, 0, arr.length-1);
        }
    
        //对数组的[start, end]区间进行归并排序
        private static void mergeSortRangeInPlace(int[] arr, int start, int end) {
            if (start < end) {
                //子问题：继续划分，缩小数据规模\
                int mid = (end - start) / 2 + start;
                mergeSortRangeInPlace(arr, start, mid);
                mergeSortRangeInPlace(arr, mid+1, end);
    
                //合并操作
                mergeInPlace(arr, start, mid, end);
            }
        }
    
        //空间复杂度为O(1)的合并操作
        private static void mergeInPlace(int[] arr, int start, int mid, int end) {
            //int[] tempArr = new int[end - start + 1];
            // 已经有序
            if (arr[mid] <= arr[mid + 1]) {
                return;
            }
    
            int i = start, j = mid + 1, k = start;
            while (i <= mid && j <= end) {
                if (arr[i] <= arr[j]) {
                    //第一个子序列当前指针向后移动一位
                    i++;
                } else {
                    //腾出一个位置
                    int temp = arr[j];
                    for (int index=j; index>i; index--) {
                        arr[index] = arr[index-1];
                    }
                    mid++;
                    //将第二个子序列的元素放到第一个子序列中
                    arr[i++] = temp;
                    //第二个子序列当前指针向后移动一位
                    j++;
                }
            }
        }
        
    }

另一种写法，记录一个比所有元素都大的数字maxElement，从头到尾遍历两个子序列的范围，将每个位置重新赋值为初始值+实际值\*maxElement，最后再遍历一遍，将每个位置的元素 / maxElement重新赋值为实际值。

import java.util.Arrays;
    public class Sort {
    
        //空间复杂度为O(1)的归并排序
        public static void mergeSortInPlace1(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
    
            int maxElement = Arrays.stream(arr).max().getAsInt() + 1;
            System.out.println(maxElement);
            mergeSortRangeInPlace1(arr, 0, arr.length-1, maxElement);
        }
        //对数组的[start, end]区间进行归并排序
        private static void mergeSortRangeInPlace1(int[] arr, int start, int end, int maxElement) {
            if (start < end) {
                //子问题：继续划分，缩小数据规模\
                int mid = (end - start) / 2 + start;
                mergeSortRangeInPlace1(arr, start, mid, maxElement);
                mergeSortRangeInPlace1(arr, mid+1, end, maxElement);
    
                //合并操作
                mergeInPlace1(arr, start, mid, end, maxElement);
            }
        }
        //空间复杂度为O(1)的合并操作
        private static void mergeInPlace1(int[] arr, int start, int mid, int end, int maxElement) {
            //只有一个子序列
            if (end - start + 1 == 1) {
                return;
            }
            // 已经有序
            if (arr[mid] <= arr[mid + 1]) {
                return;
            }
    
            int i = start, j = mid + 1, k = start;
            while (i<=mid && j<=end) {
                if (arr[i] % maxElement <= arr[j] % maxElement) {
                    arr[k] = arr[k] + (arr[i] % maxElement) * maxElement;
                    k++;
                    i++;
                } else {
                    arr[k] = arr[k] + (arr[j] % maxElement) * maxElement;
                    k++;
                    j++;
                }
            }
            while (i <= mid) {
                arr[k] = arr[k] + (arr[i] % maxElement) * maxElement;
                k++;
                i++;
            }
            while (j <= end) {
                arr[k] = arr[k] + (arr[j] % maxElement) * maxElement;
                k++;
                j++;
            }
            for (k=start; k<=end; k++) {
                arr[k] = arr[k] / maxElement;
            }
        }
        
    }

### 4、最好情况的时间复杂度为O(n)的归并排序（Tim排序） ###

归并排序的基本实现最好情况、平均情况、最坏情况的时间复杂度均为O(nlogn)，而Tim排序则是将归并排序最好情况（数组本身有序）的时间复杂度优化成O(n)。

Tim排序是一种时间复杂度为O(nlogn)的稳定排序，Java的Arrays.sort()就使用了这种排序。Tim排序基于插入排序和归并排序，首先使用插入排序对各个小序列（块）排序，然后使用归并排序合并各个小序列（块）。具体来说，将数组分成各个块（run），使用插入排序一个个对这些run排序，然后使用归并排序中的合并操作将这些run合并。如果数组大小小于run，则数组只使用插入排序进行排序。

在下面的实现中，有3个细节：首先，将run的大小定义为32；其次，将大小小于等于run的片段一一排序；最后，不断合并各个片段，每次合并之后片段的大小变为原来的2倍（32, 64, 128, ...）。

Tim排序其实跟迭代版本的归并排序很像，只不过后者的子序列大小是从1开始，只采用合并操作，没有采用额外的排序算法。

public class Sort {
    
        //Tim排序
        private static int RUN = 32;
        public static void timSort(int[] arr) {
            if (arr == null || arr.length <= 1) {
                return;
            }
    
            //将大小为RUN的小序列排序
            int n = arr.length;
            for (int i=0; i<n; i += RUN) {
                timInsertion(arr, i, Math.min((i + 31), (n-1)));
            }
    
            //合并各个RUN，合并后的大小为128, 256, ...
            for (int size=RUN; size<n; size=2*size) {   //当size>=n，说明整个数组作为一个子序列，自然无需合并操作。也就是说，当数组的长度小于RUN，就只采用插入排序
                for (int left=0; left<n; left+=2*size) {
                    int mid = left + size - 1;
                    int right = Math.min(left+2*size-1, n-1);
                    //合并arr[left ... mid] 和 arr[mid+1 ... right]
                    timMerge(arr, left, mid, right);
                }
            }
        }
    
        //某个区间的插入排序
        private static void timInsertion(int[] arr, int left, int right) {
            for (int i=left; i<=right; i++) {
                int temp = arr[i];
    
                int j = i - 1;
                for (; j>=left && arr[j]>temp; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
        }
    
        //合并操作
        private static void timMerge(int[] arr, int start, int mid, int end) {
            //有序
            if (end - start + 1 == 1) {
                return;
            }
    
            int[] tempArr = new int[end - start + 1];
            int i = start, j = mid + 1, k = 0;
            while (i <= mid && j <= end) {
                tempArr[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= mid) {
                tempArr[k++] = arr[i++];
            }
            while (j <= end) {
                tempArr[k++] = arr[j++];
            }
            for (k=0; k<tempArr.length; k++) {
                arr[start + k] = tempArr[k];
            }
        }
        
    }

参考：

[https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin][https_baike.baidu.com_item_E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F_1639015_fr_aladdin]

[https://www.jianshu.com/p/33cffa1ce613][https_www.jianshu.com_p_33cffa1ce613]

[https://www.jianshu.com/p/892ebd063ad9][https_www.jianshu.com_p_892ebd063ad9]

[https_baike.baidu.com_item_E5_BD_92_E5_B9_B6_E6_8E_92_E5_BA_8F_1639015_fr_aladdin]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin
[https_www.jianshu.com_p_33cffa1ce613]: https://www.jianshu.com/p/33cffa1ce613
[https_www.jianshu.com_p_892ebd063ad9]: https://www.jianshu.com/p/892ebd063ad9