Overview

quick sort

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

void quickSortBase(vector<int>& v, int low, int high) {
	if (low >= high) return;
	int key = v[low], start = low, end = high;
	while (start < end) {
		//find element smaller than key, break when v[end] < key, choose end
		while (start < end && v[end] >= key)
			end--;
		v[start] = v[end];
		//find element bigger than key, break when v[start] > key, choose start
		while (start < end && v[start] <= key)
			start++;
		v[end] = v[start];
	}
	//store key in suitable position
	v[start] = key;
	quickSortBase(v, low, start - 1);
	quickSortBase(v, start + 1, high);
}
void quickSort(vector<int>& v) {
	quickSortBase(v, 0, v.size() - 1);
}

优化

当数列近乎有序的时，由于每次选取的都是第一个数，所以造成数列分割的极其不等，此时快排蜕化成 O(n^2) 的算法，此时只要随机选取基准点即可
当数列中包含大量的重复元素的时候，这一版的代码也会造成”分割不等“的问题，此时需要将重复元素均匀的分散的自数列旁
使用三路快排

bubble sort

对一个数组进行多次遍历，比较相邻的两项，如果顺序错了则交换。每次遍历，都会有最大项放在了正确的位置。
假如有n个元素，进行升序排序，则第一轮要进行n-1次比较，然后最大的数放在最后，然后对前面n-1个元素进行第二次遍历，进行n-2次比较，其中最大的放在倒数第二个位置。

void bubbleSort(vector<int>& v) {
	int len = v.size();
	for (int i = len - 1; i >= 0; --i) {
		for (int j = 0; j <= i - 1; ++j) {
			if (v[j] > v[j + 1]) {
				// swap
				int tmp = v[j + 1];
				v[j + 1] = v[j];
				v[j] = tmp;
			}
		}
	}
}

优化

因为冒泡排序必须要在最终位置找到之前不断交换数据项，所以它经常被认为是最低效的排序方法。这些 “浪费式” 的交换操作消耗了许多时间。但是，由于冒泡排序要遍历整个未排好的部分，它可以做一些大多数排序方法做不到的事。尤其是如果在整个排序过程中没有交换，我们就可断定列表已经排好。因此可改良冒泡排序，使其在已知列表排好的情况下提前结束。
如果一个列表只需要几次遍历就可排好，冒泡排序就占有优势

void bubbleSort(vector<int>& v) {
	int len = v.size();
	bool isExchanged = false;
	for (int i = len - 1; i >= 0; --i) {
		isExchanged = false;
		for (int j = 0; j <= i - 1; ++j) {
			if (v[j] > v[j + 1]) {
				int tmp = v[j + 1];
				v[j + 1] = v[j];
				v[j] = tmp;
				isExchanged = true;
			}
		}
		if (!isExchanged)
			return;
	}
}

select sort

选择排序提高了冒泡排序的性能，它每遍历一次列表只交换一次数据，即进行一次遍历时找到最大的项，完成遍历后，再把它换到正确的位置。

void selectSort(vector<int>& v) {
	int len = v.size();
	for (int i = len - 1; i >= 0; --i) {
		int maxPos = 0;
		for (int j = 0; j <= i; ++j) {
			if (v[j] > v[maxPos]) {
				maxPos = j;
			}
		}
		// swap
		int tmp = v[i];
		v[i] = v[maxPos];
		v[maxPos] = tmp;
	}
}

insert sort

它总是保持一个位置靠前的已排好的子数组，然后每一个新的数据项被 “插入” 到前边的子数组里，排好的子数组增加一项。

void insertSortBase(vector<int>& v, int low, int high) {
	if (low >= high)
		return;
	cout << "start:" << low << ", end:" << high << endl;
	for (int i = low + 1; i <= high; ++i) {
		int cur = v[i];
		int j = i - 1;
		for (; j >= low; --j) {
			if (v[j] > cur) {
				v[j + 1] = v[j];
			}
			else {
				v[j + 1] = cur;
				break;
			}
		}
		// corner case
		if (j + 1 == low)
			v[low] = cur;
	}
}
void insertSort(vector<int>& v) {
	insertSortBase(v, 0, v.size() - 1);
}

shell sort

是优化版的插入排序，核心思想是把把每间隔为gap的所有元素选出来组成子数组，然后对每个子数组进行插入排序，最后当 gap = 1 时，对整体进行一次直接插入排序

void gapInsertSort(vector<int>& v, int start, int gap) {
	int len = v.size();
	for (int i = start + gap; i < len; i += gap) {
		int cur = v[i];
		int j = i - gap;
		for (; j >= start; j = j - gap) {
			if (v[j] > cur) {
				v[j + gap] = v[j];
			}
			else {
				v[j + gap] = cur;
				break;
			}
		}
		// corner case
		if (j + gap == start)
			v[start] = cur;
	}
}
void shellSort(vector<int>& v) {
	int len = v.size();
	for (int gap = len / 2; gap > 0; gap = gap / 2) {
		for (int i = 0; i < gap; ++i) {
			gapInsertSort(v, i, gap);
		}
	}
}

merge sort

归并排序是一种递归算法，它持续地将一个列表分成两半。如果列表是空的或者只有一个元素，那么根据定义，它就被排序好了（最基本的情况）。如果列表里的元素超过一个，我们就把列表拆分，然后分别对两个部分调用递归排序。有自顶向下（递归法）和自底向上的两种实现方法

vector<int> merge(vector<int>& v1, vector<int>& v2) {
	int len1 = v1.size(), len2 = v2.size(), p1 = 0, p2 = 0;
	vector<int> ret;
	while (p1 < len1 && p2 < len2) {
		int a = v1[p1], b = v2[p2];
		if (a <= b) {
			ret.push_back(a);
			p1++;
		}
		else {
			ret.push_back(b);
			p2++;
		}
	}
	for (; p1 < len1; p1++) {
		ret.push_back(v1[p1]);
	}
	for (; p2 < len2; p2++) {
		ret.push_back(v2[p2]);
	}
	return ret;
}
vector<int> mergeSortBase(vector<int>& v, int low, int high) {
	if (low > high)
		return {};
	if (low == high)
		return vector<int>(1, v[low]);
	int mid = (low + high) / 2;
	vector<int> left = mergeSortBase(v, low, mid);
	vector<int> right = mergeSortBase(v, mid + 1, high);
	return merge(left, right);
}
vector<int> mergeSort(vector<int>& v) {
	return mergeSortBase(v, 0, v.size() - 1);
}

test case

int main() {
	vector<int> src;
	for (int i = 0; i < 10000; ++i) {
		src.push_back(rand());
	}
	vector<int> dst(src);

	sort(src.begin(), src.end());
	// YourSortFunction(dst); 

	for (int i = 0; i < 10000; ++i) {
		if (src[i] != dst[i]) {
			cout << "false" << endl;
			cout << "i:" << i << ", src:" << src[i] << ", dst:" << dst[i];
			return 0;
		}
	}
	cout << "true";
	return 0;
}

Reference

https://zhuanlan.zhihu.com/p/40695917

zztttt

Sort Algorithm