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

zhangjinxuan

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

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

一、冒泡排序

void boubles(int * a, int len) { //冒泡
        for (int i = 0; i < len; i++){
                bool swaped = false;
                for (int j = 0; j < len - i - 1; j++) {
                        if (a[j] > a[j + 1]) {
                                swap(a[j], a[j + 1]);
                                swaped=true;
                        }
                }
                if (not swaped)return;
        }
}

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

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

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

二、选择排序

void selects(int *a, int len) { //选择
        int min = 0;
        for (int i = 0; i < len - 1; i++) {
                for (int j = i; j < len; j++) 
                        if (a[j] < a[min])
                                min = j;
                swap(a[min], a[i]);
                min = i + 1;
        }
}

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

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

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

三、插入排序

void inserts(int * a, int len) { //插排
         for (int i = 1; i < len; i++) {
                 int temp = a[i];
                 int j = i - 1;
                 for ( ; j >= 0; j--) {
                         if (temp < a[j]) a[j + 1] = a[j];
                         else break;
                }
                a[j + 1] = temp;
        }
}

测试结果：

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

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

四、借助STL的堆排序

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

测试结果：

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

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

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

五、希尔排序

void shells(int * a, int n) //希尔 
{
        int d, i, j, temp;
        for (d = n / 2; d >= 1; d = d / 2) {
                for (i = d; i < n; i++) {
                        if (a[i] < a[i - d])
                        {
                                temp = a[i];
                                 for (j = i - d; j >= 0&& temp < a[j]; j -= d) a[j + d] = a[j];
                                 a[j + d] = temp;
                         }
                }
        }
}

测试结果：

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

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

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

int getw(int num, int w) //基数排序专用 
{
        while (--w)
                num /= 10;
        return num % 10;
}
void rsort(int * a,int len) //基数排序
{
        static int tmp[maxs];
        int maxnum = -1 << 30, w = 0;
        for (int i = 0; i < len; ++i) maxnum = max(maxnum, a[i]);
        while (maxnum) {
                maxnum /= 10;
                w++;
        }
        for (int i = 1; i <= w; ++i) {
                int cnt[10] = {};
                for (int j = 0; j < len; ++j)
                        cnt[getw(a[j], i)]++;
                for (int i = 1; i < 10; ++i)cnt[i] += cnt[i - 1];
                for (int j = len - 1; j >= 0; --j)
                        tmp[--cnt[getw(a[j], i)]] = a[j];
                for (int i = 0; i < len; ++i)
                        a[i] = tmp[i];
        }
                
}

测试结果：

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

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

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

void counts(int * a, int len){ //计数
        int min = a[0], max = a[0];
        for (int i = 1;i < len; i++) {
                if (a[i] < min) min = a[i];
                if (a[i] > max) max = a[i];
        }
        unordered_map<int, int> c;
        c.clear();
        for (int i = 0; i < len; i++)c[a[i]]++;
        for (int i = min, k = 0; i <= max; i++)
                for (int j = 0; j < c[i]; c[i]--)
                        a[++k - 1] = i;        
}

测试结果：

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

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

八、stl之sort

sort(a, a + len)

测试结果：

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

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

九、快速排序

void _mqsort(int * a, int r, int l = 0) { //快排
        if (l >= r) return;
        int i = l, j = r, t = a[l];
        while (i <= j) {
                while (a[i] < t) i++;
                while (a[j] > t) j--;
                if (i <= j) swap(a[i++], a[j--]);
        }
        _mqsort(a,l,j);
        _mqsort(a,i,r);
}
void mqsort(int * a, int len) {
        _mqsort(a, len);
}

测试结果：

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

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

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

void _msort(int * a, int r, int l = 0) {//归并排序
        if (l < r) {
                int mid = (l + r) / 2;
                _msort(a, l, mid);
                _msort(a, mid + 1, r);
                int l1 = l, r1 = mid, l2 = mid + 1, r2 = r, m = 0;
                static int res[maxs];
                while (l1 <= r1 && l2 <= r2)
                        res[m++] = a[l1] > a[l2] ? a[l2++] : a[l1++];
                while (l1 <= r1) res[m++] = a[l1++];
                while (l2 <= r2) res[m++] = a[l2++];
                for (int i = l, p = 0; i <= r; ++i, ++p) a[i] = res[p];
        }
}
void msort(int * a, int len) {
        _msort(a, len);
}

测试结果：

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

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

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

int _qsf(const void * a, const void * b) {
        return (*(int*)a - *(int*)b);
}
void stlqsort(int * a, int len) {
        qsort(a, len, sizeof(int), _qsf);
}

测试结果：

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

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

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

int st[10000001][2], top;
void ncqsort(int * a, int r) {//非递归快排
        top = 0;
        st[++top][0] = 0;
        st[top][1] = r;
        while (top) {
            int l = st[top][0], r = st[top--][1];
            if (l >= r) continue;
            int t = a[l], i = l, j = r;
            while (i <= j) {
                while (i <= j && a[i] < t) ++i;
                while (i <= j && a[j] > t) --j;
                if (i <= j) swap(a[i++], a[j--]);
            }
                st[++top][0] = l, st[top][1] = j;
                st[++top][0] = i, st[top][1] = r;
        }
}

测试结果：

数组长度	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就是快排