快速排序算法行为奇怪

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

是更好地使用std排序从algorithm.h：

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