选择排序、插入排序、归并排序
main.cpp
1 #include <iostream> 2 #include "Student.h" 3 #include "SortTestHelper.h" 4 5 using namespace std; 6 7 template<typename T> 8 void selectionSort(T arr[],int n){ 9 for(int i = 0 ; i < n ; i ++){ 10 int minIndex = i; 11 for( int j = i + 1 ; j < n ; j ++ ) 12 if( arr[j] < arr[minIndex] ) 13 minIndex = j; 14 swap( arr[i] , arr[minIndex] ); 15 } 16 } 17 18 template<typename T> 19 void insertionSort(T arr[],int n){ 20 for(int i = 1 ; i < n ; i++ ){ 21 T e = arr[i]; 22 int j; 23 for(j = i ; j > 0 && arr[j-1] > e ; j --) 24 arr[j] = arr[j-1]; 25 arr[j] = e; 26 } 27 } 28 29 template<typename T> 30 // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 31 void __merge(T arr[] , int l, int mid, int r){ 32 T aux[r-l+1]; 33 // 将数组复制一份到aux[] 34 for( int i = l ; i <= r ; i ++ ) 35 aux[i-l] = arr[i]; 36 // 初始化，i、j指向左、右半部分的起始索引位置 37 int i = l, j = mid + 1; 38 for( int k = l ; k <= r ; k ++ ){ 39 // 如果左半部分已处理完毕 40 if( i > mid){ 41 arr[k] = aux[j-l]; 42 j++; 43 } 44 // 如果右半部分已处理完毕 45 else if( j > r){ 46 arr[k] = aux[i-l]; 47 i ++; 48 } 49 // 左半部分所指元素 < 右半部分所指元素 50 else if( aux[i-l] < aux[j-l] ){ 51 arr[k] = aux[i-l]; 52 i ++; 53 } 54 // 左半部分所指元素 >= 右半部分所指元素 55 else{ 56 arr[k] = aux[j-l]; 57 j++; 58 } 59 } 60 } 61 62 // 递归使用归并排序，对arr[l...r]的范围进行排序 63 template<typename T> 64 void __mergeSort(T arr[] , int l, int r){ 65 66 if( l >= r) 67 return; 68 69 int mid = (l+r)/2; 70 __mergeSort(arr,l,mid); 71 __mergeSort(arr,mid+1,r); 72 __merge(arr, l, mid, r); 73 } 74 75 template<typename T> 76 void mergeSort(T arr[] , int n){ 77 __mergeSort( arr , 0 , n-1 ); 78 } 79 80 int main(){ 81 int n = 10000; 82 //int *arr = SortTestHelper::generateNearlyOrderedArray(n,10); 83 int *arr1 = SortTestHelper::generateRandomArray(n,0,n); 84 int *arr2 = SortTestHelper::copyIntArray(arr1, n); 85 SortTestHelper::testSort("Insertion Sort",insertionSort,arr1,n); 86 SortTestHelper::testSort("Merge Sort",mergeSort,arr2,n); 87 88 delete[] arr1; 89 delete[] arr2; 90 91 return 0; 92 }
SortTestHelper.h
1 #include <iostream> 2 #include <ctime> 3 #include <cassert> 4 #include <string> 5 6 using namespace std; 7 8 namespace SortTestHelper{ 9 // 生成随机数组 10 int *generateRandomArray(int n,int rangeL,int rangeR){ 11 assert(rangeL <= rangeR); 12 int *arr = new int[n]; 13 srand(time(NULL)); 14 for(int i = 0 ; i < n ; i++) 15 arr[i] = rand()%(rangeR-rangeL+1) + rangeL; 16 return arr; 17 } 18 // 生成近似有序数组 19 int *generateNearlyOrderedArray(int n, int swapTimes){ 20 int *arr = new int[n]; 21 for(int i = 0 ; i < n ; i ++ ) 22 arr[i] = i; 23 srand(time(NULL)); 24 for( int i = 0 ; i < swapTimes ; i ++){ 25 int posx = rand()%n; 26 int posy = rand()%n; 27 swap( arr[posx] , arr[posy] ); 28 } 29 return arr; 30 } 31 32 // 拷贝整型数组a中所有元素到新数组并返回 33 int *copyIntArray(int a[], int n){ 34 int *arr = new int[n]; 35 copy(a, a+n, arr); 36 return arr; 37 } 38 39 // 打印arr数组的所有内容 40 template<typename T> 41 void printArray(T arr[],int n){ 42 for(int i = 0;i<n;i++) 43 cout << arr[i] <<" "; 44 cout << endl; 45 return; 46 } 47 48 // 判断arr数组是否有序 49 template<typename T> 50 bool isSorted(T arr[],int n){ 51 for(int i = 0 ; i<n-1 ; i++) 52 if(arr[i] > arr[i+1]) 53 return false; 54 return true; 55 } 56 57 // 测试sort排序算法排序arr数组所得结果的正确性和算法运行时间 58 template<typename T> 59 void testSort(const string &sortName,void (*sort)(T[],int),T arr[],int n){ 60 61 clock_t startTime = clock(); 62 sort(arr,n); 63 clock_t endTime = clock(); 64 65 assert(isSorted(arr,n)); 66 67 cout << sortName << " : " << double(endTime-startTime)/CLOCKS_PER_SEC << " s" <<endl; 68 69 return; 70 } 71 }
运行结果：
Merge Sort可在1s内轻松处理100万数量级的数据