排序算法之归并排序

1.归并排序介绍

归并排序的核心思想是分治法，是建立在归并操作上的一种有效的排序算法。通过递归的对半拆分成最小单元（一个元素），然后通过回溯的比较合并，构成整个归并的排序。

分治法：将原问题分解为一些规模较小的相似子问题，然后递归解决这些子问题，最后合并其结果作为原问题的解。

算法步骤：

1.把数组递归拆分成N个最小数组单元
2.回溯地对每个组进行合并排序
3.把已有的排序好的组，两两合并，直到合并到组数为1。

原数组： 2 1 8 4 10 3 9 7 第一次递归分解： (2 1 8 4) （10 3 9 7）第二次递归分解： (2 1) (8 4) （10 3) (9 7）第三次递归分解： (2) (1) (8) (4) (10) (3) (9) (7）

从最后回溯归并：第一次归并：(1 2) (4 8) (3 10) (7 9) 第二次归并：(1 2 4 8) (3 7 9 10) 第三次归并：(1 2 3 4 7 8 9 10)

Ok, 经过递归分解和归并后，整个数组有序了。

2.归并排序算法从实现到优化

V1.0

template <typename T>
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] = arr[i];
    }

    int i = L, j = mid+1;
    for(int k = L; k <= R; k++) {
        if(i > mid) {			//L....-->mid, now i has bigger than (L...mid)every one
            arr[k] = aux[j-L];
            j++;
        }
        else if(j > R) {	//mid....-->R, now j has bigger than (mid...R)every one
            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++;
        }
    }

}

template <typename T>
void __mergeSort(T arr[], int L, int R)
{
    if(L >= R)
        return;

    int mid = (L+R)/2;	//递归的对半拆分
    __mergeSort(arr, L, mid-1);
    __mergeSort(arr, mid+1, R);
    __merge(arr, L, mid, R);	//回溯的比较与合并
}

template <typename T>
void mergeSort(T arr[], int n)
{
    __mergeSort(arr, 0, n-1);
}

此版本是第一版，可以看出来，有些地方是可以优化的，从前面的插入排序知道，在越有序，插入排序效率越高，一些场景下比nlogn时间复杂度的排序算法还高。因此，可以在最后基本有序的时候，使用插入算法来代替。

同时，对于arr[mid] <= arr[mid+1]，不进行merge操作的，直接返回就OK了，因为这种情况下，前面的那段肯定比后面的小(升序排序，降序逻辑相反)。

优化后的：

template <typename T>
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] = arr[i];
    }

    int i = L, j = mid+1;
    for(int k = L; k <= R; k++) {
        if(i > mid) {			//L....-->mid, now i has bigger than (L...mid)every one
            arr[k] = aux[j-L];
            j++;
        }
        else if(j > R) {	//mid....-->R, now j has bigger than (mid...R)every one
            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++;
        }
    }

}

template <typename T>
void __mergeSort(T arr[], int L, int R)
{
    /*if(L >= R)
        return;*/
    //优化2：近乎有序时使用 插入排序 加快排序速度
    if(R - L <= 15) {
        InsertSortFunc::InsertSort2(arr, L, R);
        return ;
    }

    int mid = (L+R)/2;
    __mergeSort(arr, L, mid-1);
    __mergeSort(arr, mid+1, R);
    //优化1：对arr[mid] <= arr[mid+1] 不进行merge
    if(arr[mid] <= arr[mid+1])
        __merge(arr, L, mid, R);
}

template <typename T>
void mergeSort(T arr[], int n)
{
    __mergeSort(arr, 0, n-1);
}

经过优化后，对于近乎有序的数组效率是非常高的，但是对于一般的情况下可能会有性能的消耗。因为上面多了一个函数调用，就有栈活动和函数切换返回的消耗。所以看情况使用。

3.归并排序算法分析

当数组长为N，将数列分开成最小单元需要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，所以共O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）效率比较高的。

4.归并排序多种场景下的测试

int N = 20000;
//稀疏数组，随机性大
int *arr1 = SortTestHelper::CreateRandomArray(N, 0, 1000000);
int *arr2 = SortTestHelper::copyIntArray(arr1, N);
int *arr3 = SortTestHelper::copyIntArray(arr1, N);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr1, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr2, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr3, N);
cout << endl;

//近乎有序
int *arr4 = SortTestHelper::CreateRandomArray(N, 0, 100);
int *arr5 = SortTestHelper::copyIntArray(arr4, N);
int *arr6 = SortTestHelper::copyIntArray(arr4, N);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr4, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr5, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr6, N);
cout << endl;

//基本有序
int *arr7 = SortTestHelper::CreateRandomArray(N, 0, 10);
int *arr8 = SortTestHelper::copyIntArray(arr7, N);
int *arr9 = SortTestHelper::copyIntArray(arr7, N);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr7, N);
SortTestHelper::testSort("InsertSort", InsertSortFunc::InsertSort, arr8, N);
SortTestHelper::testSort("mergeSort", mergeSortFunc::mergeSort, arr9, N);
cout << endl;

delete[] arr1;delete[] arr2;delete[] arr3;delete[] arr4;
delete[] arr5;delete[] arr6;delete[] arr7;delete[] arr8;delete[] arr9;

测试结果：

优化前：

——–随机数组，随机性大 SelectionSort : 0.412177s InsertSort : 0.251195s mergeSort : 0.002841s

——–近乎有序 SelectionSort : 0.41445s InsertSort : 0.256053s mergeSort : 0.002498s

——–基本有序 SelectionSort : 0.426011s InsertSort : 0.232978s mergeSort : 0.002227s

优化后：

——–随机数组，随机性大 SelectionSort : 0.416574s InsertSort : 0.255791s mergeSort : 0.001487s

——–近乎有序 SelectionSort : 0.410324s InsertSort : 0.249639s mergeSort : 0.001583s

——–基本有序 SelectionSort : 0.417486s InsertSort : 0.23147s mergeSort : 0.001419s

所以，优化后的归并排序总体上都比没优化的快，而且对越有序的数组，效率更高。但是插入排序不是一种原地性的排序算法，需要开额外的内存空间，这也算一个遗憾吧。

排序算法