快速排序進入無限循環

我正在嘗試編寫快速排序的代碼，但它始終在進行無限循環，我試圖在下面的代碼中找到錯誤，請有人幫忙。快速排序進入無限循環

#include<stdio.h> 
#include<stdlib.h> 

int arr[100]; 

void quicksort(int low,int high) 
{ 
    int i = low,j = high,pivotIndex,pivot; 
    pivotIndex = rand()%20; 
    pivot = arr[pivotIndex]; 

    if(i>=j) 
     return; 

    while(i<j) 
    { 

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

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

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

    } 
    quicksort(low,i); 
    quicksort(i+1,high); 
} 

int main() 
{ 
    int i,j,temp; 

    for(i=0;i<20;i++) 
     arr[i] = rand()%21; 

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

    quicksort(0,19); 

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

    return 0; 
}

來源

2012-10-31 user1543957

@DEVENDERGOYAL：您的編輯更改的問題，實際上固定在它的錯誤之一，在這個問題上的一個問題是這樣的錯誤。確保在編輯時 - 你不會改變問題本身。 – amit

你支點的選擇是錯誤的，你應該選擇在（指數）一轉動範圍[low,high)，當你在範圍[0,20)選擇了一個支點：

pivotIndex = rand()%20;

這稍後將分區不順利，並且您後來用於遞歸的值i將是錯誤的。

編輯：

還有一個問題是與分配，也應該考慮到與樞軸元素及其重複做的 - 應該有某種「電網斷路器」 - 的數據透視應該轉到數組的一側（或者其他選擇）。
例如，假設數據的關鍵是5，數組是[5,3,8,5]：
您將只是無限地交換5的一遍又一遍，這是錯誤的。

來源

2012-10-31 08:32:30 amit

-1

pivotIndex = rand()%20; 
pivot = arr[pivotIndex];

每次

在這裏，您撥打的快速排序的pivotIndex可能不在範圍內（低，高）。您可以使用

pivotIndex = low+rand()%(high-low);

我相信這將在範圍內產生pivotIndex用。

來源

2012-10-31 08:39:47

'我確定這會生成範圍內的pivotIndex。「它不會，考慮低= 10，高= 20，初始數組只有20個元素。（結果可能是pivotIndex == 29）你應該讓他在指出問題後找出這個問題，IMO。 – amit

作爲一個排序插件的作者，我可以向你保證，重新創建這些類型的算法可以真正讓你成爲衆矢之的。 ; o）

必須特別注意（如前所述）選擇主元，算法如何影響主元值（例如，VBA以浮點形式進行整數運算，導致各種奇怪），'剩飯'去的地方，最後一步如何處理最後一個分區（你不會第一個跳過這裏的幾條記錄）。

下面是在許多語言排序算法的鏈接：

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

來源

2012-10-31 11:05:06 Avan

快速排序進入無限循環

回答

相關問題