TimSort
TimSort其实就是插入排序和合并排序的综合体. 首先切分数组, 然后利用插入排序对小数组的优势, 先sort小数组, 然后再merge几个小数组. code我是直接抄github的
|
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
// C++ program to perform TimSort. #include <iostream> using namespace std; const int RUN = 32; // this function sorts array from left index to to right index which is of size atmost RUN void insertionSort(int arr[], int left, int right) { for (int i = left + 1; i <= right; i++) { int temp = arr[i]; int j = i - 1; while (arr[j] > temp && j >= left) { arr[j+1] = arr[j]; j--; } arr[j+1] = temp; } } // merge function merges the sorted runs void merge(int arr[], int l, int m, int r) { // original array is broken in two parts, left and right array int len1 = m - l + 1, len2 = r - m; int left[len1], right[len2]; for (int i = 0; i < len1; i++) left[i] = arr[l + i]; for (int i = 0; i < len2; i++) right[i] = arr[m + 1 + i]; int i = 0; int j = 0; int k = l; // after comparing, we merge those two array in larger sub array while (i < len1 && j < len2) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } // copy remaining elements of left, if any while (i < len1) { arr[k] = left[i]; k++; i++; } // copy remaining element of right, if any while (j < len2) { arr[k] = right[j]; k++; j++; } } // iterative Timsort function to sort the array[0...n-1] (similar to merge sort) void timSort(int arr[], int n) { // Sort individual subarrays of size RUN for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); // start merging from size RUN (or 32). It will merge to form size 64, then 128, 256 and so on .... for (int size = RUN; size < n; size = 2*size) { // pick starting point of left sub array. We are going to merge arr[left..left+size-1] and arr[left+size, left+2*size-1] // After every merge, we increase left by 2*size for (int left = 0; left < n; left += 2*size) { // find ending point of left sub array // mid+1 is starting point of right sub array int mid = left + size - 1; int right = min((left + 2*size - 1), (n-1)); // merge sub array arr[left.....mid] & arr[mid+1....right] merge(arr, left, mid, right); } } } // utility function to print the Array void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } // Driver program to test above function int main() { int arr[] = {5, 21, 7, 23, 19}; int n = sizeof(arr)/sizeof(arr[0]); printf("Given Array is\n"); printArray(arr, n); timSort(arr, n); printf("After Sorting Array is\n"); printArray(arr, n); return 0; } |