【排序】对各种排序的总结

---

?
?
?

前言

---

本篇是基于我这几篇博客做的一个总结：

1. 《简单排序》（含：冒泡排序，直接插入排序，选择排序，计数排序）
2. 《希尔排序》
3. 《堆排序》
4. 《快速排序》
5. 《归并排序》

我会再对他们的时间复杂度、空间复杂度以及稳定性再做一次总结，并且在不同的场景下，测试他们的性能怎么样。

?
?

1. 排序算法的复杂度及稳定性分析

---

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O$($N$2)	$O$($N$)	$O$($N$2)	$O$($1$)	稳定
选择排序	$O$($N$2)	$O$($N$2)	$O$($N$2)	$O$($1$)	不稳定
直接插入排序	$O$($N$2)	$O$($N$)	$O$($N$2)	$O$($1$)	稳定
计数排序	$O$($N+range$)	$O$($N$)	$O$($N+range$)	$O$($range$)	—
希尔排序	$O$($N?logN$) ~ $O$($N$2)	$O$($N$1.3)	$O$($N$2)	$O$($1$)	不稳定
堆排序	$O$($N?logN$)	$O$($N?logN$)	$O$($N?logN$)	$O$($1$)	不稳定
归并排序	$O$($N?logN$)	$O$($N?logN$)	$O$($N?logN$)	$O$($N$)	稳定
快速排序	$O$($N?logN$)	$O$($N?logN$)	$O$($N$2)	$O$($logN$) ~ $O$($N$)	不稳定

?
?

2. 排序算法的性能测试

---

??：我这里只是测试一遍的结果截图，目的是让大家看看，判断一个排序的优劣需要不同场景下的大量测试。

我们比较排序时，应该换成release版本来测试，这样性能才会全部拉满

先写一段测试代码

// 测试排序的性能对比
// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;     // 十万个数的比较
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand() + i; // 生成十万个重复率低的随机值
		//a1[i] = rand() % 100; // 生成十万个重复率高的随机值
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	SelectSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	ShellSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	int begin7 = clock();
	QuickSortNonR(a7, 0, N);
	int end7 = clock();
	int begin8 = clock();
	MergeSortNonR(a8, N);
	int end8 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("SelectSort:%d\n", end2 - begin2);
	printf("ShellSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("QuickSortNonR:%d\n", end7 - begin7);
	printf("MergeSortNonR:%d\n", end8 - begin8);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

int main()
{
	srand((unsigned)time(NULL)); // 生成随机数种子

	TestOP();

	return 0;
}

2.1 重复率较低的随机值排序测试

可以看到，直接插入排序在比较低阶的排序算法中，算是很优秀的一个排序了。

我们继续加大数据，但是我得把效率比较低的排序关掉，单独来比那些比较高阶的排序：

?

2.2 重复率较高的随机值排序测试

直接看结果：

继续加大数据，把效率比较低的排序关掉，单独来比那些比较高阶的排序：