需要了解此快速排序

我真的很難理解快速排序。這是我的理解至今需要了解此快速排序

我們選擇樞軸
小於支點的所有元素都在樞軸
比樞軸更多的所有元素右側
使用遞歸去左邊去繼續這個過程

現在我的問題是，我不明白如何繼續最後一步是遞歸。到目前爲止，我有以下幾點。我只是想要一個非常基本的。該陣列將不會有重複

void quickSort(int *ptr,int lowindex , int highindex) 
{ 
    int left = lowindex ; 
    int right = highindex; 
    int pivot = ptr[rand()%highindex]; 

    while(left < right) 
    { 
     while(ptr[left] < pivot) 
     { 
      left++; 
     } 
     while(ptr[right] > pivot) 
     { 
      right--; 
     } 

     //Now swap the two 
     int temp = ptr[left]; 
     ptr[left] = ptr[right]; 
     ptr[right] = temp; 
    } 

    std::cout << "Current Array is : "; 
    for(int i=0;i<7;i++) 
    { 
     std::cout << ptr[i] << "," ; 
    } 
    std::cout << "\n"; 

     //How to add recursion ? 
}

而且是有while(left < right)環路機會卡住 - 即左，右不會改變，因此不斷循環？如果是的話我該如何處理呢？

來源

2014-03-01 Rajeshwar

當'ptr [left]'和'ptr [right]'都指向等於主鍵的值時會發生什麼？ –

嗯。我沒有考慮到這一點 – Rajeshwar

此行

int pivot = ptr[rand()%highindex];

應該是

int pivot = ptr[lowindex+rand()%(highindex-lowindex+1)];

假設活性範圍是lowindex和highindex之間。但即使如此，您仍然會遇到問題，即您不知道樞軸是屬於左側還是右側，因此從固定位置（如pivot=ptr[lowindex]）中選取它更容易。

你的一個比較操作應包括平等，像

while(ptr[left] <= pivot)

在最後你會發現left指針超過樞軸，並以right指針的權利。在這種情況下，您不得執行交換操作。

if(left < right){ // swap

後，您需要做的分區確保樞軸價值兩部分

swap(ptr[lowindex /*pivot*/], ptr[right]);

最後遞歸添加的功能是這樣的結尾之間結束了：

quickSort(ptr, lowindex, right-1); 
quickSort(ptr, left, highindex);

雖然一般的概念看起來很簡單，但細節有點棘手。準備一些調試。希望這可以幫助。

來源

2014-03-01 23:09:01 pentadecagon

需要了解此快速排序

回答

相關問題