jcx106的排序速度对比程序（自取）
2026-08-08 10:10:51
发布于：浙江
18阅读
0回复
0点赞
- 可以看到这里加了好多空格，为什么呢，不要问，问就是在 Dev-C++ 里面 Ctrl+Shift+A。
- 我也是难得写了那——么长的变量名，是为了所谓的“可读性”，但写长了似乎也不那么“可读”。
- 排序数据量的阈值是我自己在电脑上测试的，没加 -O2，不同的电脑速度阈值可能不一样，可以自己更改。
- 为了🥫，👍🏻+💬！
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long nosst = 6; //目前支持的排序种类数
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 (int 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 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);
}
clock_t clock2 = clock();
cout << double(clock2 - clock1) / CLOCKS_PER_SEC * 1000.0 << " 毫秒，";
checkI(batbs, noae);
}
int main() {
cout << "请输入数组元素数量：";
cin >> noae;
cout << "请输入数组元素最大值（不超过32767）：";
cin >> maxa;
atbs.resize(noae + 1);
batbs.resize(noae + 1);
srand((unsigned)time(0));
for (long long i = 1; i <= noae; i++)
atbs[i] = rand() % (maxa + 1);
for (long long i = 1; i <= nosst; i++) {
backup();
csa(i);
}
}
有帮助，赞一个