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 is the merge sort when qsort does not work:
|
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 |
ListNode* sortList(ListNode* head) { // merge sort if (!head || !head->next) return head; // find mid O(n) ListNode *fast = head, *slow = head; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; } // break into two fast = slow; slow = slow->next; fast->next = NULL; ListNode *left = sortList(head); ListNode *right = sortList(slow); return mergeTwoLists(left, right); } ListNode* mergeTwoLists(ListNode* left, ListNode* right) { ListNode dummy(-1); for (ListNode* p = &dummy; left || right; p = p->next) { int l = left ? left->val : INT_MAX; int r = right ? right->val : INT_MAX; if (l <= r) { p->next = left; left = left->next; } else { p->next = right; right = right->next; } } return dummy.next; } |
Array Version
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
void ms(vector<int> nums, int l, int r) { if (l == r) return; int p = (l + r) >> 1; ms(nums, l, p); ms(nums, p + 1, r); int i = l, j = p + 1; int n = r - l + 1; vector<int> tmp(n); for (int k = 0; k < n; ++k) { if (j > r || (i <= p && nums[i] < nums[j])) { tmp[k] = nums[i]; ++i; } else { tmp[k] = nums[j]; ++j; } } for (int k = 0, i = l; k < n; ++k, ++i) { nums[i] = tmp[k]; } } |
Merge
Given two sorted arrays A and B, merge B into A:
|
1 2 3 4 5 6 7 8 9 |
void Solutions::merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while (i >= 0 && j >= 0) { nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--]; } while (j >= 0) { nums1[k--] = nums2[j--]; } } |
What about Lists?
|
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 |
ListNode* Solutions::mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; ListNode* h = new ListNode(0); ListNode* ans = h; while (l1 != nullptr || l2 != nullptr) { if (l1 == nullptr) { h->next = l2; break; } if (l2 == nullptr) { h->next = l1; break; } if (l1->val < l2->val) { h->next = l1; h = h->next; l1 = l1->next; } else { h->next = l2; h = h->next; l2 = l2->next; } } return ans->next; } |
Bucket Sort
O(n)
Find the first missing positive
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int Solutions::firstMissingPositive(vector<int>& nums) { const int n = (int)nums.size(); for (int i = 0; i < n; ++i) { while (nums[i] != i + 1) { if (nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1]) break; swap(nums[i], nums[nums[i] - 1]); } } for (int i = 0; i < n; ++i) if (nums[i] != (i + 1)) return i + 1; return n + 1; } |
Bubble Sort
O(n^2)
|
1 2 3 4 5 6 7 8 9 |
int n; while (n > 0) { for (int i = 0; i < n - 1; ++i) { if (a[i] > a[i + 1]) { // use '< for descending order swap(a[i], a[i + 1]); } } --n; } |
Sort 4 Elements
|
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 |
function sort(i, j, k, l) { if (i < j) { if (j < k) { if (k < l) return [i,j,k,l]; if (j < l) return [i,j,l,k]; if (i < l) return [i,l,j,k]; return [l,i,j,k]; } else if (i < k) { if (j < l) return [i,k,j,l]; if (k < l) return [i,k,l,j]; if (i < l) return [i,l,k,j]; return [l,i,k,j]; } else { if (j < l) return [k,i,j,l]; if (i < l) return [k,i,l,j]; if (k < l) return [k,l,i,j]; return [l,k,i,j]; } } else { if (i < k) { if (k < l) return [j,i,k,l]; if (i < l) return [j,i,l,k]; if (j < l) return [j,l,i,k]; return [l,j,i,k]; } else if (j < k) { if (i < l) return [j,k,i,l]; if (k < l) return [j,k,l,i]; if (j < l) return [j,l,k,i]; return [l,j,k,i]; } else { if (i < l) return [k,j,i,l]; if (j < l) return [k,j,l,i]; if (k < l) return [k,l,j,i]; return [l,k,j,i]; } } } |
