[我在C ++中实现了合并排序和快速排序,我想使用两种情况下的执行时间,在很多情况下这些情况已经排序或没有排序,并且大小不同。
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;
void Merge(vector<int>& s, int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = low;
vector<int> u(s);
while (i <= mid && j <= high) {
if (s.at(i) < s.at(j)) {
u.at(k) = s.at(i);
i++;
} else {
u.at(k) = s.at(j);
j++;
}
k++;
}
if (i > mid) {
for (int a = j; a < high + 1; a++) {
u.at(k) = s.at(a);
k++;
}
} else {
for (int a = i; a < mid + 1; a++) {
u.at(k) = s.at(a);
k++;
}
}
for (int a = low; a < high + 1; a++)
s.at(a) = u.at(a);
}
void MergeSort(vector<int>& s, int low, int high) {
int mid;
if (low < high) {
mid = (low + high) / 2;
MergeSort(s, low, mid);
MergeSort(s, mid + 1, high);
Merge(s, low, mid, high);
}
}
void swap(int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}
void Partition(vector<int>& s, int low, int high, int& pvpoint) {
int j;
int pvitem;
pvitem = s.at(low);
j = low;
for (int i = low + 1; i <= high; i++) {
if (s.at(i) < pvitem) {
j++;
swap(s.at(i), s.at(j));
}
pvpoint = j;
swap(s.at(low), s.at(pvpoint));
}
}
void QuickSort(vector<int>& s, int low, int high) {
int pvpoint;
if (high > low) {
Partition(s, low, high, pvpoint);
QuickSort(s, low, pvpoint - 1);
QuickSort(s, pvpoint + 1, high);
}
}
int main() {
vector<int> CaseSize(20);
for (int i = 0; i < 10; i++) { //10 Arrays those are sorted
CaseSize.at(i) += (i + 1) * 500;
}
for (int i = 10; i < 20; i++) { //rest 10 those are not sorted
CaseSize.at(i) += (i + 1) * 5000;
}
cout << "------------------Sorted------------------\n\n";
cout << " Quick Sort Merge Sort\n";
for (int i = 0; i < 10; i++) {
vector<int> Arr(CaseSize.at(i));
Arr.front() = rand() % Arr.size();
for (int j = 1; j < Arr.size(); j++) {
Arr.at(j) = ((17 * Arr.at(j - 1) + 43) % (Arr.size() * 5));
}
vector<int> Arr2(Arr);
sort(Arr.begin(), Arr.end());
sort(Arr2.begin(), Arr2.end());
cout << "N : " << CaseSize.at(i) << " ";
clock_t start = (int)clock();
QuickSort(Arr, 0, Arr.size() - 1);
printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
cout << "\t\t";
clock_t start2 = (int)clock();
MergeSort(Arr2, 0, Arr2.size() - 1);
printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
cout << endl;
}
cout << endl;
cout << "------------------Random------------------\n\n";
cout << " Quick Sort Merge Sort\n";
for (int k = 10; k < 20; k++) {
vector<int> Arr(CaseSize.at(k));
Arr.front() = rand() % Arr.size();
for (int l = 1; l < Arr.size(); l++) {
Arr.at(l) = ((17 * Arr.at(l - 1) + 43) % (Arr.size() * 5));
}
vector<int> Arr2(Arr);
cout << "N : " << CaseSize.at(k) << " ";
clock_t start = (int)clock();
QuickSort(Arr, 0, Arr.size() - 1);
printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
cout << "\t\t";
clock_t start2 = (int)clock();
MergeSort(Arr2, 0, Arr2.size() - 1);
printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
cout << endl;
}
return 0;
}
嗯,该程序实际上可以工作,但是打印的执行时间与我期望的不一样。我没事吧?我想同时运行这两种算法以显示其执行时间,因此我可以用这种方式比较它们的[[TIME COMPLEXITY(尽可能不固定排序算法)。
Merge
在每个递归调用开始时复制整个数组,这是二次成本。在某些非常常见的情况下,快速排序实现在病理上也很慢:如果数组已经排序,则枢轴值始终是切片中的最小元素,因此递归深度是数组的长度,您可以得到二次时间如果不是堆栈溢出
。很难衡量这些低效率是否会最严重影响性能,但是我想MergeSort
是失败者。
printf("%0.5fms", (clock() - start) * 1000.0 / CLOCKS_PER_SEC);
要解决Merge
中的问题,请修改代码以创建正确大小的向量:
void Merge(vector<int>& s, int low, int mid, int high) {
int i = low;
int j = mid + 1;
int k = 0;
vector<int> u(high + 1 - low);
while (i <= mid && j <= high) {
if (s.at(i) < s.at(j)) {
u.at(k) = s.at(i);
i++;
} else {
u.at(k) = s.at(j);
j++;
}
k++;
}
if (i > mid) {
while (j <= high) {
u.at(k) = s.at(j);
j++;
k++;
}
} else {
while (i <= mid) {
u.at(k) = s.at(i);
i++;
k++;
}
}
for (i = low, k = 0; i <= high; i++, k++)
s.at(i) = u.at(k);
}