快速排序 C++ 代码错误分段错误 11？

Question

代码：


#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
void partition(int *A, int start, int end){ //end is the position of the last number
    cout<<"start is "<<start<<" end is "<<end<<endl;
    if(end - start+1 > 1){
        int i = start + 1, j = start + 1, pivot = A[start];
        while(j <= end){
            if(A[j] <= pivot){
                swap(A[j], A[i]);
                i++;
            }
            j++;
        }
        swap(A[start], A[i-1]);
        partition(A, start, i-1);
        partition(A, i, end);
    }
    
}

void QuickSort(int *A, int n){
    partition(A, 0, n-1);
}


int main() {
    int n, method;
    string sortMethod[ ] = {
            "Insertion sort", "Selection sort", "Bubble sort", "Merge sort", "Quick sort"
    };
    int m = sizeof(sortMethod)/sizeof(string);
    srand(time(0));
    
    while (true){
        cout << "Number of test marks: ";
        cin >> n;
        if ( n==0 ) break;
        int *A = new int[n];
        for (int i=0; i < n; i++) cin>>A[i];
        //A[i] = rand()%101;

        for (int i=0; i < n; i++)cout << A[i] << " ";
        cout<<endl<<endl;


        cout << "Sorting method: \n"; 
        for (int i=0; i < m; i++) cout << i+1 << ": " << sortMethod[i] << endl;
        // cin >> method;
        method = 5;
        cout<<endl;
        int t = time(0);
        
        QuickSort(A,n);

        if (method > m) continue;       
        cout << sortMethod[method-1] << endl;
        if (n <= 100) {
            for (int i=0; i < n; i++) {
                if (i> 0 && i%10==0) cout << endl;
                cout << A[i] << " ";
            }
            cout << endl;
        }
        else {
            cout << "Sorting completed in " <<  time(0) - t  << " sec.\n";
        }
        cout << endl;
    } 
    cout << "Program ends here."<<endl;
    return 0;
}

当我的某些输入数字具有相同的值时，我收到“分段错误：11”。

例如，“4 7 7 3 1”的输入将产生以下输出的无限行：“开始是 1 结束是 3”。

请问我应该如何改进我的代码？我知道当您尝试访问无效内存时会发生段错误 11，我认为这可能是我在这里所做的，尽管我似乎无法识别错误。谢谢！

Answer 1

这就是这里发生的事情。想象一下，在某个partition中第一个元素（pivot）也是最大的。

这意味着在 while 循环的每次迭代中，A[j]<=pivot 的值将为真，并且 i 将增加。

由于 i 和 j 在每次迭代中都增加 1，因此值相同，因此在循环结束时它们都等于 end+1。

然后你正在调用 partition(A, start, i-1) 这实际上与 partition(A, start, end) 相同 - 这意味着你有一个无限递归，一直持续到你到达......好吧，堆栈溢出和程序因段错误而崩溃.

最小的修复方法是通过从子分区中排除枢轴来确保子分区严格小于原始分区。所以像这样：

        partition(A, start, i-2); // i-1 is the pivot, so we don't need to include it
        partition(A, i, end);

快速排序 C++ 代码错误分段错误 11？

quick sort c++ code error segmentation fault 11?

c++

sorting

algorithm

quicksort