插入排序

插入排序是指每次排序的元素插入到已排序的列表中，和洗扑克牌一样。对于顺序表，插入所花时间很多。

直接插入排序

从左到右选择元素插入到已排序列表，插入时保证使已排序列表依然有序。初始已排序列表为空

基本算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool insertionSort(int arr[], const int len) {
	for (int i = 1; i < len; i++)
	{
		auto j = i;
		auto tmp = arr[i];
		while (j != 0 && arr[j - 1] > tmp) {//找到该插入的位置，并同时后一一位
			arr[j] = arr[j - 1];
			j--;
		}
		arr[j] = tmp;//插入
		pArr(arr, len);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename Container>
int insertionSort(Container& container) {
	auto first = std::begin(container);
	auto end = std::end(container);
	if (first == end) return 0;

	for (auto i = std::next(first); i != end; i++) {
		auto key = *i;
		auto j = i;

		while (j != first && (*std::prev(j) > key)) {
			*j = *std::prev(j);
			j--;
		}
		*j = key;
	}
	return 0;
}
1
2
Average time for 10000 runs and 1000 elements: 0.00060332 seconds
Total time:6.03324770

直接插入排序有两个循环，所以一般情况下时间复杂度是$O(n)*O(n)=O(n^2)$，最坏的情况是完全逆序，与平均相同，最好情况为顺序，内循环不需要比较，所以时间复杂度为$O(n)$
对于空间复杂度，需要额外空间存放一个元素，所以是$O(1)$

二分插入排序

也叫折半插入排序，直接插入排序使用了顺序查找，效率较低，所以把顺序查找换成二分查找能提高内循环效率，然而还是插入，感觉没有提高多少效率

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
bool binaryInsertionSort(int arr[], const int len) {
	for (int i = 1; i < len; i++)
	{
		auto high = i;
		auto low = 0;
		auto mid = 0;
		auto tmp = arr[i];
		while (low < high) {
			mid = (low + high) / 2;
			if (arr[mid] < tmp) {
				low = mid + 1;//防止len=2时卡死？
			}
			if (arr[mid] > tmp) {
				high = mid;
			}
			if (arr[mid] == tmp) {
				high = low = mid;
				break;
			}
		}
		for (int j = i; j > low; --j)//只移动
		{
			arr[j] = arr[j - 1];
		}
		arr[low] = tmp;//插入

		pArr(arr, len);
	}
	return 0;
}
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
template <typename Container>
bool binaryInsertionSort(Container& container) {
	auto first = std::begin(container);
	auto end = std::end(container);
	if (first == end) return false;
	for (auto i = std::next(first); i != end; ++i) {
		auto high = i;
		auto low = first;
		auto mid = first;
		auto tmp = *i;

		while (low < high) {
			mid = low;
			std::advance(mid, std::distance(low, high) / 2);
			if (*mid < tmp) {
				low = std::next(mid);
			}
			else {
				high = mid;
			}
		}

		for (auto j = i; j > low; --j) {
			*j = *std::prev(j);
		}
		*low = tmp;
	}
	return true;
}
1
2
Average time for 10000 runs and 1000 elements: 0.00054250 seconds
Total time:5.42496460

我多试了几次(20长度)，发现比直接插入的速度慢，难道是我写错了？QAQ，可能是算法太菜了。

外循环$O(n)$，内循环查找+插入$O(log_2n)+O(n)$，所以总体时间复杂度：$O(nlog_2n)+O(n^2)=O(n^2)$，对于最好时间，已排序完成，$O(n)$，最差时间，倒序$O(n^2)$

这么一看在n小时用直接插入，n大时用二分插入更好。
对于空间复杂度，由于有4个额外空间，所以是$O(4)$

希尔排序

又叫缩小增量排序。直接插入排序有两个性质，在快排序好时，效率高，大概能到O(n)，但是插入操作十分低效因为每次都只能移动一位。所以希尔排序先划分小块分别插入排序，然后再总体插入排序。

那么选取H，即间隔就很重要了，这里有两篇文章

希尔排序 - OI Wiki
希尔排序 - 维基百科，自由的百科全书

都提到了比较好的H选择，因为Sedgewick步长有点不好写，这里直接就用原作者的排序

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
bool shellSort(int arr[], const int len) {
	std::deque<int> gap = {};
	auto gapinit = [&gap](int len, auto function)
		{
			for (int i = 0;; i++) {
				int x = function(i);
				if (x > len)
					break;
				gap.insert(gap.begin(), x);
			}
		};
	auto sort = [](int arr[], int gap, const int len) {
		for (int i = gap; i < len; i++)
		{
			int j = i;
			auto tmp = arr[i];//防止j=i时arr[i]被修改
			while (j - gap > 0 && arr[j - gap] > tmp) {
				arr[j] = arr[j - gap];
				j -= gap;
			}
			arr[j] = tmp;
		}
		return 0;
		};
	gapinit(len, [](int i) {
		return (int)pow(2, i);
		});
	for (auto g : gap)
	{
		sort(arr, g, len);
		pArr(arr, 20);
	}
	return true;
}
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
template <typename Container>
bool shellSort(Container& arr) {
	std::deque<int>gap = {};
	auto first = std::begin(arr);
	auto end = std::end(arr);
	auto len = std::distance(first, end);
	auto gapinit = [&gap](int len, std::function<int(int)> func)
		{
			for (int i = 0;; i++) {
				int x = func(i);
				if (x > len)
					break;
				gap.insert(gap.begin(), x);
			}
		};
	auto sort = [first, end](Container& container, int gap)
		{
			auto len = std::distance(first, end);
			for (int i = gap; i < len; ++i)
			{
				auto tmp = (*(first + i));
				int j;
				for (j = i; j >= gap && *(first + j - gap) > tmp; j -= gap)
				{
					*(first + j) = *(first + j - gap);
				}
				*(first + j) = (tmp);
			}
		};
	gapinit(len, [](int i) {
		return std::pow(2, i);
		});
	for (auto g : gap) {
		sort(arr, g);
		pArr(arr);
	}
	return true;
}

时间测试

1
2
Average time for 10000 runs and 1000 elements: 0.00008865 seconds
Total time:0.88646020

可以看出，速度相较之前的两个提升了5倍不止。

对于希尔算法的时间复杂度，需要额外考虑gap的值，不同的值对应不同的复杂度，比如说增量为2的倍数，那么同一个组中2的倍数会多次比较，改成pow(3,i)后

1
2
Average time for 10000 runs and 1000 elements: 0.00007897 seconds
Total time:0.78967320

很稳定地提高了大约0.1s。所以只能说大致来看时间复杂度在$O(nlog(n))$，对于以2的平方为间隔的，在完全倒序的情况下最差会退化到$O(n^2)$。查资料的时候发现，这是世界上第一个突破$O(n^2)$的排序算法，真强。
对于空间复杂度，由于额外占用一个tmp，所以为$O(1)$

交换排序

交换排序是指这一次排序的元素与其它元素交换最后实现的排序

冒泡排序

稳定的排序

经典老熟人，就不多说了，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool bubbleSort(int arr[], const int len) {
	for (int j = len; j > 0; j--)
	{
		bool sorted = true;
		for (int i = 0; i < j - 1; i++)
		{
			if (arr[i] > arr[i + 1]) {
				sorted = false;
				std::swap(arr[i], arr[i + 1]);
			}
		}
		//pArr(arr, 20);
		if (sorted)
			break;
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename Container>
bool bubbleSort(Container& container) {
	bool sorted = false;
	for (auto end = std::end(container); !sorted && end != std::begin(container); --end) {
		sorted = true;
		for (auto it = std::begin(container); std::next(it) != end; ++it) {
			if (*it > *std::next(it)) {
				std::swap(*it, *std::next(it));
				sorted = false;
			}
		}
		pArr(container);
	}

	return true;
}

测试:

1
2
Average time for 10000 runs and 1000 elements: 0.00132296 seconds
Total time:13.22964510

很慢，可能只适合小数组，定死的两重循环让它只能在$O(n^2)$上，除了运气很好刚好有序，则只需$O(n)$

空间复杂度$O(1)$

快速排序

顾名思义，很快的排序。每次排序时，定义一个基准值（一般是开头元素或结尾元素）然后从左和右分别引出指针，基准远离的那个指针开始向中心移动，遇到小于基准值的就复制到离基准近的位置，然后近的指针移动找大于基准值的，复制到远离基准的指针位置，两个指针相遇后，将基准赋值到这里。然后分别对左边和右边执行这个操作。因此要使用递归。

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
44
45
bool quickSort(int arr[], const int len) {
	enum di {
		left,
		right
	};
	std::function<void(int, int)> sort;
	sort = [&arr, &sort](int is, int ie) {
		pArr(arr, 20);
		if (is == ie)
			return;
		if (is + 1 == ie) {
			if (arr[is] > arr[ie])
				std::swap(arr[is], arr[ie]);
			return;
		}
		di diriction = right;
		int ieb = ie;
		int isb = is;
		auto base = arr[is];
		while (is < ie) {
			if (diriction == right) {
				while (base <= arr[ie] && is < ie)
					ie--;
				arr[is] = arr[ie];
				diriction = left;
			}
			else {
				while (base > arr[is] && is < ie)
				{
					is++;
				}
				arr[ie] = arr[is];
				diriction = right;
			}
		}
		arr[is] = base;
		//std::cout << base << std::endl;
		if (is > isb)
			sort(isb, is - 1);
		if (is < ieb)
			sort(is + 1, ieb);
		};
	sort(0, len - 1);
	return true;
}

后面就不写模板了QAQ

1
2
Average time for 10000 runs and 1000 elements: 0.00006714 seconds
Total time:0.67141270

可以看出确实很快，比希尔又少了0.1s左右。由于每次是折半,所以速度是$O(nlog(n))$，对应的，由于有折半次的递归，所以空间复杂度是$O(logn)$

选择排序

简单选择排序

树形选择排序

堆排序

归并排序

基数排序

外部排序