| 各种排序算法耗时比较 | 您所在的位置：网站首页 › 堆排序和快排哪个好 › 各种排序算法耗时比较 |
各种排序算法耗时比较
|
我们知道，各个排序算法的时间复杂度从快速排序的nlogn到冒泡的n^2，但是即使时间复杂度相同，其具体的耗时也是不同的。今天就来实地测测每种算法到底耗时如何 一号选手：冒泡排序。我们知道冒泡排序算的上是最慢的一种排序方法了 #include #include #include #include //笔者自定义的一个头文件，如果各位想自己实践一下，别忘了把这个头文件删除改成自己的头文件 #include #include //交换两个数 void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } //冒泡排序 void bubbleSort(int *arr, int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { //如果前面的数比后面大，进行交换 if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); } } } return; } void main() { int i = 0，j = 0; clock_t start, finish; //用来计时的结构体 double duration; int arr[100000]; srand((unsigned)time(NULL)); //随机播种 for (i = 0; i < 100000; i++) { arr[i] = rand() % 100000; //产生十万个0-10000的随机数 } start = clock(); bubbleSort(arr, 1000); //先进行1000个数字的排序，后面再依次增加 finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf("冒泡排序耗时：%f seconds\n", duration); }
进行了十次统计，平均下来0.007秒。因为数字太少，所以可能偏差有点大。 由统计了2000个数字的排序，结果是0.03秒。 3000个数字是0.07秒。 4000个数字，0.125秒。 10000个数字，0.84秒 20000个数字，3.45秒 可以看出，冒泡排序的时间复杂度确实比较高， 令A=t/(n^2),t取值为实际耗时的100倍，n取数字个数的一千分之一。可以算出A=0.778,0.781,0.84,0.86. 可以看出，A基本上随着n^2保持平稳，时间复杂度为O(n^2)。
二号选手，希尔排序 代码就不贴了，可以看之前的博客代码。这里只展示实际测试的耗时 1000：0.005秒 2000 : 0.019秒 4000 : 0.078秒 10000 : 0.445秒 20000 ： 1.76秒 可以看出，希尔排序耗时比冒泡排序要少不少。计算A，分别为0.5,0.47,0.486，0.445,0.44 时间复杂度仍然是O(n^2)，但是耗时要比冒泡少不少
三号选手：堆排序 堆排序是一种时间复杂度比较低的排序方法，平均下来是O(nlogn)，我们来看看具体的表现 1000:0秒....太快了 2000:0.001秒 4000:0.003秒 8000:0.007秒 16000:0.013秒 32000:0.03秒 堆排序确实比前两个优秀很多。也可以想到高数里面的logx的增长速度要比x慢很多很多。。。修改A的表达式 令A=t/(nlogn)，第一个就不计算了。。。。分别计算A=0.5,0.375,0.3,0.203.0.468 比较奇怪的是A竟然不稳定了。。。可能的因素是耗时太短，我们的计时手段可能精度不够。我自己又测了更多组的数据，A的值还是挺稳定的。。。看来10次误差还是不小。时间复杂度为O(nlogn)。
重量级选手：快速排序 为什么说是重量级呢，因为堆排序的表现已经挺好了，但是一山更比一山高，快速排序不愧于这个名字，真的很快。。。 20000个数字排序耗时才0.03秒，而且非常稳定。十次数据九次都是0.03.。。。 这个就不贴数据了，耗时太短，误差比较大。通过“严密的数学分析”可以得出时间复杂度为O(nlogn)。
通过这次实验，可以得出一个基本结论，快速排序>堆排序>>希尔排序>冒泡排序。也可以看出即使时间复杂度相同，其最终结果也相差很大。纠正了我的一个误区，以前总是以为时间复杂度相同，耗时应该是差不多的，打脸了~ 所以，快速排序一个程序员一定要掌握的算法，很优秀。 |
【本文地址】