归并排序详细思路与插入排序的对比

太过爱你忘了你带给我的痛 2023-06-11 08:22 2阅读 0赞

# 一、基本概念 #

### 1.归并概念：将两个**有序数列**合并成一个有序数列，我们称之为**“归并”。** ###

### 2. 归并排序（Merge Sort）概念 ###

建立在归并操作上的一种排序算法，该算法是采用[分治法][Link 1]（Divide and Conquer）的一个非常典型的应用。

归并排序有多路归并排序、两路归并排序，可用与内排序，也可用于外排序。

### 3.算法思路及实现 ###

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array\[L..m\]，array\[m + 1..R\]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array\[L..R\]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array\[i\] 和 array\[j\] 的关键字，取关键字较小（或较大）的记录复制到 temp\[p\] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70][]

### 4.具体步骤： ###

*  **分解** -- 将当前区间一分为二，即求分裂点 mid = (L + R)/2;
 *  **求解** -- 递归地对两个子区间a\[L...mid\] 和 a\[mid+1...R\]进行归并排序。递归的终结条件是子区间长度为1。
 *  **合并** -- 将已排序的两个子区间a\[L...mid\]和 a\[mid+1...R\]归并为一个有序的区间a\[L...R\]。

# 二、（1）图解实现： #

**归并排序（Merge Sort）**

![20191030201714415.png][]

**当我们要排序数组的时候，使用归并排序法，将数组分成两半。如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 1][]

**然后把左边的数组和右边的数组排序，最后一起归并。当我们对左边的数组和右边数组进行排序的时候，再分别将左边的数组和右边的数组分成一半，然后对每一个部分先排序，再归并。（也就是一次次递归进行分组排序，归并，再分组再排序再归并过程）如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 2][]

**对于上面的每一个部分呢，我们依然是先将他们分半，再归并，如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 3][]

**分到一定细度的时候，每一个部分就只有一个元素了，那么我们此时不用排序，对他们进行一次简单的归并就好了。如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 4][]

**直至最后归并完成。**

![20191030202137708.png][]

归并的细节：

两个已经排序好的数组，如何归并成一个数组？

我们可以开辟一个临时数组来辅助我们的归并。也就是说他比我们插入排序也好，选择排序也好多使用了存储的空间，也就是说他需要o（n）的额外空间来完成这个排序。只不过现在计算机中时间的效率要比空间的效率重要的多。

整体来讲我们要使用三个索引来在数组内进行追踪。

## 2. 排序稳定性 ##

所谓排序稳定性，是指如果在排序的序列中，存在两个相等的两个元素，排序前和排序后他们的相对位置不发生变化的话，我们就说这个排序算法是稳定的。

排序算法是**稳定**的算法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 5][]

**蓝色的箭头表示最终选择的位置，而红色的箭头表示两个数组当前要比较的元素，比如当前是2与1比较，1比2小，所以1放到蓝色的箭头中，蓝色的箭头后移，1的箭头后移。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 6][]

**然后2与4比较，2比4小那么2到蓝色的箭头中，蓝色箭头后移，2后移，继续比较.......**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 7][]

#  二、（2）代码实现： #

版本一：

