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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
| class my_sort { public: void bubble_sort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { swap(arr[i], arr[j]); } } } }
void quick_sort(vector<int>& arr) { _quick_sort_(arr, 0, arr.size() - 1); }
void merge_sort(vector<int>& arr) { vector<int> temp(arr.size()); merge(temp, arr, 0, arr.size()); }
void shell_sort(vector<int>& arr) { for (int seg = arr.size(); seg > 0; seg /= 2) { single_shell_sort(arr, seg); } }
void insertion_sort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int l = 0, r = i; while (l < r) { int mid = l + (r - l) / 2; if (arr[mid] < arr[i]) { l = mid + 1; } else { r = mid; } } for (int j = i; j >= l + 1; j--) { swap(arr[j], arr[j - 1]); } } }
void heap_sort(vector<int>& arr) { int n = arr.size(); for (int i = n / 2 - 1; i >= 0; i--) { heap_adjust(arr, i, n - 1); } for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heap_adjust(arr, 0, i - 1); } }
void selection_sort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n; i++) { swap(arr[i], arr[find_min(arr, i)]); } }
private: void single_shell_sort(vector<int>& arr, int dk) { int n = arr.size(); for (int i = dk; i < n; i++) { if (arr[i] < arr[i - dk]) { int tmp = arr[i]; int j = 0; for (j = i - dk; j >= 0 && arr[j] > tmp; j -= dk) { arr[j + dk] = arr[j]; } arr[j + dk] = tmp; } } } void heap_adjust(vector<int>& arr, int start, int end) { int dad = start; int son = dad * 2 + 1; while (son <= end) { if (son + 1 <= end && arr[son] < arr[son + 1]) { son++; } if (arr[son] < arr[dad]) { return; } else { swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } } } void _quick_sort_(vector<int>& arr, int start, int end) { if (start >= end) { return; } else { int i = start, j = end; int tmp = arr[start]; while (i < j) { for (; i < j && tmp < arr[j];j--) {} if (i < j) { swap(arr[i], arr[j]); i++; } for (; i < j && arr[i] < tmp ;i++) {} if (i < j) { swap(arr[i], arr[j]); j--; } } _quick_sort_(arr, start, i - 1); _quick_sort_(arr, i + 1, end); } } int adjust_arr(vector<int>& arr, int l, int r) { int i = l + 1, j = r - 1, key = arr[l]; while (i < j) { for(; arr[i] <= key && i < j; i++) {} swap(arr[l], arr[i]); for(; arr[j] >= key && i < j; j--) {} swap(arr[l], arr[j]); } return i; } void merge(vector<int>& temp, vector<int>& arr, int l, int r) { if (r - l > 1) { int mid = (l + r) >> 1; merge(temp, arr, l, mid); merge(temp, arr, mid, r); int i = l, j = mid, k = 0; while (i < mid && j < r) { temp[k] = (arr[i] < arr[j] ? arr[i++] : arr[j++]); k++; } while (j < r) { temp[k++] = arr[j++]; } while (i < mid) { temp[k++] = arr[i++]; } for (int i = 0; i < k; i++) { arr[i + l] = temp[i]; } } } int find_min(vector<int>& arr, int cur_index) { int i = cur_index, n = arr.size(); for (int j = i; j < n; j++) { i = (arr[j] < arr[i] ? j : i); } return i; } };
|