Сортировка слиянием имеет наихудший вариант сложности O (logN) по сравнению с быстрой сортировкой с O (N ^ 2), поэтому теоретически сортировка слиянием должна работать лучше, чем быстрая сортировка.Но я слышал, что из-за некоторого количества копий в большинстве случаев быстрая сортировка превосходит сортировку слиянием. См. Ссылку .
Затем я решил реализовать и протестировать, ниже приведен мой полный исходный код на C,
Исходный код
#include <stdio.h>
#include <time.h>
#define SZ 10000000
#define MOD 10000007
#define i64 long long int
i64 nums[SZ];
i64 L[SZ], R[SZ];
i64 seed = 0xff;
i64 srand(){
seed = (seed + 17 * seed) % MOD;
return seed;
}
void make(){
for (register int i = 0; i < SZ; i++)
nums[i] = srand() % MOD;
}
void swap(i64 *a, i64 *b){
i64 t = *a;
*a = *b;
*b = t;
}
int pivote(int s, int e){
//int p = s + srand() % (e - s + 1);
int p = s + (e - s) / 2;
//int p = s;
//int p = e;
i64 v = nums[p];
int c = s;
swap(nums + p, nums + e);
for (register int i = s; i < e; i++){
if (nums[i] < v){
swap(nums + i, nums + c);
c++;
}
}
swap(nums + c, nums + e);
return c;
}
void qsort(int s, int e){
if (s < e){
int p = pivote(s, e);
qsort(s, p - 1);
qsort(p + 1, e);
}
}
void merge(i64 arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(i64 arr[], int l, int r){
if (l < r){
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void testQsort(){
double s, e;
make();
s = clock();
qsort(0, SZ - 1);
e = clock();
printf("qsort random: %Lf ms\n", (e - s) / 1);
s = clock();
qsort(0, SZ - 1);
e = clock();
printf("qsort sorted: %Lf ms\n", (e - s) / 1);
}
void testMsort(){
double s, e;
make();
s = clock();
mergeSort(nums, 0, SZ - 1);
e = clock();
printf("msort random: %Lf ms\n", (e - s) / 1);
s = clock();
mergeSort(nums, 0, SZ - 1);
e = clock();
printf("msort sorted: %Lf ms\n", (e - s) / 1);
}
int main(){
testMsort();
testQsort();
return 0;
}
Результатдля 10 миллионов элементов:
msort random: 4596.000000 ms
msort sorted: 3354.000000 ms
qsort random: 7637.000000 ms
qsort sorted: 5074.000000 ms
Я использовал четыре варианта быстрой сортировки,
- поворот на первой позиции
- поворот на последней позиции
- поворот в средней позиции
- поворот в случайной позиции
Кажется, что ни одна из версий быстрой сортировки не превосходит сортировку слиянием.Может кто-нибудь сказать, почему было упомянуто, что быстрая сортировка превосходит сортировку слиянием?
Есть ли что-то не так с моей реализацией быстрой сортировки?
Обновление 1
После ответа @rcgldrупомянутый ниже, я протестировал приведенную ниже версию быстрой сортировки, и она, наконец, превосходит любую версию сортировки слиянием.
void qsort3(int s, int e){
if (s < e){
i64 p = nums[(s + e) / 2];
int i = s - 1;
int j = e + 1;
while (true){
while (nums[++i] < p);
while (nums[--j] > p);
if (i >= j) break;
swap(nums + i, nums + j);
}
qsort3(s, j);
qsort3(j + 1, e);
}
}