#include<iostream>
    #include<algorithm>
    //#include "SortTestHelper.h"
    //#include "SelectionSort.h"
    #include<stdio.h>
    using namespace std;
    //归并排序
    template<typename T>//泛型
    //归并操作
    
    //将arr[l,mid]和[mid+1,r]两部分进行归并操作
    void __merge(T arr[],int l,int mid,int r){
    	T aux[r-l+1];//临时存放的数组，开辟的空间
    	for(int i=l;i<=r;i++)
    		aux[i-l] = aux[i]; //有一个l的偏移量，并且完成临时空间
    	//首先我设置两个索引已经排好序的两部分子数组
    	int i = l,j = mid+=1;
    	for(int k=l;k<=r;k++){
    		//判断数组索引越界问题，当i>mid后面还没有进行完操作、
    		if(i>mid){
    			arr[k] = aux[j-l];
    			j++;
    		}
    		else if(j>r){
    			arr[k] = aux[i-l];
    			i++;
    		}
    		else if(arr[i-l]<arr[j-l]){
    			aux[k] = aux[i-l];
    			i++;//索引到下一个位置
    		}else{
    			aux[k] = aux[j-l];
    			j++;//索引到下一个位置
    		}
    	}
    }
    
    
    template<typename T>//泛型
    //递归使用归并排序，对arr[l,r]的范围进行排序
    void __mergeSort(T arr[] ,int l,int r){
    	if(l>=r){//这是一个不可能的情况，等于时候，也就是说没有数据需要处理
    		return ;
    	}
    	//定义中间的数
    	int mid = (l+r)/2;
    	//开始对分开的左右两个部分分别进行归并排序
    	__mergeSort(arr,l,mid);//对左边进行归并排序
    
    	__mergeSort(arr,mid+1,r);//对右边就行归并排序
    	__merge(arr,l,mid,r);//将两段进行merge,归并或者是融合操作
    }
    
    
    template<typename T>//泛型
    
    void mergeSort(T arr[], int n){
    	__mergeSort(arr,0,n-1);
    }
    int main(){
    
    int a[105],n,i;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	scanf("%d",&a[i]);
        
        mergeSort(a,n);
        sort(a,a+n);
    	for(i=0;i<n;i++)
    	printf("%d ",a[i]);
    
    	return 0;
    }

结果：

![20191030215827755.png][]

测试对比插入排序与归并排序的时间的复杂度代码：

**main.cpp:**

#include <iostream>
    #include "SortTestHelper.h"
    #include "InsertionSort.h"
    
    using namespace std;
    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    template<typename  T>
    void __merge(T arr[], int l, int mid, int r){
    
        // 经测试,传递aux数组的性能效果并不好
        T aux[r-l+1];
        for( int i = l ; i <= r; i ++ )
            aux[i-l] = arr[i];
    
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){
    
            if( i > mid )   { arr[k] = aux[j-l]; j ++;}
            else if( j > r ){ arr[k] = aux[i-l]; i ++;}
            else if( aux[i-l] < aux[j-l] ){ arr[k] = aux[i-l]; i ++;}
            else                          { arr[k] = aux[j-l]; j ++;}
        }
    }
    
    // 递归使用归并排序,对arr[l...r]的范围进行排序
    template<typename T>
    void __mergeSort(T arr[], int l, int r){
    
        if( l >= r )
            return;
    
        int mid = (l+r)/2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid+1, r);
        __merge(arr, l, mid, r);
    }
    
    template<typename T>
    void mergeSort(T arr[], int n){
    
        __mergeSort( arr , 0 , n-1 );
    }
    
    
    int main() {
    
        int n = 50000;
    
        // 测试1 一般性测试
        cout<<"Test for Random Array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
        int* arr1 = SortTestHelper::generateRandomArray(n,0,n);
        int* arr2 = SortTestHelper::copyIntArray(arr1, n);
    
        SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
        SortTestHelper::testSort("Merge Sort",     mergeSort,     arr2, n);
    
        delete[] arr1;
        delete[] arr2;
    
        cout<<endl;
    
    
        // 测试2 测试近乎有序的数组
        int swapTimes = 100;
        cout<<"Test for Random Nearly Ordered Array, size = "<<n<<", swap time = "<<swapTimes<<endl;
        arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
        arr2 = SortTestHelper::copyIntArray(arr1, n);
    
        SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
        SortTestHelper::testSort("Merge Sort",     mergeSort,     arr2, n);
    
        delete(arr1);
        delete(arr2);
    
        return 0;
    }

**SortTestHelper.h:**

