排序函數C++

Question

所以我有這個函數，在一個數據透視表上排序，我遇到的問題是獲取數據透視圖，一旦中間數字到達它，它將數字的右側和數字的左側進行排序在樞軸之間，但一旦到達中心，它就不會跨越。我認爲這與我的while循環有關。請幫助！

void qsort（int * arry，unsigned int size）;

int main() 
{ 
    int arry[] = {45, 27, 82, 21, 63, 22, 35, 19, 4, 5}; 

    qsort(arry, 10); 


    system("pause"); 
    return 0; 
} 


void qsort(int *arry, unsigned int size) 
{ 
    int piv = *arry; 
    int *left, *right, temp; // create the traversal pointers 
    if (size > 1) 
    { 


     while(WHAT GOES HERE?!) 
     { 

     left = arry + 1; 
     right = arry + (size - 1); 


      //process left pointer for value larger than piv. 
      while((*left < piv) && (left < right)) 
      { 
       ++left; 
      } 
      cout << *left << endl; 

      //process right pointer for value smaller tham piv 
      while((*right > piv) && (right > left)) 
      { 
       right--; 
      } 
      cout << *right << endl; 
      temp = *left; 
      *left = *right; 
      *right = temp; 
     } 

    } //How do I verify the placement of the pivot value? 
    for(unsigned int i=0; i < size; i++) 
     cout << arry[i] << " "; 
    cout << endl; 
} 

Answer 1

什麼是這裏不是你應該有這個代碼的唯一問題。有很多問題可能會出現。

首先，你的left-ptr和right-ptr初始化器不應該在循環內;他們需要在外設之前成爲設置的一部分。你的功能序言看起來應該是這樣的：

void quicksort(int *arry, size_t size) 
{ 
    if (size <= 1) // skip 1-length lists. 
     return; 

    // since you're using a static pivot location, 
    // may as well use the one at the right end. 
    int *left = arry; 
    int *right = arry + (size-1); 

    // choose a pivot value. ideally a random trio is chosen, and the 
    // middle element of those three is selected. for this simple case 
    // we're using the element at the right-most location of the list 
    int piv = arry[size-1]; 

下一步這裏是限制器，最終停止你的while循環的瘋狂。傳統上它很簡單：

while (left < right) 

只要你的左邊，PTR趕上你的右指針（反之亦然），就沒有必要再繼續循環。請記住，已知左側ptr左側的所有值都小於（並且可能等於，但我們將在一分鐘內達到）主軸。同樣，right-ptr右側的所有值都知道大於pivot。後面的摺疊旋轉窗的想法是你從未真正交換，直到你有物品需要交換的地方。

這將我們帶入內部while循環。

//process left pointer for value larger than piv. 
    while((*left < piv) && (left < right)) 
     ++left; 

    //process right pointer for value smaller tham piv 
    while((*right > piv) && (right > left)) 
     right--; 

這個最根本的問題是，當*left和*right碰巧在同一時間運行到樞軸值（在兩個不同的時隙）會發生什麼。他們都停止，然後他們都這樣做：

temp = *left; 
*left = *right; 
*right = temp; 

然後循環繼續。兩個迴路周圍的下一次將立即終止（因爲他們倆都坐在旋轉的價值，他們會回來的調劑，再次切換他們，然後重複此...永遠。爲了解決這個問題，這些指針之一必須包括樞軸作爲允許步行過而且只交換，如果左PTR仍比右PTR少

// walk up until we find a value strictly larger than the pivot 
while(left < right && (*left <= piv)) 
    ++left; 

// walk down until we find a value smaller than the pivot 
while (right > left && (*right > piv)) 
    --right; 

if (left < right) 
    swap(*left, *right); 

注意：這裏使用了std::swap()功能，最方便的工具

。

最後，從底部丟失的那一塊，遞歸我們回到剛剛與我們的步行者確定的兩個部分，但只有在確保底部分區和頂部分區確實是分離的之後。

// make sure left and right are properly ordered. 
if (left > right) 
    swap(left,right); 

// sort subslices 
quicksort(arry, (left - arry)); 
quicksort(arry + (right - arry), size - (right - arry)); 

與測試中，它的一個範例程序全部放在一起，沿着：

示例程序

#include <iostream> 
#include <vector> 
#include <string> 
#include <iterator> 
#include <cstdlib> 
#include <ctime> 
using namespace std; 

// in-place quicksort. 
void quicksort(int *arry, size_t size) 
{ 
    if (size <= 1) 
     return; 

    // since you're using a static pivot location, 
    // may as well use the one at the right end. 
    int *left = arry; 
    int *right = arry + (size-1); 

    // choose a pivot value. ideally a random trio is chosen, and the 
    // middle element of those three is selected. for this simple case 
    // we're using the element at the right-most location of the list 
    int piv = arry[size-1]; 

    while(left < right) 
    { 
     // walk up until we find a value strictly larger than the pivot 
     while(left < right && (*left <= piv)) 
      ++left; 

     // walk down until we find a value smaller than the pivot 
     while (right > left && (*right > piv)) 
      --right; 

     if (left < right) 
      swap(*left, *right); 
    } 

    // make sure left and right are properly ordered. 
    if (left > right) 
     swap(left,right); 

    // sort subslices 
    quicksort(arry, (left - arry)); 
    quicksort(arry + (right - arry), size - (right - arry)); 
} 

int main() 
{ 
    int arry[] = {45, 27, 82, 21, 63, 22, 35, 19, 4, 5}; 

    // before picture 
    std::copy(arry, arry+10, ostream_iterator<int>(cout, " ")); 
    cout << endl; 
    quicksort(arry, 10); 

    // after picture 
    std::copy(arry, arry+10, ostream_iterator<int>(cout, " ")); 
    cout << endl; 

    std::srand((unsigned)std::time(0)); 
    std::vector<int> vals(30); 
    for (size_t i=0;i<15;++i) 
     vals[i] = vals[15+i] = int(i+1); 
    std::random_shuffle(vals.begin(), vals.end()); 

    // before picture 
    std::copy(vals.begin(), vals.end(), ostream_iterator<int>(cout, " ")); 
    cout << endl; 
    quicksort(vals.data(), vals.size()); 

    // after picture 
    std::copy(vals.begin(), vals.end(), ostream_iterator<int>(cout, " ")); 
    cout << endl; 

    return 0; 
} 

樣本輸出

45 27 82 21 63 22 35 19 4 5 
4 5 19 21 22 27 35 45 63 82 
14 9 2 1 3 11 8 4 12 15 10 13 5 3 2 11 14 7 7 12 8 15 6 9 6 5 10 4 13 1 
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 

我希望這answe關於一般快速排序如何工作的一些問題。我個人更喜歡單端的就地掃描版本。我發現解釋要容易得多，當然也更容易理解。如果你想看到它，讓我知道。