1

我编写了下面的快速排序程序。但是，它似乎不起作用。有人能指出这个程序有什么问题吗？

#include<stdio.h>

void swap (int a[], int left, int right) {
    int temp;
    temp=a[left];
    a[left]=a[right];
    a[right]=temp;
} 

void printarray(int a[], int);
void partition( int a[], int low, int high );

void quicksort( int a[], int low, int high ) {
    srand((unsigned int)time(0));
    partition( a, low, high );
} 

void partition( int a[], int low, int high ) {
    int left, right;
    int pivot_item, pivot;

    left = low;
    right = high;

    if ((right - left) <= 1)
        return;

    pivot = rand() % (high - low + 1);
    pivot_item = a[pivot];

    while (left < right) {
        while (a[left] <= pivot_item)
            left++;

        while (a[right] > pivot_item)
            right--;

        swap(a,left,right);
    }

    partition(a, low, right-1);
    partition(a, right+1, high);

    return;
}

int main() {
    int a[] = {24, 5, 3, 35, 14, 23, 19, 43, 2, 1};
    int i, n = 10;

    printf("\nUnsorted elements: \n");
    printarray(a,n);
    quicksort(a,0,n-1);
    printf("\nSorted elements: \n");
    printarray(a,n);

}


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

    for (i = 0; i < n; i++)
        printf(" %d ", a[i]);
    printf("\n");
}

每次我得到不同的输出如下。

:>~/prgms$ ./a.out 

Unsorted elements: 
 24  5  3  35  14  23  19  43  2  1 

Sorted elements: 
 14  2  19  1  5  23  43  35  3  24 

:>~/prgms$ ./a.out 

Unsorted elements: 
 24  5  3  35  14  23  19  43  2  1 

Sorted elements: 
 1  5  35  14  23  19  3  24  43  2
4

2 回答 2

3

除了stark指出的错误，可以通过更改来修复

pivot = rand() % (high - low + 1);

至

pivot = low + rand() % (high - low + 1);

还有两个错误。第一的，

    while( a[left] <= pivot_item )
    left++;

应该

    while (a[left] < pivot_item) left++;

否则，索引left可能会增加超出枢轴位置甚至数组末尾，从而导致未定义的结果。第二，

if ((right - left) <= 1)
return;

应该

if (right - left < 1) return;

否则，长度为 2 的分区不会被排序。

于 2014-10-02T07:31:27.523 回答
2

在分区中，枢轴取自范围 0..(high-low+1)。它应该取自低..高的范围。

于 2013-10-18T20:38:43.113 回答