#ifndef INC_04_INSERTION_SORT_SORTTESTHELPER_H
    #define INC_04_INSERTION_SORT_SORTTESTHELPER_H
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <ctime>
    #include <cassert>
    
    using namespace std;
    
    
    namespace SortTestHelper {
    
        int *generateRandomArray(int n, int range_l, int range_r) {
    
            int *arr = new int[n];
    
            srand(time(NULL));
            for (int i = 0; i < n; i++)
                arr[i] = rand() % (range_r - range_l + 1) + range_l;
            return arr;
        }
    
        int *generateNearlyOrderedArray(int n, int swapTimes){
    
            int *arr = new int[n];
            for(int i = 0 ; i < n ; i ++ )
                arr[i] = i;
    
            srand(time(NULL));
            for( int i = 0 ; i < swapTimes ; i ++ ){
                int posx = rand()%n;
                int posy = rand()%n;
                swap( arr[posx] , arr[posy] );
            }
    
            return arr;
        }
    
        int *copyIntArray(int a[], int n){
    
            int *arr = new int[n];
            copy(a, a+n, arr);
            return arr;
        }
    
        template<typename T>
        void printArray(T arr[], int n) {
    
            for (int i = 0; i < n; i++)
                cout << arr[i] << " ";
            cout << endl;
    
            return;
        }
    
        template<typename T>
        bool isSorted(T arr[], int n) {
    
            for (int i = 0; i < n - 1; i++)
                if (arr[i] > arr[i + 1])
                    return false;
    
            return true;
        }
    
        template<typename T>
        void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
    
            clock_t startTime = clock();
            sort(arr, n);
            clock_t endTime = clock();
            cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
    
            assert(isSorted(arr, n));
    
            return;
        }
    
    };
    #endif //INC_04_INSERTION_SORT_SORTTESTHELPER_H

**InsertionSort.h:**

** 测试结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 8][]

# 三、时间复杂度及稳定性 #

## 1. 时间复杂度 ##

长度为n的序列需要进行logn次二路归并才能完成排序（归并排序的形式其实就是一棵二叉树，需要遍历的次数就是二叉树的深度），而每趟归并的时间复杂度为O(n)，因此**归并排序的时间复杂度为O(nlogn)**。

**算法复杂度：O（nlogn）**；

也许有很多同学说，原来也学过很多O（n^2）或者O（n^3）的排序算法，有的可能优化一下能到O（n）的时间复杂度，但是在计算机中都是很快的执行完了，没有看出来算法优化的步骤，那么我想说有可能是你当时使用的测试用例太小了，我们可以简单的做一下比较

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 9][]

**当数据量很大的时候 nlogn的优势将会比n^2越来越大，当n=10^5的时候，nlogn的算法要比n^2的算法快6000倍，那么6000倍是什么概念呢，就是如果我们要处理一个数据集，用nlogn的算法要处理一天的话，用n^2的算法将要处理6020天。这就基本相当于是15年。**

[Link 1]: http://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70]: /images/20230531/dd474dd7fc444c08826f2ae21d5b50a1.png
[20191030201714415.png]: /images/20230531/ed007c5ed7ba4c609cfa72ff63e740de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 1]: /images/20230531/4d3189b8e844424db86714f1b71952b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 2]: /images/20230531/e66a90956d714db981ffaa2a4dd528a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 3]: /images/20230531/03af77cb145244218c01c25d9d810732.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 4]: /images/20230531/3066d5e9262e41d1830b8da0802425a0.png
[20191030202137708.png]: /images/20230531/1dcf033cc3ef4f6fb52f695d2d83c0ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 5]: /images/20230531/f6e28db54b2244e6bc7e74446bd094c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 6]: /images/20230531/a68ffe1be46d40968bc8ca189c624bd8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 7]: /images/20230531/e3011dd0718d486eb61e3b5c697bf5d2.png
[20191030215827755.png]: /images/20230531/b4b65aa1d25b44ef948b4558b0d65ddd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 8]: /images/20230531/850ac5fffe3f49328557b0677b8f3d09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 9]: /images/20230531/1496a8b8ddde4aadae1e1a1b5cdbb430.png