c++ - 递归快速排序导致段错误(不是溢出)

Question

请帮助我(这对于明天到期的学校项目来说非常方便)

我一直在尝试用 C++ 实现递归快速排序算法，但是，当我运行它时，我遇到了运行时段错误 (windows):

#include <iostream>
#include <sstream>
#include <stdlib.h>

using namespace std;

void getRandomList(int, int*);
void outputList(int, int*);
void quicksort(int, int*);

int main()
{
    cout<<"Quick Sort example, By Jack Wilkie\n";
    while (true)
    {
        cout<<"Please enter list length\n";
        string pnput;
        cin>>pnput;
        cin.ignore(1);
        stringstream temp;
        temp << pnput;
        int length;
        temp >> length;
        if (length < 1 || length > 100000)
        {
            cout<<"INVALID INPUT! (0 < input < 100,000)\n";
        }
        else
        {
            cout<<"Creating random list of "<<length<<" items\n";
            int *list = new int[length];
            getRandomList(length, list);
            outputList(length, list);
            double start = clock();
            quicksort(length, list);
            double stop = clock();
            double time = stop-start;
            cout<<time<<"ms";
            cin.get();
            delete[] list;
            break;
        }
    }
}

void quicksort(int len, int* list)
{
    if (len < 1)
    {
        return;
    }
    else
    {
        int low[10];
        int mid[10];
        lmid[0] = list[0];
        int high[10];
        int lens[3] = {0,1,0};
        for(int i = 1; i < len; i++)
        {
            if(list[i] < list[0])
            {
                low[lens[0]] = list[i];
                lens[0]++;
            }
            else if (list[i] > list[0])
            {

                high[lens[2]] = list[i];
                lens[2]++;
            }
            else
            {
                mid[lens[1]] = list[i];  
                lens[1]++;
            }
        }
        quicksort(lens[0], low);
        quicksort(lens[2], high);
        for(int i = 0; i < len; i++)
        {
                if (i < lens[0])
                {
                      list[i] = low[i];
                }
                else if (i < lens[0]+lens[1])
                {
                       list[i] = mid[i-lens[0]];
                }
                else
                {
                    list[i] = high[i-lens[0]-lens[1]];
                }
        }
    }
    return;

}

我的调试程序(dev c++，几乎没有互联网而且无法得到任何大的东西)说错误在线

    lmid[0] = list[0];

但是我找不到任何问题，它一调用快速排序函数就出错，我相信这个问题与传递数组有关，而且我很确定该函数不是递归的并使堆栈膨胀

如果你需要它来调试，这里是我使用的其他函数

void getRandomList(int length, int* output)
{
    for(int i = 0; i < length; i++)
    {
        output[i] = rand() % 100;
    }
    return;
}

void outputList(int length, int* input)
{
    for(int i = 0; i < length; i++)
    {
        cout<<input[i]<<" ";
    }
    cout<<"\n";
    return;
}

Answer 1

您的退出基本情况不正确。

这个:

if (len < 1)

应该是这样的:

if (len <= 1)

这对于停止程序的无限递归非常很重要。你的错误发生是因为你破坏了你的自动变量存储空间(也就是堆栈)，每次迭代消耗越来越多的空间，直到最后 ker-boom。

---

一般就地快速排序

作为算法实现说明，您正在使这个比需要的难得多。 Quicksort 是关于分区的，并且正确完成后，您应该不需要用于交换元素的临时变量之外的临时存储。充分利用图书馆。为您提供交换机制，即std::swap .这显着清理了代码。

void quicksort(int arr[], size_t len)
{
    if (len <= 1)
        return;

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

    // important: do NOT include the pivot slot
    quicksort(arr, pvt++);
    quicksort(arr+pvt, len-pvt);
}

这在某些基本方面与您的算法不同，不仅仅是因为它有效:

• 它以数组作为第一个参数，长度第二。
• 它使用 arr[len-1] 来保持主元值，而不是 arr[0]
• 它不需要任何临时数组。

除了选择枢轴值(它应该是随机的，而不是总是在特定的槽位置)之外，这是用于就地快速排序的传统扫描分区方法。

---

基于迭代器的模板

虽然对您的需求来说有些过分，但上述算法可以扩展为通用的基于迭代器的模板，该模板可以使用 C++ 标准库轻松实现。

#include <type_traits>
#include <iterator>
#include <cstdlib>

// assumes T::operator <(const T&) exists for the iterated type.
template<
   typename Iterator,
   typename Compare=std::less<typename std::iterator_traits<Iterator>::value_type>
>
void quicksort(Iterator first, Iterator last, Compare&& cmp = Compare())
{
    // early exit on trivial list (zero or one element)
    typename std::iterator_traits<Iterator>::difference_type len = std::distance(first, last);
    if (len <= 1)
        return;

    // establish pivot, move it to end of sequence
    Iterator tail = std::prev(last,1);
    Iterator pvt = std::next(first, (std::rand() % len));
    std::iter_swap(pvt, tail);

    // run through scan
    pvt = first;
    for (Iterator head = first; head != tail; ++head)
    {
        if (cmp(*head,*tail))
            std::iter_swap(head, pvt++);
    }
    std::iter_swap(pvt, tail);

    // run through sublists. note: pvt is NOT included.
    quicksort(first, pvt, cmp);
    quicksort(++pvt, last, cmp);
}

这允许您在任何支持双向迭代器的序列容器上调用它。例如:

std::vector<int> data;

// populate data with values.

quicksort(data.begin(), data.end());

同样，它可以用在固定数组上:

int arr[N];

// populate arr with values

quicksort(std::begin(arr), std::end(arr));

// or
quicksort(arr, arr + sizeof(arr)/sizeof(*arr));

最后，使用围绕我们的快速排序实现的简单固定数组模板包装器，可以使固定数组示例更加直接:

template<typename T, std::size_t N>
void quicksort(T (&arr)[N])
{
    quicksort(std::begin(arr), std::end(arr));
}

然后我们可以简单地这样做:

int arr[N];

// populate arr with values

quicksort(arr);