快速排序算法行爲奇怪

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/