归并排序与自然归并排序

红太狼 2024-02-05 13:52 80阅读 0赞

## 归并排序 ##

> 归并排序(merge - sort)是建立在归并操作上的一种有效的排序算法,该算法是采用**分治法**的一个非常典型的应用.将已有的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.**若将两个有序表合并成一个有序表,成为二路归并**.

### 核心步骤讲解 ###

归并排序的核心步骤如下:

![28c145b108e84b66b4518fbc29ea1eec.png][]

可以看出,这算法的核心逻辑就是类似小学语文学文章的一种结构的"总-分-总".

让我们来具体剖析一下,来看看它的思路:

拆分过程:以10 6 7 1这一组为例来看一下拆分过程(核心:使用start, end, mid分别表示开头结尾和中间) :

![25797fc342fb4afbab28233e3d32a7d3.png][]

合并过程:让我么以6,10/1,7这一组为例,来看一下合并过程:最主要的地方就在于传入两组要合并的组,然后创建一个新的数组tmpArr,存放要合并的两个组元素,并将tmpArr中的内容放在源数组中对应位置.

![5976cbbe0d3b499b97c4f996c00322bb.png][]

下面是代码:

public class MergeSort {
        public static void mergeSort(int[] arr) {
            mergeSortFun(arr, 0, arr.length - 1);
        }
    
        public static void mergeSortFun(int[] arr, int start, int end) {
            //当start和end重合之后,结束递归
            if(start >= end) {
                return;
            }
            //找到要切割的位置
            int mid = (start + end) / 2;
            //左分支
            mergeSortFun(arr, start, mid);
            //右分支
            mergeSortFun(arr, mid + 1, end);
            //合并内容
            merge(arr, start, mid, end);
        }
    
        public static void merge(int[] arr, int left, int mid, int right) {
            //为了好理解,这里重新用s1,s2,e1,e2表示
            int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;
            //定义一个新的数组,用来返回排序好的部分
            int[] tmpArr = new int[right - left + 1];
            //用k表示下标(在新创建的数组中的位置)
            int k = 0;
            while(s1 <= e1 && s2 <= e2) {
                if(arr[s1] <= arr[s2]) {
                    tmpArr[k++] = arr[s1++];
                } else {
                    tmpArr[k++] = arr[s2++];
                }
            }
    
            //用来存放剩余的部分
            while(s1 <= e1) {
                tmpArr[k++] = arr[s1++];
            }
    
            while(s2 <= e2) {
                tmpArr[k++] = arr[s2++];
            }
    
            //将排序好的数组,放到原来的数组中
            for(int i = 0; i < tmpArr.length; i++) {
                arr[i + left] = tmpArr[i];
            }
        }
    
        public static void main(String[] args) {
            int[] arr = {10, 6, 7, 1, 3, 9, 4, 2};
            mergeSort(arr);
            for(int x : arr) {
                System.out.print(x + " ");
            }
        }
    }

### 归并排序总结 ###

> 1.归并的缺点在于需要O(N)的空间复杂度,**归并排序的思考更多的是解决在磁盘中的外排序问题**.
> 
> 2.时间复杂度:O(N \* logN)
> 
> 3.空间复杂度:O(N)
> 
> 4.稳定度:稳定.

### 海量数据的排序问题 ###

外部排序:排序过程中需要在磁盘等外部存储进行的排序.

eg:内存只有1G,需要排序的数据有100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序.而归并排序是最常用的外部排序.

> 1.先把文件切分成200份,每个512M
> 
> 2.分别对512M内容进行排序,因为每个内存都放得下,所以任意排序都可以
> 
> 3.进行二路归并,同时对200份有序文件进行归并过程,最终结果就有序了.

## 自然归并排序 ##

> 自然归并排序是归并排序的一种变体,**其主要特点是利用输入数据的初始有序性**.**自然归并排序的思想是先找到已经有序的子序列,然后合并这些子序列,直至整个数组有序**.

