Register_int @ 2021-12-21 19:32:13
rt,数据统一随机打乱，储存采用vector。
by UnyieldingTrilobite @ 2021-12-21 19:35:06
给个代码？
by rxjdasiwzl @ 2021-12-21 19:35:17
给个代码？
by Register_int @ 2021-12-21 19:36:14
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void quicksort(vector<int>& a, int l, int r) {
if (l >= r) return;
int i(l), j(r), base(a[l]), t;
while (i < j) {
while (a[j] >= base && i < j) --j;
while (a[i] <= base && i < j) ++i;
if (i < j) {
a[i] ^= a[j] ^= a[i] ^= a[j];
}
}
a[l] = a[i], a[i] = base;
quicksort(a, l, i - 1), quicksort(a, i + 1, r);
}
void msort(vector<int>& a, vector<int>& t, int l, int r) {
if (l == r) return;
int mid(l + r >> 1);
msort(a, t, l, mid), msort(a, t, mid + 1, r);
int i(l), j(mid + 1), k(l);
while (i <= mid && j <= r) t[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) t[k++] = a[i++];
while (j <= r) t[k++] = a[j++];
for (register int i(l); i <= r; ++i) a[i] = t[i];
}
void mergesort(vector<int>& a, int l, int r) {
vector<int> t;
t.resize(r);
msort(a, t, l, r);
}
void combsort(vector<int>& a, int l, int r) {
int step(r - l);
double add = 1 / 1.3;
while ((step = int(step * add)) >= 1) {
for (register int i(0), j(step); j <= r; ++i, ++j) {
if (a[i] > a[j]) a[i] ^= a[j] ^= a[i] ^= a[j];
}
}
}
void shellsort(vector<int>& a, int l, int r) {
int num = 0, gap = (r + 1) / 3;
while (gap) {
for (register int i(gap); i <= r; ++i) {
num = a[i];
register int j = i;
while (j >= gap && num < a[j - gap]) a[j] = a[j -= gap];
a[j] = num;
}
gap = gap / 3;
}
}
void stdsort(vector<int>& a, int l, int r) {
sort(a.begin(), a.end());
}
void stdstablesort(vector<int>& a, int l, int r) {
stable_sort(a.begin(), a.end());
}
inline double GetUsedTime(void (*f)(vector<int>&, int, int), const int n) {
vector<int> a;
for (register int i(0); i < n; ++i) a.push_back(i);
random_shuffle(a.begin(), a.end());
auto st = chrono::system_clock::now();
f(a, 0, n - 1);
auto ed = chrono::system_clock::now();
//for (register i(0); i < n; ++i) printf("%d ", a[i]);
chrono::duration<double> time = ed - st;
return time.count();
}
int main() {
srand(time(0));
puts("numbers: 1e4");
printf("quicksort\t\tis used %.7lfs.\n", GetUsedTime(quicksort, 1e4));
printf("mergesort\t\tis used %.7lfs.\n", GetUsedTime(mergesort, 1e4));
printf("combsort\t\tis used %.7lfs.\n", GetUsedTime(combsort, 1e4));
printf("shellsort\t\tis used %.7lfs.\n", GetUsedTime(shellsort, 1e4));
printf("std::sort\t\tis used %.7lfs.\n", GetUsedTime(stdsort, 1e4));
printf("std::stable sort\tis used %.7lfs.\n", GetUsedTime(stdstablesort, 1e4));
puts("numbers: 1e6");
printf("quicksort\t\tis used %.7lfs.\n", GetUsedTime(quicksort, 1e6));
printf("mergesort\t\tis used %.7lfs.\n", GetUsedTime(mergesort, 1e6));
printf("combsort\t\tis used %.7lfs.\n", GetUsedTime(combsort, 1e6));
printf("shellsort\t\tis used %.7lfs.\n", GetUsedTime(shellsort, 1e6));
printf("std::sort\t\tis used %.7lfs.\n", GetUsedTime(stdsort, 1e6));
printf("std::stable sort\tis used %.7lfs.\n", GetUsedTime(stdstablesort, 1e6));
puts("numbers: 1e7");
printf("quicksort\t\tis used %.7lfs.\n", GetUsedTime(quicksort, 1e7));
printf("mergesort\t\tis used %.7lfs.\n", GetUsedTime(mergesort, 1e7));
printf("combsort\t\tis used %.7lfs.\n", GetUsedTime(combsort, 1e7));
printf("shellsort\t\tis used %.7lfs.\n", GetUsedTime(shellsort, 1e7));
printf("std::sort\t\tis used %.7lfs.\n", GetUsedTime(stdsort, 1e7));
printf("std::stable sort\tis used %.7lfs.\n", GetUsedTime(stdstablesort, 1e7));
puts("numbers: 1.1e8");
printf("quicksort\t\tis used %.7lfs.\n", GetUsedTime(quicksort, 1.1e8));
printf("mergesort\t\tis used %.7lfs.\n", GetUsedTime(mergesort, 1.1e8));
printf("combsort\t\tis used %.7lfs.\n", GetUsedTime(combsort, 1.1e8));
printf("shellsort\t\tis used %.7lfs.\n", GetUsedTime(shellsort, 1.1e8));
printf("std::sort\t\tis used %.7lfs.\n", GetUsedTime(stdsort, 1.1e8));
printf("std::stable sort\tis used %.7lfs.\n", GetUsedTime(stdstablesort, 1.1e8));
}by Register_int @ 2021-12-21 19:45:24
所以我要不要交到学术版（
by UCanHexAKing @ 2021-12-21 19:46:09
STL 开不开 O2 速度真的有天壤之别
建议开了试试
by rxjdasiwzl @ 2021-12-21 19:46:30
@const_int 无法复现。
by rxjdasiwzl @ 2021-12-21 19:46:47
numbers: 1e4
quicksort is used 0.0004867s.
mergesort is used 0.0006596s.
combsort is used 0.0005938s.
shellsort is used 0.0007623s.
std::sort is used 0.0005195s.
std::stable sort is used 0.0005690s.
numbers: 1e6
quicksort is used 0.0748660s.
mergesort is used 0.1000717s.
combsort is used 0.0930059s.
shellsort is used 0.1358223s.
std::sort is used 0.0601295s.
std::stable sort is used 0.0676055s.
numbers: 1e7
quicksort is used 0.7870125s.
mergesort is used 1.1342612s.
combsort is used 1.1655668s.
shellsort is used 2.5701798s.
std::sort is used 0.6921147s.
std::stable sort is used 0.8089213s.
numbers: 1.1e8
quicksort is used 9.5174215s.
mergesort is used 14.5988685s.
combsort is used 14.8207961s.
shellsort is used 67.3008008s.
std::sort is used 8.3332881s.
std::stable sort is used 10.0402136s.by rxjdasiwzl @ 2021-12-21 19:47:19
我不知道快排哪里慢了。
by UCanHexAKing @ 2021-12-21 19:48:21
在你谷 ide 上 C++14 GCC9 O2 环境下 std::sort 的优势还是很明显的
by rxjdasiwzl @ 2021-12-21 19:49:36
@ClHg2 他问的应该是自己的快排？