快速排序运行时速度问题

Question

我遇到麻烦的事情。我有一个快速排序算法的实现，但是当我在一个有30多个元素的整数数组上进行测试时，在我看来排序需要很长时间。有时甚至超过10秒，与选择排序，插入排序和冒泡排序不同，它们在10000个元素上比在100个元素上快速排序要快。

这里是我的解决方案，请给予建议:)

void kvikSort(int a[], int l, int d) { 
int i, k; 

if (l >= d) 
    return; 

k = l; 
swap(&a[l], &a[(l + d)/2]); 

for (i = l + 1; i <= d; i++) 
    if (a[i] < a[l]) 
     swap(&a[++k], &a[i]); 
swap(&a[l], &a[k]); 

kvikSort(a, 0, k-1); 
kvikSort(a, k+1, d); 

}

编辑：我使用GCC 4.7.2 v在我的Linux Mint的14，PROC：英特尔酷睿2 E7400

编辑：我的其他算法：

void selectionSort(int a[], int n) { 
int i, j, min; 

for (i = 0; i < n - 1; i++) { 
    min = i; 
    for (j = i + 1; j < n; j++) 
     if (a[j] < a[min]) 
      min = j; 
    if (min != i) 
     swap(&a[min], &a[i]); 
} 

}

void insertionSort(int a[], int n) { 
int i, j; 

for (i = 0; i < n - 1; i++) 
    for (j = i + 1; j > 0 && a[j] < a[j-1]; j--) 
     swap(&a[j], &a[j-1]); 

}

void bubbleSort(int a[], int n) { 
int i, j; 

for (i = n - 1; i > 0; i--) 
    for (j = 0; j < i; j++) 
     if (a[j] > a[j+1]) 
      swap(&a[j], &a[j+1]); 

}

void swap(int *i, int *j) { 
    int tmp; 

    tmp = *i; 
    *i = *j; 
    *j = tmp; 

}

编辑：也许我应该提到，在我的测试程序，我第一次outputing随机生成的阵列到一个文本文件，然后将数组排序到另一个文本文件。所以它肯定会运行缓慢，但这不是问题，问题是快速排序比其他问题慢得多。

Answer 1

这里的问题：

void kvikSort(int a[], int l, int d) { 
int i, k; 

if (l >= d) 
    return; 

k = l; 
swap(&a[l], &a[(l + d)/2]); 

for (i = l + 1; i <= d; i++) 
    if (a[i] < a[l]) 
     swap(&a[++k], &a[i]); 
swap(&a[l], &a[k]); 

>>> kvikSort(a, 0, k-1); 
kvikSort(a, l, k-1); 
kvikSort(a, k+1, d); 

Answer 2

你的第一个递归调用

kvikSort(a, 0, k-1); 

有错误的下界，它应该是

kvikSort(a, l, k-1); 

随着下限为0，你再重新排序数组的初始部分，再次。