### 核心步骤讲解 ###

> **1.查找有序子序列:**从数组的起始位置开始,**找到第一个有序子序列(递增或递减)**.这可以通过遍历数组来实现.
> 
> **2.合并有序子序列:**将找到的有序子序列进行合并,在合并的过程中,继续查找下一个有序子序列,直到整个数组有序.
> 
> **3.重复步骤1和2:**重复执行步骤1和2,直到整个数组完全有序.

以下是大致过程:

![55752950f1894a7ba3f0d528f02005b7.png][]

相对于之前的归并排序,这里就不是单纯的向下递归的过程,而是一个寻找子序列的过程,而在归并的过程中,是基本与之前的一致的.所以这里只需要分析一下寻找子序列的过程即可:

![35386040b309453db8be34e87aead35e.png][]

重点:**标记的end是上一组的下一个**,然后循环时不断标记end,控制为两两一组,进行合并.反复执行上述过程,就可以直接完成.

可能讲的会有点不清楚,请看代码:

import java.util.Arrays;
    
    public class NaturalMergeSort {
    
        public static void main(String[] args) {
            int[] array = {10, 6, 7, 1, 3, 9, 4, 2};
            naturalMergeSort(array);
            for(int x : array) {
                System.out.print(x + " ");
            }
        }
    
        public static void naturalMergeSort(int[] array) {
            int n = array.length;
            int[] tempArray = new int[n];
            int l = -1, m, r;
    
            //外部循环,直到不能发现更多的子数组
            while(l != 0) {
                l = 0;
                //内部循环,以寻找并合并有序子数组
                while (l < n) {
                    m = findNextSortedSubarray(array, l, n, tempArray);
                    //当m 与 n重合时,表明已经找到尾了,退出循环(里和外)
                    if (m == n) {
                        break;
                    }
                    r = findNextSortedSubarray(array, m, n, tempArray);
    
                    merge(array, l, m, r, tempArray);
                    l = r;
                }
            }
        }
        //查找下一个有序子数组的方法(返回的是结束位置)
        private static int findNextSortedSubarray(int[] array, int start, int n, int[] tempArray) {
            int end = start + 1;
            while (end < n && array[end - 1] <= array[end]) {
                end++;
            }
            return end;
        }
    
        //二路归并
        private static void merge(int[] array, int l, int m, int r, int[] tempArray) {
            int i = l, j = m, k = 0;
            while (i < m && j < r) {
                if (array[i] <= array[j]) {
                    tempArray[k++] = array[i++];
                } else {
                    tempArray[k++] = array[j++];
                }
            }
    
            while (i < m) {
                tempArray[k++] = array[i++];
            }
    
            while (j < r) {
                tempArray[k++] = array[j++];
            }
    
            System.arraycopy(tempArray, 0, array, l, k);
        }
    }

### 自然归并排序总结 ###

> 1.这玩意的思路相比于其它排序其实特别恶心,在生产环境中非常不建议使用,你的项目组成员可能会骂街,说你小子装什么逼??**(除非是这种情况:就比如你的数据结构老师不知道是为啥心血来潮让你讲这个,整一个反转课堂啥的,那你也没办法~~)**
> 
> 2.时间复杂度:遍历了一次:O(n)
> 
> 3.空间复杂度:O(n)

[28c145b108e84b66b4518fbc29ea1eec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/687a863c30b64b929ce59174da129ffb.png
[25797fc342fb4afbab28233e3d32a7d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/9a5ed8445b2042609fb10119c1f1d015.png
[5976cbbe0d3b499b97c4f996c00322bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3c3a6732553f471eb3bc2767afbc16f5.png
[55752950f1894a7ba3f0d528f02005b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e08cac0a132443c79633466e6e145a20.png
[35386040b309453db8be34e87aead35e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/bd0e81ea85f44f40a6b800702e20f7db.png