排序速度对比程序v2.0（自取）
2026-08-23 11:53:10
发布于：浙江
85阅读
0回复
0点赞
- 可以看到这里加了好多空格，为什么呢，不要问，问就是在 Dev-C++ 里面 Ctrl+Shift+A。
- 我也是难得写了那——么长的变量名，是为了所谓的“可读性”，但写长了似乎也不那么“可读”。
- 排序数据量的阈值是我自己在比较新的电脑上测试的，没加 -O2，不同的电脑速度阈值可能不一样，可以自己更改。
- 为了🥫，👍🏻+💬！
- 较v1.0增加了堆排序，并增大了随机数最大值。
- 测试数据量要量力而行，数据量太大容易卡崩老电脑。
换新电脑了，旧的呢？被jcx106的排序速度对比程序卡崩了！
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long nosst = 7; //目前支持的排序种类数
string tnotsa[] = {"", "冒泡排序", "选择排序", "插入排序", "折半插入排序", "希尔排序", "快速排序", "堆排序"}; //排序名
long long noae; //需要排序的数组元素个数
long long maxa; //数组的最大元素
vector<long long> atbs; //需要排序的数组
vector<long long> batbs; //对需要排序的数组进行的备份
bool check(vector<long long>& arr, long long noa) {
for (long long i = 2; i <= noa; i++)
if (arr[i] < arr[i - 1])
return 0;
return 1;
}
//---------------------------------------------------------------------------------
void checkI(vector<long long>& arr, long long noa) {
bool flag = check(arr, noa);
if (!flag) {
cout << "但是排序后的数组不正确，这说明 jcx106 写的代码出了 bug，请在 ACGO 私信联系。\n";
} else {
cout << "并且排序后的数组正确。\n";
}
}
//---------------------------------------------------------------------------------
void backup() {
for (long long i = 1; i <= noae; i++)
batbs[i] = atbs[i];
}
//---------------------------------------------------------------------------------
void BubbleSort(vector<long long>& arr, long long noa) {
for (long long i = 1; i <= noa; i++) {
bool flag = 0;
for (long long j = 2; j <= noa - i + 1; j++)
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
flag = 1;
}
if (!flag)
return;
}
}
//---------------------------------------------------------------------------------
void SelectionSort(vector<long long>& arr, long long noa) {
for (long long i = 1; i <= noa; i++) {
long long mi = 1e18, k = -1;
for (long long j = i; j <= noa; j++)
if (arr[j] < mi) {
mi = arr[j];
k = j;
}
swap(arr[i], arr[k]);
}
}
//---------------------------------------------------------------------------------
void InsertSort(vector<long long>& arr, long long noa) {
for (long long i = 2; i <= noa; i++) {
long long temp = arr[i];
long long j = i - 1;
while (j > 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
//---------------------------------------------------------------------------------
void BinaryInsertSort(vector<long long>& arr, long long noa) {
for (long long i = 2; i <= noa; i++) {
long long temp = arr[i];
long long l = 1, r = i - 1;
while (l <= r) {
long long mid = (l + r) / 2;
if (temp < arr[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
for (long long j = i - 1; j >= l; j--) {
arr[j + 1] = arr[j];
}
arr[l] = temp;
}
}
//---------------------------------------------------------------------------------
void ShellSort(vector<long long>& arr, long long noa) {
for (long long d = noa / 2; d >= 1; d /= 2) {
for (long long i = d + 1; i <= noa; i++) {
long long temp = arr[i];
long long j = i - d;
while (j > 0 && arr[j] > temp) {
arr[j + d] = arr[j];
j -= d;
}
arr[j + d] = temp;
}
}
}
//---------------------------------------------------------------------------------
void QuickSort_Left_Right(vector<long long>& arr, long long l, long long r) {
if (l >= r)
return;
long long mid = (l + r) >> 1, i = l, j = r, k = arr[mid];
while (i <= j) {
while (arr[i] < k) i++;
while (arr[j] > k) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++, j--;
}
}
QuickSort_Left_Right(arr, l, j);
QuickSort_Left_Right(arr, i, r);
}
void QuickSort(vector<long long>& arr, long long noa) {
QuickSort_Left_Right(arr, 1, noa);
}
//---------------------------------------------------------------------------------
void DownAdjust(vector<long long>& arr, long long k, long long n) {
long long i = k, j = (i << 1);
while (j <= n) {
if (j + 1 <= n && arr[j + 1] > arr[j])
j++;
if (arr[i] < arr[j]) {
swap(arr[i], arr[j]);
i = j;
j = (i << 1);
} else
break;
}
}
void HeapSort(vector<long long>& arr, long long noa) {
for (long long i = (noa >> 1); i >= 1; i--)
DownAdjust(arr, i, noa);
for (long long i = noa; i >= 2; i--) {
swap(arr[1], arr[i]);
DownAdjust(arr, 1, i - 1);
}
}
//---------------------------------------------------------------------------------
void csa(long long op) {
cout << "用" << tnotsa[op] << "进行排序的总时间为：";
clock_t clock1 = clock();
if (op == 1) {
if (noae > 90000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
BubbleSort(batbs, noae);
} else if (op == 2) {
if (noae > 300000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
SelectionSort(batbs, noae);
} else if (op == 3) {
if (noae > 430000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
InsertSort(batbs, noae);
} else if (op == 4) {
if (noae > 500000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
BinaryInsertSort(batbs, noae);
} else if (op == 5) {
if (noae > 50000000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
ShellSort(batbs, noae);
} else if (op == 6) {
if (noae > 180000000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
QuickSort(batbs, noae);
} else if (op == 7) {
if (noae > 40000000) {
cout << "预计使用时间 >10000 毫秒，不再测试。\n";
return;
}
HeapSort(batbs, noae);
}
clock_t clock2 = clock();
cout << double(clock2 - clock1) / CLOCKS_PER_SEC * 1000.0 << " 毫秒，";
checkI(batbs, noae);
}
//---------------------------------------------------------------------------------
long long rnd() {
long long a = rand() % 32768;// 防非Windows系统
long long b = rand() % 32768;// 防非Windows系统
return a * 32768 + b;
}
//---------------------------------------------------------------------------------
int main() {
cout << "请输入数组元素数量：";
cin >> noae;
cout << "请输入数组元素最大值：";
cin >> maxa;
atbs.resize(noae + 1);
batbs.resize(noae + 1);
srand((unsigned)time(0));
for (long long i = 1; i <= noae; i++)
atbs[i] = rnd() % (maxa + 1);
for (long long i = 1; i <= nosst; i++) {
backup();
csa(i);
}
}
或许这也可以作为排序题模版使用？
全部评论 8
不敢@AC君
不敢@cjdst
不敢@wcqk
不敢@🥥
不敢@Stars_Seeker 🎖️
2026-08-22 来自 浙江
0
请输入数组元素数量：30000
请输入数组元素最大值（不超过32767）：30000
用冒泡排序进行排序的总时间为：3211 毫秒，并且排序后的数组正确。
用选择排序进行排序的总时间为：578 毫秒，并且排序后的数组正确。
用插入排序进行排序的总时间为：709 毫秒，并且排序后的数组正确。
用折半插入排序进行排序的总时间为：483 毫秒，并且排序后的数组正确。
用希尔排序进行排序的总时间为：7 毫秒，并且排序后的数组正确。
用快速排序进行排序的总时间为：5 毫秒，并且排序后的数组正确。
用堆排序进行排序的总时间为：8 毫秒，并且排序后的数组正确。2026-08-22 来自 天津
1请输入数组元素数量：89999
请输入数组元素最大值（不超过32767）：32767
用冒泡排序进行排序的总时间为：38952 毫秒，并且排序后的数组正确。
用选择排序进行排序的总时间为：7830 毫秒，并且排序后的数组正确。
用插入排序进行排序的总时间为：13723 毫秒，并且排序后的数组正确。
用折半插入排序进行排序的总时间为：6590 毫秒，并且排序后的数组正确。
用希尔排序进行排序的总时间为：34 毫秒，并且排序后的数组正确。
用快速排序进行排序的总时间为：14 毫秒，并且排序后的数组正确。
用堆排序进行排序的总时间为：34 毫秒，并且排序后的数组正确。2026-08-22 来自 天津
0
有帮助，赞一个