voidquick_sort(vector<int> &nums, int l, int r) { if (l + 1 >= r) { return; } int first = l, last = r - 1, key = nums[first]; while (first < last){ while(first < last && nums[last] >= key) { --last; } nums[first] = nums[last]; while (first < last && nums[first] <= key) { ++first; } nums[last] = nums[first]; } nums[first] = key; quick_sort(nums, l, first); quick_sort(nums, first + 1, r); }
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
把长度为n的输入序列分成两个长度为n/2的子序列;
对这两个子序列分别采用归并排序;
将两个排序好的子序列合并成一个最终的排序序列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidmerge_sort(vector<int> &nums, int l, int r, vector<int> &temp) { if (l + 1 >= r) { return; } // divide int m = l + (r - l) / 2; merge_sort(nums, l, m, temp); merge_sort(nums, m, r, temp); // conquer int p = l, q = m, i = l; while (p < m || q < r) { if (q >= r || (p < m && nums[p] <= nums[q])) { temp[i++] = nums[p++]; } else { temp[i++] = nums[q++]; } } for (i = l; i < r; ++i) { nums[i] = temp[i]; } }
// 上浮 从下到上调整堆 voidswim(vector<int>& heap, int i){ while (i > 0 && priorityThan(heap[i], heap[(i - 1) / 2])) { swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } }
// 下沉 从下到上调整堆 voidsink(vector<int>& heap, int i, int N){ while (2 * i + 1 <= N) { int j = 2 * i + 1; if (j + 1 <= N && priorityThan(heap[j + 1], heap[j])) { j++; } if (priorityThan(heap[i], heap[j])) { break; } swap(heap[i], heap[j]); i = j; } } };