c - 快速排序算法行为异常

Question

这是一个尝试使用快速排序算法对数组进行排序的程序。一切似乎都很好，只是输出不正确。

（尝试 n=5 的程序，然后 n=10。它适用于前者，但不适用于后者。）

#include <stdio.h>
//#include <iostream.h>
//#include <conio.h>

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i <= j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    return i;
}

void quick_sort(int arr[], int p, int r)   {
    if (p<r)   {
       int q=partition(arr, p, r);
       quick_sort(arr, p, q-1);
       quick_sort(arr, q+1, r);
    }
}

int main()  {
    int values[100], n, i;

    //clrscr();

    printf("Enter no. of elements ");
    scanf("%d", &n);

    if (n>100) {
        printf("Invalid input. Exiting now");
        //getch();
        return 0;
    }

    for (i=0; i<100; i++) values[i]=0;

    printf("Enter the numbers\n");
    for (i=0; i<n; i++) scanf("%d", &values[i]);

    printf("The numbers you entered are\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    printf("\n");

    quick_sort(values, 0, n-1);

    printf("Numbers after sorting are\n");
    printf("(The output might not be the expected one (Be careful).\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    //std::cin.get();

    return 0;
}

Answer 1

有两个问题。首先，比较i <= j是错误的。如果i == j，则不应将元素与其自身交换。i < j这应该在两个地方都改为。其次，您不应该在交换后移动i和数组索引。j如果它是最后一次交换，i则会超过实际的枢轴并导致您的错误。

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i < j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    return i;
}

Answer 2

最好使用 algorithm.h中的 std 排序：

http://www.cplusplus.com/reference/algorithm/sort/