【C++板块提升计划】12种排序方法大比拼【原创】

zhangjinxuan

本贴一共收集了12种不同的排序算法，并且经行了对比，与总结，大家如果有更高效的排序，可以分享哦~

测评配置:
处理器：Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
内存：8GB
类型：64位, 基于x64的处理器

一、冒泡排序

1. void boubles(int * a, int len) { //冒泡
   
2.         for (int i = 0; i < len; i++){
   
3.                 bool swaped = false;
   
4.                 for (int j = 0; j < len - i - 1; j++) {
   
5.                         if (a[j] > a[j + 1]) {
   
6.                                 swap(a[j], a[j + 1]);
   
7.                                 swaped=true;
   
8.                         }
   
9.                 }
   
10.                 if (not swaped)return;
    
11.         }
    
12. }

复制代码

很简单，萌新也会，不过正是因为简单，而导致效率低，下面是测试结果：

数组长度	3千	1万	3万
排序时间(ms)	18	275	超时

只用于一些特殊题目，不推荐！

二、选择排序

1. void selects(int *a, int len) { //选择
   
2.         int min = 0;
   
3.         for (int i = 0; i < len - 1; i++) {
   
4.                 for (int j = i; j < len; j++)
   
5.                         if (a[j] < a[min])
   
6.                                 min = j;
   
7.                 swap(a[min], a[i]);
   
8.                 min = i + 1;
   
9.         }
   
10. }

复制代码

在冒泡排序上做了一点优化，使交换次数变少，下面是测试结果：

数组长度	3千	1万	3万
排序时间(ms)	11	129	超时

还行吧，不过3万就不行了，不推荐！

三、插入排序

1. void inserts(int * a, int len) { //插排
   
2.         for (int i = 1; i < len; i++) {
   
3.                 int temp = a[i];
   
4.                 int j = i - 1;
   
5.                 for ( ; j >= 0; j--) {
   
6.                         if (temp < a[j]) a[j + 1] = a[j];
   
7.                         else break;
   
8.                 }
   
9.                 a[j + 1] = temp;
   
10.         }
    
11. }

复制代码

测试结果：

数组长度	3千	1万	3万	10万
排序时间(ms)	6	73	632	超时

至少可以过3万了，但是10万这一个坎仍然过不去，只用于特殊题目，不推荐！

四、借助STL的堆排序

1. void dui(int *a, int len) {//堆排
   
2.         priority_queue<int, vector<int>, greater<int>> d;
   
3.         for (int i = 0; i < len; i++) d.push(a[i]);
   
4.         for (int i = 0; i < len; i++) {
   
5.                 a[i] = d.top();
   
6.                 d.pop();
   
7.         }
   
8. }

复制代码

测试结果：

数组长度	10万	30万	1百万	2百万
排序时间(ms)	77	259	956	超时

终于过10万了！及格了！而且代码有短，比较推荐^_^

不过，后面的排序，简直是小巫见大巫！

五、希尔排序

1. void shells(int * a, int n) //希尔
   
2. {
   
3.         int d, i, j, temp;
   
4.         for (d = n / 2; d >= 1; d = d / 2) {
   
5.                 for (i = d; i < n; i++) {
   
6.                         if (a[i] < a[i - d])
   
7.                         {
   
8.                                 temp = a[i];
   
9.                                  for (j = i - d; j >= 0&& temp < a[j]; j -= d) a[j + d] = a[j];
   
10.                                  a[j + d] = temp;
    
11.                          }
    
12.                 }
    
13.         }
    
14. }

复制代码

测试结果：

数组长度	10万	30万	1百万	2百万	3百万
排序时间(ms)	29	93	355	788	超时

这是插入排序的优化，效率挺快的~比较推荐！

六、基数排序
(a_i在十亿以内)

1. int getw(int num, int w) //基数排序专用
   
2. {
   
3.         while (--w)
   
4.                 num /= 10;
   
5.         return num % 10;
   
6. }
   
7. void rsort(int * a,int len) //基数排序
   
