自底向上实现归并排序

r囧r小猫 2023-06-12 06:26 19阅读 0赞

1.  首先是一个数组 ：![20191031222144854.png][]
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 1][]
4.   最后八个元素一个小段：最终完成了整个归并排序的过程。![20191031222358269.png][]

代码实现：

**main.cpp**:

#include <iostream>
    #include "SortTestHelper.h"
    #include "MergeSort.h"
    
    
    using namespace std;
    
    template <typename T>
    void mergeSortBU(T arr[], int n){
    
    //    for( int sz = 1; sz <= n ; sz += sz )
    //        for( int i = 0 ; i < n ; i += sz+sz )
    //            // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
    //            __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
    
        // Merge Sort Bottom Up 优化
        for( int i = 0 ; i < n ; i += 16 )
            insertionSort(arr,i,min(i+15,n-1));
    
        for( int sz = 16; sz <= n ; sz += sz )
            for( int i = 0 ; i < n - sz ; i += sz+sz )
                if( arr[i+sz-1] > arr[i+sz] )
                    __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
    }
    
    
    int main() {
    
        int n = 1000000;
    
        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("Merge Sort", mergeSort, arr1, n);
        SortTestHelper::testSort("Merge Sort Bottom Up", mergeSortBU, 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("Merge Sort", mergeSort, arr1, n);
        SortTestHelper::testSort("Merge Sort Bottom Up", mergeSortBU, arr2, n);
    
        delete(arr1);
        delete(arr2);
    
        return 0;
    }

**SortTestHelper.h:**

#ifndef INC_04_MERGE_SORT_BOTTOM_UP_SORTTESTHELPER_H
    #define INC_04_MERGE_SORT_BOTTOM_UP_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

** MergeSort.h:**

#ifndef INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H
    #define INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H
    
    #include <iostream>
    #include <algorithm>
    #include "InsertionSort.h"
    
    using namespace std;
    
    
    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 )   { 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 ++;}
        }
    }
    
    template<typename T>
    void __mergeSort(T arr[], int l, int r){
    
        if( r - l <= 15 ){
            insertionSort(arr, l, r);
            return;
        }
    
        int mid = (l+r)/2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid+1, r);
        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 );
    }
    
    #endif //INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H

**insertionSort.h:**

#ifndef INC_04_MERGE_SORT_BOTTOM_UP_INSERTIONSORT_H
    #define INC_04_MERGE_SORT_BOTTOM_UP_INSERTIONSORT_H
    
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    
    template<typename T>
    void insertionSort(T arr[], int n){
    
        for( int i = 1 ; i < n ; i ++ ) {
    
            T e = arr[i];
            int j;
            for (j = i; j > 0 && arr[j-1] > e; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    
        return;
    }
    
    // 对arr[l...r]范围的数组进行插入排序
    template<typename T>
    void insertionSort(T arr[], int l, int r){
    
        for( int i = l+1 ; i <= r ; i ++ ) {
    
            T e = arr[i];
            int j;
            for (j = i; j > l && arr[j-1] > e; j--)
                arr[j] = arr[j-1];
            arr[j] = e;
        }
    
        return;
    }
    
    #endif //INC_04_MERGE_SORT_BOTTOM_UP_INSERTIONSORT_H

[20191031222144854.png]: /images/20230531/86110b20ea1641d98542873b34fa7ea8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70]: /images/20230531/d4f754a105de4b5ea1e36e74ee36bcb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDc5NDY0_size_16_color_FFFFFF_t_70 1]: /images/20230531/9de33b73f1ff4c488ae90f1a376a3317.png
[20191031222358269.png]: /images/20230531/767c078989d549fab3859aaea35501c1.png