排序算法 1 O(n)2 1 2 3 4 5 6 7 8 9 for (int i = 0 ; i < n ; i ++){ int minIndex = i; for ( int j = i + 1 ; j < n ; j ++ ) if ( arr[j] < arr[minIndex] ) minIndex = j; swap( arr[i] , arr[minIndex] ); }
2 插入排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 for ( int i = 1 ; i < n ; i ++ ) { for ( int j = i ; j > 0 ; j-- ) if ( arr[j] < arr[j-1 ] ) swap( arr[j] , arr[j-1 ] ); else break ; for ( int j = i ; j > 0 && arr[j] < arr[j-1 ] ; j -- ) swap( arr[j] , arr[j-1 ] ); }
3 插入排序优化 swap交换需要赋值三次,可以改进。
1 2 3 4 5 6 7 for (int i = 0 ; 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; }
4 冒泡排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 bool swapped; do{ swapped = false; for( int i = 1 ; i < n ; i ++ ) if( arr[i-1] > arr[i] ){ swap( arr[i-1] , arr[i] ); swapped = true; } // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置 // 所以下一次排序, 最后的元素可以不再考虑 n --; }while(swapped);
5 希尔排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093... int h = 1; while( h < n/3 ) h = 3 * h + 1; while( h >= 1 ){ // h-sort the array for( int i = h ; i < n ; i ++ ){ // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序 T e = arr[i]; int j; for( j = i ; j >= h && e < arr[j-h] ; j -= h ) arr[j] = arr[j-h]; arr[j] = e; } h /= 3; }
6 归并排序 数组分成两半进行排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 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 ( 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 ); }
7 归并排序优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 template <typename T>void __mergeSort2(T arr[], int l, int r){ if ( r - l <= 15 ){ insertionSort(arr, l, r); return ; } int mid = (l+r)/2 ; __mergeSort2(arr, l, mid); __mergeSort2(arr, mid+1 , r); if ( arr[mid] > arr[mid+1 ] ) __merge(arr, l, mid, r); } template <typename T>void mergeSort2 (T arr[], int n) { __mergeSort2( arr , 0 , n-1 ); }
8 自底向上归并排序 变递归为迭代,而且可用于链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 template <typename T>void mergeSortBU (T arr[], int n) { for ( int sz = 1 ; sz < n ; sz += sz ) for ( int i = 0 ; i < n - sz ; i += sz+sz ) __merge(arr, i, i+sz-1 , min (i+sz+sz-1 ,n-1 ) ); 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 ) ); }
9 快速排序 将第一个元素作为标记点,找到该标记的正确位置,之前的元素小于标记元素,之后的元素大于标记元素。
快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 int __partition(T arr[], int l, int r){ T v = arr[l]; int j = l; for ( int i = l + 1 ; i <= r ; i ++ ) if ( arr[i] < v ){ j ++; swap( arr[j] , arr[i] ); } swap( arr[l] , arr[j]); return j; } template <typename T>void __quickSort(T arr[], int l, int r){ if ( l >= r ) return ; int p = __partition(arr, l, r); __quickSort(arr, l, p-1 ); __quickSort(arr, p+1 , r); } template <typename T>void quickSort (T arr[], int n) { __quickSort(arr, 0 , n-1 ); }
10 随机化快速排序 随机选择标定点,改善近似顺序列表排序性能
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 template <typename T>int _partition(T arr[], int l, int r){ swap( arr[l] , arr[rand()%(r-l+1 )+l] ); T v = arr[l]; int j = l; for ( int i = l + 1 ; i <= r ; i ++ ) if ( arr[i] < v ){ j ++; swap( arr[j] , arr[i] ); } swap( arr[l] , arr[j]); return j; } template <typename T>void _quickSort(T arr[], int l, int r){ if ( r - l <= 15 ){ insertionSort(arr,l,r); return ; } int p = _partition(arr, l, r); _quickSort(arr, l, p-1 ); _quickSort(arr, p+1 , r); } template <typename T>void quickSort (T arr[], int n) { srand(time(NULL )); _quickSort(arr, 0 , n-1 ); }
11 双路快速排序 从两头向中间执行partition,使等于v的元素分散在两边,使两部分尽量平衡,适用于大量重复数据的场合
双路快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 template <typename T>int _partition2(T arr[], int l, int r){ swap( arr[l] , arr[rand()%(r-l+1 )+l] ); T v = arr[l]; int i = l+1 , j = r; while ( true ){ while ( i <= r && arr[i] < v ) i ++; while ( j >= l+1 && arr[j] > v ) j --; if ( i > j ) break ; swap( arr[i] , arr[j] ); i ++; j --; } swap( arr[l] , arr[j]); return j; } template <typename T>void _quickSort(T arr[], int l, int r){ if ( r - l <= 15 ){ insertionSort(arr,l,r); return ; } int p = _partition2(arr, l, r); _quickSort(arr, l, p-1 ); _quickSort(arr, p+1 , r); } template <typename T>void quickSort (T arr[], int n) { srand(time(NULL )); _quickSort(arr, 0 , n-1 ); }
12 三路快速排序
三路快速排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 template <typename T>void __quickSort3Ways(T arr[], int l, int r){ if ( r - l <= 15 ){ insertionSort(arr,l,r); return ; } swap( arr[l], arr[rand()%(r-l+1 )+l ] ); T v = arr[l]; int lt = l; int gt = r + 1 ; int i = l+1 ; while ( i < gt ){ if ( arr[i] < v ){ swap( arr[i], arr[lt+1 ]); i ++; lt ++; } else if ( arr[i] > v ){ swap( arr[i], arr[gt-1 ]); gt --; } else { i ++; } } swap( arr[l] , arr[lt] ); __quickSort3Ways(arr, l, lt-1 ); __quickSort3Ways(arr, gt, r); } template <typename T>void quickSort3Ways (T arr[], int n) { srand(time(NULL )); __quickSort3Ways( arr, 0 , n-1 ); }
最后更新时间:2020-05-07 15:14:55
转载请注明出处