8. {
   
9.         static int tmp[maxs];
   
10.         int maxnum = -1 << 30, w = 0;
    
11.         for (int i = 0; i < len; ++i) maxnum = max(maxnum, a[i]);
    
12.         while (maxnum) {
    
13.                 maxnum /= 10;
    
14.                 w++;
    
15.         }
    
16.         for (int i = 1; i <= w; ++i) {
    
17.                 int cnt[10] = {};
    
18.                 for (int j = 0; j < len; ++j)
    
19.                         cnt[getw(a[j], i)]++;
    
20.                 for (int i = 1; i < 10; ++i)cnt[i] += cnt[i - 1];
    
21.                 for (int j = len - 1; j >= 0; --j)
    
22.                         tmp[--cnt[getw(a[j], i)]] = a[j];
    
23.                 for (int i = 0; i < len; ++i)
    
24.                         a[i] = tmp[i];
    
25.         }
    
26.                
    
27. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	31	93	312	622	931	超时

可以干掉大部分排序算法了，不过，a_i在十万以内可以发挥出更大的作用~
但是理解较难，对新手极不友好，不是很推荐，

七，计数排序
（a_i在10万以内）

1. void counts(int * a, int len){ //计数
   
2.         int min = a[0], max = a[0];
   
3.         for (int i = 1;i < len; i++) {
   
4.                 if (a[i] < min) min = a[i];
   
5.                 if (a[i] > max) max = a[i];
   
6.         }
   
7.         unordered_map<int, int> c;
   
8.         c.clear();
   
9.         for (int i = 0; i < len; i++)c[a[i]]++;
   
10.         for (int i = min, k = 0; i <= max; i++)
    
11.                 for (int j = 0; j < c[i]; c[i]--)
    
12.                         a[++k - 1] = i;       
    
13. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	19	60	208	412	620	超时

这里只是a_i较小的情况，较大的时候就歇菜了，不过理解很简单~

八、stl之sort

1. sort(a, a + len)

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	18	60	215	450	698	超时

还是可以的，非常适合懒人，推荐！

九、快速排序

1. void _mqsort(int * a, int r, int l = 0) { //快排
   
2.         if (l >= r) return;
   
3.         int i = l, j = r, t = a[l];
   
4.         while (i <= j) {
   
5.                 while (a[i] < t) i++;
   
6.                 while (a[j] > t) j--;
   
7.                 if (i <= j) swap(a[i++], a[j--]);
   
8.         }
   
9.         _mqsort(a,l,j);
   
10.         _mqsort(a,i,r);
    
11. }
    
12. void mqsort(int * a, int len) {
    
13.         _mqsort(a, len);
    
14. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	18	60	211	447	685	超时

大名鼎鼎的快速排序果然名副其实的快，不过还是过不去5百万这个坎，总体还是推荐~

十、归并排序（效率第三）

1. void _msort(int * a, int r, int l = 0) {//归并排序
   
2.         if (l < r) {
   
3.                 int mid = (l + r) / 2;
   
4.                 _msort(a, l, mid);
   
5.                 _msort(a, mid + 1, r);
   
6.                 int l1 = l, r1 = mid, l2 = mid + 1, r2 = r, m = 0;
   
7.                 static int res[maxs];
   
8.                 while (l1 <= r1 && l2 <= r2)
   
9.                         res[m++] = a[l1] > a[l2] ? a[l2++] : a[l1++];
   
10.                 while (l1 <= r1) res[m++] = a[l1++];
    
11.                 while (l2 <= r2) res[m++] = a[l2++];
    
12.                 for (int i = l, p = 0; i <= r; ++i, ++p) a[i] = res[p];
    
13.         }
    
14. }
    
15. void msort(int * a, int len) {
    
16.         _msort(a, len);
    
17. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	17	56	198	423	664	超时

挺意外的，居然比快速排序还要快~
既可以做较多的特殊题目，又可以非常快的排序，十分推荐~

十一、stl之快排（效率第二）

1. int _qsf(const void * a, const void * b) {
   
2.         return (*(int*)a - *(int*)b);
   
3. }
   
4. void stlqsort(int * a, int len) {
   
5.         qsort(a, len, sizeof(int), _qsf);
   
6. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	14	46	180	342	549	879

STLYYDS!
总算破了5百万大关，但是接下来这个排序，谁都要跪下拜神！！

十二、非递归快排（效率第一）

1. int st[10000001][2], top;
   
2. void ncqsort(int * a, int r) {//非递归快排
   
3.         top = 0;
   
4.         st[++top][0] = 0;
   
5.         st[top][1] = r;
   
6.         while (top) {
   
7.             int l = st[top][0], r = st[top--][1];
   
8.             if (l >= r) continue;
   
9.             int t = a[l], i = l, j = r;
   
10.             while (i <= j) {
    
11.                 while (i <= j && a[i] < t) ++i;
    
12.                 while (i <= j && a[j] > t) --j;
    
13.                 if (i <= j) swap(a[i++], a[j--]);
    
14.             }
    
15.                 st[++top][0] = l, st[top][1] = j;
    
16.                 st[++top][0] = i, st[top][1] = r;
    
17.         }
    
18. }

复制代码

测试结果：

数组长度	10w	30w	1b	2b	3b	5b
排序时间(ms)	9	31	109	228	349	608

太厉害了，十分推荐！！！



好了，本章到此结束，如果大家还有什么更高效的排序，欢迎留言哦~


整理不易，求评分~

嘉岳呀

sort排序是优化后的快排，避免了快排的最差效果

zhangjinxuan

嘉岳呀 发表于 2022-11-12 11:59
sort排序是优化后的快排，避免了快排的最差效果

我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排

嘉岳呀

zhangjinxuan 发表于 2022-11-12 12:01
我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排

我也听说过...

高山

不错啊，顶
帖子写的很详细哦，已经作了一番顶的猛操作

zhangjinxuan

求支持@柿子饼同学 @不二如是 @陈尚涵

嘉岳呀

@zhangjinxuan 排序的时间是怎么测试的？

zhangjinxuan

嘉岳呀 发表于 2022-11-12 19:43
@zhangjinxuan 排序的时间是怎么测试的？

排序前记录当前时间，排序后记录当前时间，下一步自己想一想

dolly_yos2

据我所知，无论是 std::sort 还是 qsort 都没有被在标准中定义或规定为使用快速排序实现，只说明了它们的效果是“排序”
STL 是标准模板库， qsort 也似乎没有任何表明其有“模板”特质的迹象
另外还发现了一个小细节，标准中要求 qsort 可以是不稳定的，但 std::sort 是稳定的

柿子饼同学

好耶

zhangjinxuan

dolly_yos2 发表于 2022-11-12 21:37
据我所知，无论是 std::sort 还是 qsort 都没有被在标准中定义或规定为使用快速排序实现，只说明了它们的效 ...

好的，感谢提醒，今天太晚，明天再改

123woshishui

陈尚涵

快排和冒泡是最常用的

zhangjinxuan

陈尚涵 发表于 2022-11-13 13:37
快排和冒泡是最常用的

是的~

陈尚涵

zhangjinxuan 发表于 2022-11-12 12:01
我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排

为什么我的老师说sort就是快排