Quick Sort This is used in research code when built-in qsort does not satisfy the demands.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void qs(int l, int r){ int p, mid, i, j; i = l; j = r; mid = avg[(l + r) >> 1]; do { while (avg[i] < mid) ++i; while (avg[j] > mid) --j; if (i <= j){ swap(avg[i], avg[j]); swap(order[i], order[j]); ++i; --j; } } while (i < j); if (l < j) qs(l, j); if (i < r) qs(i, r); } |
K-th element Qsort can be used to find the Kth smallest element a[k]:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void Kth(int l,int r,int k) { int i = l,j = r,mid= a [(i + j) >> 1]; while (i <= j) { while (a[i] < mid) ++i; while (a[j] > mid) --j; if (i<=j) { int t = a[i]; a[i] = a[j]; a[j] = t; ++i;--j; } } if (k >= i && k<= r) Kth(i, r, k); if (k >= l && k<= j) Kth(l, j, k); } |
In Python,
|
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 |
class Solution(object): def kSort(self, a, l, r, k): i, j, p = l, r, a[(l + r) >> 1] while i < j: while a[i] < p: i += 1 while a[j] > p: j -= 1 if i <= j: a[i], a[j] = a[j], a[i] i += 1 j -= 1 if l < j and k <= j: self.kSort(a, l, j, k) if i < r and k >= i: self.kSort(a, i, r, k) def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ self.kSort(nums, 0, len(nums) - 1, len(nums) - k) return nums[len(nums) - k] |
Use partition to sort 0, 0, 0, 1, 1, 2, 2, 2…
|
1 2 3 4 5 6 |
void Solutions::sortColors(vector<int>& nums) { partition( partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)), nums.end(), bind1st(equal_to<int>(), 1) ); } |
Merge Sort Linked List Version Here…
