自底向上实现归并排序

首先是一个数组 ： 从左到右依次划分为小段：两个元素一个小段。 然后进行四个小段进行排序： 最后八个元素一个小段：最终完成了整个归并排序的过程。

 代码实现：

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