快速排序运行时速度问题(Quick sort runtime speed concerns)

快速排序运行时速度问题(Quick sort runtime speed concerns)

我有些困扰我的事情。 我有一个快速排序算法的实现，但是当我在一个包含超过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); }

编辑：我在我的Linux Mint 14上使用GCC v 4.7.2，proc：intel core2duo 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; }

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

I am having something that troubles me. I have my implementation of a quick sort algorithm, but when I test it on an array of integers that has over 30 elements, sorting takes, in my opinion to long. Sometimes even more than 10 seconds, unlike with selection sort, insertion sort and bubble sort, which are faster on 10000 elements than quick sort on 100 elements.

Here is my solution, please give advice :)

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); }

EDIT: I am using GCC v 4.7.2 on my Linux Mint 14, proc: intel core2duo e7400

EDIT: My other algorithms:

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; }

EDIT: Maybe I should mention that in my test program I am first outputing randomly generated array to a text file, then sorted array to another text file. So it is certainly running slow, but that's not the problem, the problem is that quick sort runs a lot slower than the rest.

最满意答案

这是问题所在：

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);

Here's the problem:

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);