排序速度对比程序v2.0（自取）

userId_undefined
jcx106
倔强青铜时间刺客空间掌握者分支·分支解题者模拟·模拟练习生循环·循环打卡人

2026-08-23 11:53:10

发布于：浙江

78阅读
0回复
0点赞
  1. 可以看到这里加了好多空格，为什么呢，不要问，问就是在 Dev-C++ 里面 Ctrl+Shift+A。
  2. 我也是难得写了那——么长的变量名，是为了所谓的“可读性”，但写长了似乎也不那么“可读”。
  3. 排序数据量的阈值是我自己在比较新的电脑上测试的，没加 -O2，不同的电脑速度阈值可能不一样，可以自己更改。
  4. 为了🥫，👍🏻+💬！
  5. 较v1.0增加了堆排序，并增大了随机数最大值。
  6. 测试数据量要量力而行，数据量太大容易卡崩老电脑。换新电脑了，旧的呢？被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);
	}
}

或许这也可以作为排序题模版使用？

userId_undefined
去预览
0/2000

全部评论 8

热门讨论