掘金后端 ( ) • 2024-03-22 11:05

theme: channing-cyan

📋 前言

经典的各种排序大家都听过，但是相信各位铁汁都对各种排序的性能都很好奇，大家都有心中自己的看法今天来彻底对比一下谁究竟才是排序性能 TOP1 @TOC

一、排序算法有那些

在这里插入图片描述

1.1 测试排序竞选

上述就是我们全部的常见算法了，但是由于有些算法时间复杂度实在太高了排序上千万个数据的话实在是太慢了可能半个小时都排不完

所以咱们只选择那些大人那桌的数据来进行性能测试，至于冒泡选择这些排序还是让他们去小孩那桌去喝哇哈哈吧！

在这里插入图片描述

1.1 最终参选选手：

希尔排序
堆排序
快速排序
归并排序
计数排序

二、测试方案

2.1 随机数测试

本次我们采用 rand( ) 来自动生成随机数来进行生成数据进行排序但是 ==rand () 函数最多只能生成 3万个随机数我也我们进行+i 来增加数据的随机性==。

本次测试使用1000万个数据来对比

🍸 代码演示：

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 10000000;
	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);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand()+i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];

	}

	//int begin1 = clock();
	//InsertSort(a1, N);
	//int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	//int begin3 = clock();
	//SelectSort(a3, N);
	//int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	CountSort(a7, N);
	int end7 = clock();

	//printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	//printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("CountSort:%d\n", end7 - begin7);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

📑 代码结果： 在这里插入图片描述

从这里就可以看到在排整数数据的排序来看计数排序是非常占优势的，直接拿下TOP1的排序性能排名我们的老大哥快排紧随其后

总体而言在当前1000万个较为不重复数据中：

计数排序 > 快速排序 > 希尔排序 > 堆排序 > 归并排序

🔥 ==注：当然这代表的并不绝对，希尔排序不一定比堆排差因为1000万个数据而rand就算+i 避免了一些重复数据，但还是有很多。==

2.2 重复值较为多的随机数测试

本次测试使用1000万个数据来对比，并不进行加工去重

在这里插入图片描述

诶这里来看计数依旧遥遥领先, 继续做稳老大哥的位置而归并在重复值较多的情况下跑到了第二

总体而言在当前1000万个重复数据较多的排序中：

计数排序 > 归并排序 > 快速排序 > 希尔排序 > 堆排序

三、排序稳定性对比

说到稳定性对比很多铁汁可能以为是排序性能在各种场景的波动的性能稳定性大不不大但其实排序的稳定性其实不是这样算下面就来看看排序的稳定性到底是怎么算的吧

3.1 什么是排序稳定性

排序的稳定性是指在排完序后相同数据的顺序不变这才能确定一个排序是否稳定。

假设你是对考试比赛成绩来进行排序，但是同一分数内考生提交的时间不一样这就需要我们使用排序稳定的算法来进行排序了

如果使用不稳定的排序那么考试顺不就全乱了这是绝对不能犯的错误

3.2 排序的稳定的有那些

冒泡排序

冒泡排序的思想是俩俩比较然后才进行交换但是如果数据一样的话肯定就不会进行交换这样相同数据的先后顺序就不会发生改变了

直接插入排序

直接插入排序也是当新数据来的时候如果和前一个数据一模一样的话那么就直接在其后面进行插入所以也不会打乱相同数据的先后顺序

归并排序

归并排序我们可以将其相同数据比较的时候优先归并前一个数据这样也不会打乱相同数据的先后顺序。

这样可以改变稳定性的排序都是稳定的

3.3 那些排序为什么不稳定

希尔排序

由于希尔排序是分租来进行排序的所以相同数据可能分成很多不同的组会打乱其相同数据的排序顺序所以是不稳定的

预排序的时候会分到不同的组所以不稳定

在这里插入图片描述

堆排序

堆排序是每次和子节点进行比较交换而当左右节点的数据一样的时候并不能确保先向下调整哪一个所以其稳定性也是不稳定的

快速排序

快速排序每次都会把前一个数据交换到中间或者其他地方所以他的性能也是不稳定的

在这里插入图片描述

计数排序

计数排序只能排序整形，而显示生活中对一些事务的排序往往需要排多种数据结构所以不能对其比较稳定性

四、排序性能总结表

在这里插入图片描述