【C++板块提升计划】12种排序方法大比拼【原创】
本帖最后由 zhangjinxuan 于 2022-11-12 11:21 编辑本贴一共收集了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 > a) {
swap(a, a);
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 < a)
min = j;
swap(a, a);
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;
int j = i - 1;
for ( ; j >= 0; j--) {
if (temp < a) a = a;
else break;
}
a = 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);
for (int i = 0; i < len; i++) {
a = 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 < a)
{
temp = a;
for (j = i - d; j >= 0&& temp < a; j -= d) a = a;
a = 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;
int maxnum = -1 << 30, w = 0;
for (int i = 0; i < len; ++i) maxnum = max(maxnum, a);
while (maxnum) {
maxnum /= 10;
w++;
}
for (int i = 1; i <= w; ++i) {
int cnt = {};
for (int j = 0; j < len; ++j)
cnt, i)]++;
for (int i = 1; i < 10; ++i)cnt += cnt;
for (int j = len - 1; j >= 0; --j)
tmp[--cnt, i)]] = a;
for (int i = 0; i < len; ++i)
a = tmp;
}
}
测试结果：
数组长度 |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, max = a;
for (int i = 1;i < len; i++) {
if (a < min) min = a;
if (a > max) max = a;
}
unordered_map<int, int> c;
c.clear();
for (int i = 0; i < len; i++)c]++;
for (int i = min, k = 0; i <= max; i++)
for (int j = 0; j < c; c--)
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;
while (i <= j) {
while (a < t) i++;
while (a > t) j--;
if (i <= j) swap(a, a);
}
_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;
while (l1 <= r1 && l2 <= r2)
res = a > a ? a : a;
while (l1 <= r1) res = a;
while (l2 <= r2) res = a;
for (int i = l, p = 0; i <= r; ++i, ++p) a = res;
}
}
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, top;
void ncqsort(int * a, int r) {//非递归快排
top = 0;
st[++top] = 0;
st = r;
while (top) {
int l = st, r = st;
if (l >= r) continue;
int t = a, i = l, j = r;
while (i <= j) {
while (i <= j && a < t) ++i;
while (i <= j && a > t) --j;
if (i <= j) swap(a, a);
}
st[++top] = l, st = j;
st[++top] = i, st = r;
}
}
测试结果：
数组长度 |10w| 30w|1b |2b|3b |5b
排序时间(ms)|9|31 |109 |228 |349|608
太厉害了，十分推荐！！！
好了，本章到此结束，如果大家还有什么更高效的排序，欢迎留言哦~
整理不易，求评分~ sort排序是优化后的快排，避免了快排的最差效果 嘉岳呀 发表于 2022-11-12 11:59
sort排序是优化后的快排，避免了快排的最差效果
我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排 zhangjinxuan 发表于 2022-11-12 12:01
我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排
我也听说过... 本帖最后由 高山 于 2022-11-12 16:15 编辑
不错啊，顶
帖子写的很详细哦，已经作了一番顶的猛操作 求支持{:10_254:}@柿子饼同学 @不二如是 @陈尚涵 @zhangjinxuan 排序的时间是怎么测试的？{:10_281:} 嘉岳呀 发表于 2022-11-12 19:43
@zhangjinxuan 排序的时间是怎么测试的？
排序前记录当前时间，排序后记录当前时间，下一步自己想一想{:5_109:} 据我所知，无论是 std::sort 还是 qsort 都没有被在标准中定义或规定为使用快速排序实现，只说明了它们的效果是“排序”
STL 是标准模板库， qsort 也似乎没有任何表明其有“模板”特质的迹象
另外还发现了一个小细节，标准中要求 qsort 可以是不稳定的，但 std::sort 是稳定的 好耶{:7_146:}
dolly_yos2 发表于 2022-11-12 21:37
据我所知，无论是 std::sort 还是 qsort 都没有被在标准中定义或规定为使用快速排序实现，只说明了它们的效 ...
好的，感谢提醒，今天太晚，明天再改{:10_256:} {:7_146:} 快排和冒泡是最常用的 陈尚涵 发表于 2022-11-13 13:37
快排和冒泡是最常用的
是的~ zhangjinxuan 发表于 2022-11-12 12:01
我听说sort在数据量小的时候用插排，中等用快排，数据量大的时候用堆排
为什么我的老师说sort就是快排
页:
[1]