C++ QuickSort算法不斷崩潰

Question

試圖實現快速排序algorithm.I認爲問題是與遞歸，但我不知道我應該做什麼來解決它。每次我運行它時程序都會繼續崩潰，我不明白爲什麼。下面是代碼：

#include<iostream> 

using namespace std; 
int pIndex; 

int Partition(int *A,int start,int end){ 

int pivot; 
int pIndex; 
if(start<end){ 
    int pivot=A[end]; 
    int pIndex=start; 
    for(int x=0;x<end;x++){ 
     if(A[x]<A[end]){ 
      swap(A[x],A[pIndex]); 
      pIndex=pIndex+1; 
     } 
    } 
    swap(A[pIndex],A[end]); 
} 
//cout<<pIndex<<endl; 
swap(A[pIndex],A[end]); 
return pIndex; 
}; 
void QuickSort(int *A, int start,int end){ 
    if(start<end) 
    { 

    pIndex=Partition(A,start,end); 
    QuickSort(A,pIndex+1,end); 
    QuickSort(A,start,pIndex-1); 
} 
}; 
int main(){ 

int A[10]{4,23,1,43,2,10}; 
//Partition(A,0,9); 
QuickSort(A,0,5); 
for(int x=0;x<10;x++){ 
    cout<< A[x]<<" "; 
} 
} 

Answer 1

您的分區算法大約是它需要的兩倍的代碼。你似乎總是選擇最後元素的順序爲您的樞紐，雖然不可取，它將適用於學術演示。

你崩潰

你定義兩個pIndex值，只有其中一個是真正的確定性。您還聲明兩個pivot變量，但這不會導致您的崩潰（第一個從未使用）。應清理無 - 少，但在你的代碼中的喪鐘是複製pIndex

int pivot; 
int pIndex;  // HERE 
if(start<end){ 
    int pivot=A[end]; 
    int pIndex=start; // HERE AGAIN 
    for(int x=0;x<end;x++){ 
     if(A[x]<A[end]){ 
      swap(A[x],A[pIndex]); 
      pIndex=pIndex+1; 
     } 
    } 
    swap(A[pIndex],A[end]); 
} 
swap(A[pIndex],A[end]); // uses non-determined pIndex 
return pIndex; // returns non-determined pIndex 

更改int pIndex=start;到僅僅是pIndex=start;將解決您的崩潰，但你的分區方法仍然需要...幫助。

---

的「掃」分區方法

分區的「掃蕩」方法一般是這樣做對於被認爲是右尾樞軸價值，你會很難得到這個簡單（調用std::partition不耐受）：

size_t Partition(int *A, size_t len) 
{ 
    if (len < 2) 
     return 0; 

    size_t pvt = 0; 
    for (size_t i=0; i<end; ++i) 
    { 
     if (A[i] < a[len-1]) 
      std::swap(A[i], A[pvt++]) 
    } 
    std::swap(A[pvt], a[len-1]); 
    return pvt; 
}; 

以上算法僅包括需要一個分區的必需品：序列迭代器（在你的情況下指針），以及sequenc長度。其他一切都是基於這兩個項目的確定性。這是如何工作的快速樣本程序如下，以故意放置5樞軸值：

#include <iostream> 

size_t Partition(int *A, size_t len) 
{ 
    if (len < 2) 
     return 0; 

    size_t pvt = 0; 
    for (size_t i=0; i<len-1; ++i) 
    { 
     if (A[i] < A[len-1]) 
      std::swap(A[i], A[pvt++]); 
    } 
    std::swap(A[pvt], A[len-1]); 
    return pvt; 
}; 

int main() 
{ 
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 }; 
    size_t n = Partition(arr, sizeof(arr)/sizeof(*arr)); 
    std::cout << "Partition : " << n << '\n'; 
    for (auto x : arr) 
     std::cout << x << ' '; 
    std::cout << '\n'; 
} 

輸出

Partition : 4 
4 3 2 1 5 7 8 6 9 

---

如何調用從快速排序

調用在快速排序分區設置的樞轉位置，這將成爲「末端」迭代點o F中的底段和頂段的一BEFORE迭代點。這是從Partition()的調用返回關鍵樞軸位置遞歸時不應該包括在要麼序列。

void QuickSort(int *A, size_t len) 
{ 
    if (len < 2) 
     return; 

    size_t pvt = Partition(A, len); 
    QuickSort(A, pvt++);  // NOTE: post increment... 
    QuickSort(A+pvt, len-pvt); // ...which makes this skip the pivot 
} 

是的，指針算術的岩石，你不覺得嗎？

---

全部放在一起

下面程序結合兩者的Partition和QuickSort：

#include <iostream> 

size_t Partition(int *A, size_t len) 
{ 
    if (len < 2) 
     return 0; 

    size_t pvt = 0; 
    for (size_t i=0; i<len-1; ++i) 
    { 
     if (A[i] < A[len-1]) 
      std::swap(A[i], A[pvt++]); 
    } 
    std::swap(A[pvt], A[len-1]); 
    return pvt; 
}; 

void QuickSort(int *A, size_t len) 
{ 
    if (len < 2) 
     return; 

    size_t pvt = Partition(A, len); 
    QuickSort(A, pvt++);   // NOTE: post increment 
    QuickSort(A+pvt, len-pvt); 
} 

int main() 
{ 
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 }; 
    QuickSort(arr, sizeof(arr)/sizeof(*arr)); 
    for (auto x : arr) 
     std::cout << x << ' '; 
    std::cout << '\n'; 
} 

輸出

1 2 3 4 5 6 7 8 9 

我希望它有幫助。

Answer 2

在這一部分：

int pivot; 
int pIndex; 
if(start<end){ 
    int pivot=A[end]; 
    int pIndex=start; 

您定義兩個支點，和兩個p食指的。根本沒有使用數據透視表，並且使用最後一次交換使用未初始化的pIndex。這應該工作：

int Partition(int *A,int start,int end){  
    int pIndex = start; 
    if(start<end){ 
     for(int x=0;x<end;x++){ 
      if(A[x]<A[end]){ 
       swap(A[x],A[pIndex]); 
       pIndex=pIndex+1; 
      } 
     } 
     swap(A[pIndex],A[end]); 
    } 
    swap(A[pIndex],A[end]); 
    return pIndex; 
} 

Answer 3

我也是一個C++新手，但我發現自己好奇開始> =結束時會發生什麼。看起來你的分區函數仍然會返回一個pIndex值，但是我看不到你在哪裏定義它。如果（如我懷疑）它返回任何值發生駐留在內存中，那麼當你使用A [pIndex]