假设这里的排序都是升序。
Merge Sort:
归并排序。分治法（divide and conquer）思想入门的算法。Recursively 递归入栈时将字符串分为左右两半，直到无法分割为止。出栈时再把这两半合并起来，在合并的过程中排序。最后所有的栈返回是一个排好序的数组。在用分治法的时候注意一下和纯递归求解的区别。
// merge part
vector<int> merge(vector<int> A, vector<int> B) {
vector<int> rst;
std::vector<int>::iterator iter1 = A.begin(), iter2 = B.begin();
while (iter1 != A.end() || iter2 != B.end()) {
if (iter1 == A.end()) {
rst.insert(rst.end(), iter2, B.end());
break;
}
if (iter2 == B.end()) {
rst.insert(rst.end(), iter1, A.end());
break;
}
if (*iter1 < *iter2) {
rst.emplace_back(*iter1);
iter1++;
}
else {
rst.emplace_back(*iter2);
iter2++;
}
}
return rst;
}
// key part of merge sort, recursive function
vector<int> MSort(vector<int> array, int left, int right) {
vector<int> rst;
if (left == right) {
rst.emplace_back(array[left]);
return rst;
}
int mid = left + (right - left) / 2;
vector<int> leftArr = MSort(array, left, mid);
vector<int> rightArr = MSort(array, mid + 1, right);
rst = merge(leftArr, rightArr);
return rst;
}
// driver for merge sort
vector<int> mergeSort(vector<int> array) {
if (array.size() <= 1) return array;
vector<int> rst;
rst = MSort(array, 0, array.size() - 1);
return rst;
}
复杂度分析： $O(nlog(n))$
画出递归树，一共 $log(n)$ 层, 每一层是 $O(n)$ 的复杂度.
Demo: GeeksforGeeks
Quick Sort:
快速排序的核心的思想为是 partition. 这个思想在很多类型的问题中都会用到，会在后文举例说明。
快速排序的基本操作为：
- 选取一个pivot。
- 所有比pivot小的数放在pivot的左边，所有比pivot大的数放在pivot的右边。
- 分割数组：对pivot两边的数组递归重复以上步骤，直到不能分割。
具体有哪些实现呢。 先来看第一种方法。这是一个textbook的解法。
int median(vector<int>& arr, int left, int right){
// arr[left] <= arr[center] <= arr[right]
int center = left + (right - left)/2;
if (arr[left] > arr[center]) swap(&arr[left], &arr[center]);
if (arr[left] > arr[right]) swap(&arr[left], &arr[right]);
if (arr[center] > arr[right]) swap(&arr[center], &arr[right]);
swap(&arr[center], &arr[right - 1]); //hide pivot
return arr[right - 1];
}
void QSort(vector<int> & arr, int left, int right) {
// if (left >= right) return;
if (left + CutOff <= right){
int pivot = median(arr, left, right);
int i = left;
int j = right - 1;
for(;;){
while (arr[++i] < pivot){}
while (arr[--j] > pivot){}
if (i < j) swap(&arr[i], &arr[j]);
else break;
}
// if (left + 1 != right){
swap(&arr[i], &arr[right - 1]); //restore pivot
// }
QSort(arr, left, i - 1);
QSort(arr, i + 1, right);
}
else{
insertion_Sort(arr, left, right - left + 1);
}
}
vector<int> quickSort(vector<int> array) {
if (array.size() <= 1) return array;
QSort(array, 0, array.size() - 1);
return array;
}
另一个解法。基本思想是一样的。每次都要保持所有比pivot小的数放在pivot的左边，所有比pivot大的数放在pivot的右边这个条件。 实现的过程为，选取两块挡板，分别从数组的头和尾往中间靠拢，直到挡板相遇。在每一次的循环中，保证第一块挡板左边的数都小于pivot，第二块挡板右边的数都大于pivot。
事实上根据上面这个general rule来分，两个挡板指向的两个数只有四种情况：
$$a[i] < pivot, a[j] > pivot$$
$$a[i] < pivot, a[j] < pivot$$
$$a[i] > pivot, a[j] > pivot$$
$$a[i] >= pivot, a[j] <= pivot$$
那么对应刚才的rule该做着么呢？
满足条件：移动挡板i++， j–
满足前半个条件，移动挡板i++，继续检查条件
满足后半个条件，移动挡板j–，继续检查条件
不满足任何条件，但是一旦交换两个挡板上的数，即可让条件满足
void QuickSort(vector<int> & array, int left, int right){
if (left > right) return;
int pivot_index = (left + right)/2;
int pivot = array[pivot_index];
int left_bound = left;
int right_bound = right - 1;
//hide the pivot in the rightmost
std::swap(array[pivot_index], array[right]);
//three regions:
//1. [0, leftbound - 1] : all elements smaller than pivot should be here
//2. [leftbound, rightbound]: to be discovered, scan the element in a[leftbound], and move leftbound every step
//3. [rightbound + 1, array.size() - 1] all elements bigger than pivot should be here
while (left_bound <= right_bound) {
//check two
if (array[left_bound] < pivot) {
// obey all three rules, move leftbound
++left_bound;
}
else if (array[right_bound] > pivot) {
--right_bound;
}
else {
//array[left_bound] > pivot && array[right_bound < pivot]
std::swap(array[left_bound++], array[right_bound--]);
}
}
//restore the pivot to the original position
std::swap(array[left_bound], array[right]);
//partition and recursion
QuickSort(array, left, left_bound - 1);
QuickSort(array, left_bound + 1, right);
}
vector<int> quickSort(vector<int> array) {
if (array.size() <= 1) return array;
QuickSort(array, 0, array.size() - 1);
return array;
}
这样的解法可以归结为一种类型。比如一堆数中只有两种，三种四种数，那么就可以对应个数的挡板将数分割成相应区域，每次检查条件是否满足。Eg: Sort colors。这样的做法复杂度只需要$O(n)$.
Demo: GeeksforGeeks
Partition Extension I: Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
void sortColors(vector<int>& nums) {
int zero = 0;
int one = 0; //explorer
int two = nums.size() - 1;
//Three seperator Four regions
//[0, zero) 0
//[zero, one] 1
//(two, end] 2
while (one <= two) {
if (nums[one] == 0) {
swap(nums[one++], nums[zero++]);
} else if (nums[one] == 1) {
one++;
} else {
swap(nums[one], nums[two--]);
//don't move 'one':
//you don't know what is swaped from 'two'
}
}
}
Follow up I: four colors
vector<int> rainbowSortII(vector<int> array) {
int zero = 0, one = 0, other = array.size() - 1;
while (one <= other) {
if (array[one] < 1) {
swap(array[one++], array[zero++]);
} else if (array[one] > 1) {
swap(array[other--], array[one]);
} else {
one++;
}
}
int two = one, three = array.size() - 1;
while (two <= three) {
if (array[two] == 3 && array[three] == 2) {
swap(array[two++], array[three--]);
} else if (array[two] == 2) {
two++;
} else {
three--;
}
}
return array;
}
Follow up II: k colors
TODO: couting sort.
Partition Extension II: Kth smallest/largest element in an unsorted array
quick sort partition 思想的另一经典应用。 https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/
Wiggle Sort
$nums[0] <= nums[1] >= nums[2] <= nums[3]….$
这个时间复杂度优化到了O(n)。下面那个做法是通用的。
void wiggleSort(vector<int>& nums) {
for (int i=0; i<(int)nums.size() - 1; i++) {
if (i % 2 == 0 && nums[i] > nums[i+1]) {
swap(nums[i], nums[i+1]);
}
if (i % 2 == 1 && nums[i] < nums[i+1]) {
swap(nums[i], nums[i+1]);
}
}
}
Follow up: Wiggle Sort II
$nums[0] < nums[1] > nums[2] < nums[3]…$
根据这个性质，我们可以确定一种排法一定可以成立：把小的那一半排在偶数位，把大的那一半排在奇数位。这个是通用的。 时间复杂度 $ O(nlog(n)) $.
void wiggleSort(vector<int>& nums) {
vector<int> copy(nums);
sort(copy.begin(), copy.end());
int left = (nums.size() + 1) / 2 - 1;
int right = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) {
nums[i] = (i % 2 == 0)? copy[left--] : copy[right--];
}
}
传说中$O(n)$ 的解法。
Sort In Specified Order
A1 = {2, 1, 2, 5, 7, 1, 9, 3},
A2 = {2, 1, 3},
A1 is sorted to {2, 2, 1, 1, 3, 5, 7, 9}
vector<int> helper(vector<int> & A1, vector<int> & A2) {
// Write your solution here.
if (A1.size() <= 1 |||| A2.size() == 0) {
sort(A1.begin(), A1.end());
return A1;
}
map<int, int> t;
for (int i = 0; i < A2.size(); i++) {
t.emplace(A2[i], i);
}
int j = 0, k = A1.size() - 1;
while (j <= k) {
if (t.find(A1[j]) == t.end() && t.find(A1[k]) != t.end()) {
swap(A1[j], A1[k]);
j++;
k--;
}
else if (t.find(A1[j]) != t.end()) {
j++;
}
else {
k--;
}
}
//sort the [0, j) in specified order
//[2 1 3 4]
//2 1 2 1 4 3 => 2 2 1 1 3 4
for (int i = 0; i < j; i++) {
int min_index = i;
for (int l = i; l < j; l++) {
if (t[A1[min_index]] > t[A1[l]]) {
min_index = l;
}
}
swap(A1[i], A1[min_index]);
}
//sort the (k, n) part in ascending order
sort(A1.begin() + k + 1, A1.end());
return A1;
}
Insertion Sort:
插入排序。假设一个长度为N的数组$A[]$，总体过程为，从 index 为 1 开始到 N-1，使得 $A[0,index]$ 是一个排好序的数组。
template<typename T>
void insertion_sort(T arr[], int len){
for (int i = 1; i < len; i++){
int temp = arr[i];
for (int j = i; j > 0 && arr[j-1]>temp; j--){ //实际比较的是j-1
arr[j] = arr[j-1]; //全部往后移一位腾出位置等插入
}
arr[j] = temp; //插入到腾出来的位置
}
}
复杂度： $O(n^2)$
Selection Sort:
选择排序。假设一个长度为N的数组$A[]$，总体过程为，从index为0开始到N-1，使得$A[0,index]$是一个排好序的数组。
怎么跟插入排序这么像呢？是挺像的，但是具体的过程是有区别。这区别就是“插入”和“选择”的区别。
插入排序是每次往前面那些已经排序好的数里“插入”进去，而选择排序则是，每次从这个数后面那些没排好序的数里“选择”到最小的，和这个数交换。
template<typename T>
void selection_sort(T arr[], int len){
for (int i = 0; i < len - 1; i++){ //len - 1即可，最后一次交换在倒数第一个和倒数第二个之间进行
int min_index = i;
for (int j = i + 1; j < len; j++){
//找到未排序的数组中最小的数的index
if (arr[j]<arr[min_index]){
min_index = j;
}
}
swap(arr[i], arr[min_index]);
}
}
复杂度分析： $O(n^2)$的复杂度。实际上是冒泡排序的一个优化，虽然最坏时间复杂度上是一样的。
附上冒泡排序代码。
void bubble_sort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}