1

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

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

4

2 回答 2

4

你的第一个递归调用

kvikSort(a, 0, k-1);

有错误的下限，它应该是

kvikSort(a, l, k-1);

使用下限 0，您会一次又一次地重新排序数组的初始部分。

于 2013-04-11T22:29:49.807 回答
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);
于 2013-04-11T22:30:53.847 回答