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;
}

我遇到的问题是数组被排序了，但当在for循环中调用mya[0]时，它会输出-842150451。这只是一个基本的快速排序，由于某些原因，我遇到了问题。

Answer 1

您的调用错误。

QuickSort(mya, 0, last-1);

请记住，有last元素，这意味着它们被索引为0.last1。

您在计算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

对我来说，这解决了你的问题。但我认为在你的void QuickSort(int mya[], int a, int b)
应将if (a <= b)更改为if (a < b)。