C++快速排序索引0返回-842150451

Question

分區並具有myswap的基本快速排列功能。除了數組中的索引0以外，一切正常。

#include<iostream> 
#include<string> 
#include<iostream> 
#include<vector> 
#include <ctime> 

using namespace std; 

//swap 
void myswap(int mya[], int a, int b) { 
int temp = mya[a]; 
mya[a] = mya[b]; 
mya[b] = temp; 
} 

//partition, returns pivot index 
int mypartition(int mya[], int first, int last) 
{ 
    int middle = ((first + last)/2); 
    int pivot = mya[middle]; 
    //swap first with middle 
    myswap(mya, first, middle); 
    //two pointers 
    int pivotindex = first; 
    //loop through the elements 
    for (int index = first + 1; index <= last; index++) { 
     if (mya[index] <= pivot) 
     { 
      pivotindex++; 
      myswap(mya, pivotindex, index); 
     } 
    } 
    //swap the pivot in its right place 
    myswap(mya, first, pivotindex); 
    return pivotindex; 
} 



void QuickSort(int mya[], int a, int b) 
{ 
    //partition 
    if (a <= b) 
    { 
     int index = mypartition(mya, a, b); 
     QuickSort(mya, a, index - 1); 
     QuickSort(mya, index + 1, b); 
    } 
} 



int main() { 
    //vector<int> mya; 
    int * mya = new int[5000000]; 
srand(time(0)); 
int i = 0; 
int last = 0; 
while(i < 100) 
{ 
    int x = (rand() + time(0)) % 5000000; 
    mya[last] = x; 
    last++; 
    i++; 
} 

clock_t startTime, endTime; 
startTime = clock(); 
QuickSort(mya, 0, last); 
endTime = clock(); 
    cout << "Sorted in " << (double)(endTime - startTime)/CLOCKS_PER_SEC  << "  seconds" << endl; 
for (int i = 0; i < 100; i++) 
{ 
    cout << mya[i] << endl; 
} 
delete[] mya; 
return 0; 

} 

遇到的問題IM是，數組被排序，但是當MYA [0]是所謂的for循環它輸出-842150451。這只是一個基本的快速排序，由於某種原因我有麻煩。

Answer 1

你說錯了。

QuickSort(mya, 0, last-1); 

請記住，有last元素，這意味着它們的索引爲0..last-1。

在計算middle時，您也有潛在的溢出問題。使用(last - first + 1)/2 + first。

希望這會有所幫助。

Answer 2

整數溢出導致此問題。

int x = (rand() + time(0)) % 5000000;

這行有時兩個10位數號碼，其總和導致整數溢出。

只需修改聲明如下，你的代碼開始工作：

int x = (rand() % 5000000) + (time(0) % 5000000);

編輯：這是我發現使用Ideone執行你的代碼中的問題。進一步注意到我發現你的索引0問題實際上是由分區函數引起的。

變化for (int index = first + 1; index <= last; index++) {此行

for (int index = first + 1; index < last; index++) { //remove the equal sign

N.B：這對我來說固定您的問題。但我認爲你的void QuickSort(int mya[], int a, int b)
if (a <= b)應改爲if (a < b)。