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;

}

我的调试程序（开发 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。

---

常规就地快速排序

作为算法实现说明，你做的比它需要的要困难得多。快速排序是关于分区的，如果做得正确，你应该不需要临时存储在用于交换元素的临时变量之外。使用图书馆对您有利。为您提供了一种交换机制，即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);

Answer 2

不是你的问题的答案。

几周前，我在练习 C++ 容器和算法，并决定实现快速排序。我附上我的代码并不是因为它特别好或特别高效，而是我喜欢它给我使用 C++ 算法来解决特定问题的感觉。

也许它可以帮助您理解算法及其使用 C++ 的“功能”实现。

#include<iostream>
#include<iterator>
#include<functional>
#include<algorithm>
#include<vector>
#include<array>
#include<list>
#include<string>

namespace detail {
template<typename T, typename Iterator>
void show(Iterator first, Iterator last, Iterator pidx, int depth) {
  if(std::distance(first, last) <= 0) {
    return;
  }
  std::cout<<"tail depth: "<<depth<<std::string(depth, '\t')<<"[ ";
  std::copy(first, pidx, std::ostream_iterator<T>(std::cout, " "));
  std::cout<<"]  + "<<(*pidx) <<" + [ ";
  std::copy(std::next(pidx), last, std::ostream_iterator<T>(std::cout, " "));
  std::cout<<"]"<<std::endl;
}

template<typename T, typename Iterator>
void quicksort(Iterator first, Iterator last, int depth=0) {
  if(std::distance(first, last) > 0) {
    auto pred = std::bind(std::less<T>(), std::placeholders::_1, *first);    

    std::iter_swap(first, std::prev(last));
    auto pidx = std::partition(first, last, pred);    
    std::iter_swap(pidx, std::prev(last));

    depth++;    
    show<T>(first, last, pidx, depth);

    detail::quicksort<T>(first, pidx, depth);
    detail::quicksort<T>(std::next(pidx), last, depth);
  }
}
}

template<typename T>
void show(T& data) {
  std::cout<<"[ ";
  std::copy(data.begin(), data.end(), std::ostream_iterator<typename T::value_type>(std::cout, " "));
  std::cout<<"]"<<std::endl;
}

template<typename Container>
void quicksort(Container& data) {
  using T = typename Container::value_type;
  std::cout<<"Before sort: "; show(data);
  detail::quicksort<T>(std::begin(data), std::end(data));
  std::cout<<"After sort: "; show(data);
}

int main(int argc, char* argv[]) {

  std::cout<<"working with vector<int>"<<std::endl;
  std::vector<int> vdata = {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(vdata);

  std::cout<<"working with array<double>"<<std::endl;  
  std::array<double, 9> adata = {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(adata);

  std::cout<<"working with list<float>"<<std::endl;  
  std::list<float> cdata =  {5, 10, 0, 2, 8, 3, 7, 4, 6};
  quicksort(cdata);
  std::cout<<"worst case performance: sort a sorted container"<<std::endl;  
  quicksort(cdata);

  size_t N = argc == 2 ? std::stoi(argv[1]) : 100;
  std::cout<<"test on vector<int> with elements in [0, ..., "<<N-1<<"] shuffled randomly"<<std::endl;
  std::vector<int> ldata(N);
  std::iota(ldata.begin(), ldata.end(), 0);
  std::random_shuffle(ldata.begin(), ldata.end());
  quicksort(ldata);
  return 0;
}

我使用 GCC 4.8.1 在 OS X 10.7.4 上编译。样品运行：

$ /usr/local/bin/g++ quicksort-functional.cpp -std=c++11 -Wall -Wextra
$ ./a.out 
working with vector<int>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
working with array<double>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
working with list<float>
Before sort: [ 5 10 0 2 8 3 7 4 6 ]
tail depth: 1   [ 4 3 0 2 ]  + 5 + [ 10 7 6 8 ]
tail depth: 2       [ 2 3 0 ]  + 4 + [ ]
tail depth: 3           [ 0 ]  + 2 + [ 3 ]
tail depth: 4               [ ]  + 0 + [ ]
tail depth: 4               [ ]  + 3 + [ ]
tail depth: 2       [ 8 7 6 ]  + 10 + [ ]
tail depth: 3           [ 6 7 ]  + 8 + [ ]
tail depth: 4               [ ]  + 6 + [ 7 ]
tail depth: 5                   [ ]  + 7 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
worst case performance: sort a sorted container
Before sort: [ 0 2 3 4 5 6 7 8 10 ]
tail depth: 1   [ ]  + 0 + [ 2 3 4 5 6 7 8 10 ]
tail depth: 2       [ ]  + 2 + [ 3 4 5 6 7 8 10 ]
tail depth: 3           [ ]  + 3 + [ 4 5 6 7 8 10 ]
tail depth: 4               [ ]  + 4 + [ 5 6 7 8 10 ]
tail depth: 5                   [ ]  + 5 + [ 6 7 8 10 ]
tail depth: 6                       [ ]  + 6 + [ 7 8 10 ]
tail depth: 7                           [ ]  + 7 + [ 8 10 ]
tail depth: 8                               [ ]  + 8 + [ 10 ]
tail depth: 9                                   [ ]  + 10 + [ ]
After sort: [ 0 2 3 4 5 6 7 8 10 ]
test on vector<int> with elements in [0, ..., 99] shuffled randomly
Before sort: [ 95 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 99 96 33 11 34 4 86 46 39 52 97 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 98 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 40 85 18 65 92 ]
tail depth: 1   [ 92 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 93 45 79 62 31 19 60 22 69 94 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 0 3 72 ]  + 95 + [ 97 96 99 98 ]
tail depth: 2       [ 72 37 56 15 50 77 61 66 8 43 90 7 25 74 1 26 38 87 13 64 57 84 6 16 17 67 35 42 55 9 59 81 2 68 58 29 76 73 65 18 33 11 34 4 86 46 39 52 85 82 10 41 53 28 49 5 80 12 71 14 91 88 24 3 45 79 62 31 19 60 22 69 0 63 51 32 44 75 40 78 30 89 47 23 83 48 54 21 70 36 20 27 ]  + 92 + [ 93 94 ]
tail depth: 3           [ 27 37 56 15 50 20 61 66 8 43 36 7 25 70 1 26 38 21 13 64 57 54 6 16 17 67 35 42 55 9 59 48 2 68 58 29 23 47 65 18 33 11 34 4 30 46 39 52 40 44 10 41 53 28 49 5 32 12 71 14 51 63 24 3 45 0 62 31 19 60 22 69 ]  + 72 + [ 88 91 80 82 75 85 78 86 89 73 76 83 81 84 87 74 90 77 79 ]
tail depth: 4               [ 22 19 0 15 3 20 24 14 8 12 5 7 25 10 1 26 4 21 13 11 18 23 6 16 17 2 9 ]  + 27 + [ 55 35 59 48 67 68 58 29 54 47 65 57 33 64 34 38 30 46 39 52 40 44 70 41 53 28 49 36 32 43 71 66 51 63 61 50 45 56 62 31 37 60 69 42 ]
tail depth: 5                   [ 9 19 0 15 3 20 2 14 8 12 5 7 17 10 1 16 4 21 13 11 18 6 ]  + 22 + [ 26 25 24 23 ]
tail depth: 6                       [ 6 4 0 1 3 7 2 5 8 ]  + 9 + [ 14 20 17 10 15 16 19 21 13 11 18 12 ]
tail depth: 7                           [ 5 4 0 1 3 2 ]  + 6 + [ 8 7 ]
tail depth: 8                               [ 2 4 0 1 3 ]  + 5 + [ ]
tail depth: 9                                   [ 1 0 ]  + 2 + [ 3 4 ]
tail depth: 10                                      [ 0 ]  + 1 + [ ]
tail depth: 11                                          [ ]  + 0 + [ ]
tail depth: 10                                      [ ]  + 3 + [ 4 ]
tail depth: 11                                          [ ]  + 4 + [ ]
tail depth: 8                               [ 7 ]  + 8 + [ ]
tail depth: 9                                   [ ]  + 7 + [ ]
tail depth: 7                           [ 12 11 13 10 ]  + 14 + [ 16 19 21 17 20 18 15 ]
tail depth: 8                               [ 10 11 ]  + 12 + [ 13 ]
tail depth: 9                                   [ ]  + 10 + [ 11 ]
tail depth: 10                                      [ ]  + 11 + [ ]
tail depth: 9                                   [ ]  + 13 + [ ]
tail depth: 8                               [ 15 ]  + 16 + [ 21 17 20 18 19 ]
tail depth: 9                                   [ ]  + 15 + [ ]
tail depth: 9                                   [ 19 17 20 18 ]  + 21 + [ ]
tail depth: 10                                      [ 18 17 ]  + 19 + [ 20 ]
tail depth: 11                                          [ 17 ]  + 18 + [ ]
tail depth: 12                                              [ ]  + 17 + [ ]
tail depth: 11                                          [ ]  + 20 + [ ]
tail depth: 6                       [ 23 25 24 ]  + 26 + [ ]
tail depth: 7                           [ ]  + 23 + [ 25 24 ]
tail depth: 8                               [ 24 ]  + 25 + [ ]
tail depth: 9                                   [ ]  + 24 + [ ]
tail depth: 5                   [ 42 35 37 48 31 45 50 29 54 47 51 43 33 32 34 38 30 46 39 52 40 44 36 41 53 28 49 ]  + 55 + [ 64 57 71 66 65 63 61 58 68 56 62 67 59 60 69 70 ]
tail depth: 6                       [ 28 35 37 41 31 36 40 29 39 30 38 34 33 32 ]  + 42 + [ 51 47 46 54 52 50 44 45 48 53 49 43 ]
tail depth: 7                           [ ]  + 28 + [ 35 37 41 31 36 40 29 39 30 38 34 33 32 ]
tail depth: 8                               [ 32 33 34 31 30 29 ]  + 35 + [ 39 36 38 41 37 40 ]
tail depth: 9                                   [ 29 30 31 ]  + 32 + [ 33 34 ]
tail depth: 10                                      [ ]  + 29 + [ 30 31 ]
tail depth: 11                                          [ ]  + 30 + [ 31 ]
tail depth: 12                                              [ ]  + 31 + [ ]
tail depth: 10                                      [ ]  + 33 + [ 34 ]
tail depth: 11                                          [ ]  + 34 + [ ]
tail depth: 9                                   [ 37 36 38 ]  + 39 + [ 40 41 ]
tail depth: 10                                      [ 36 ]  + 37 + [ 38 ]
tail depth: 11                                          [ ]  + 36 + [ ]
tail depth: 11                                          [ ]  + 38 + [ ]
tail depth: 10                                      [ ]  + 40 + [ 41 ]
tail depth: 11                                          [ ]  + 41 + [ ]
tail depth: 7                           [ 43 47 46 49 48 50 44 45 ]  + 51 + [ 53 54 52 ]
tail depth: 8                               [ ]  + 43 + [ 47 46 49 48 50 44 45 ]
tail depth: 9                                   [ 45 46 44 ]  + 47 + [ 50 49 48 ]
tail depth: 10                                      [ 44 ]  + 45 + [ 46 ]
tail depth: 11                                          [ ]  + 44 + [ ]
tail depth: 11                                          [ ]  + 46 + [ ]
tail depth: 10                                      [ 48 49 ]  + 50 + [ ]
tail depth: 11                                          [ ]  + 48 + [ 49 ]
tail depth: 12                                              [ ]  + 49 + [ ]
tail depth: 8                               [ 52 ]  + 53 + [ 54 ]
tail depth: 9                                   [ ]  + 52 + [ ]
tail depth: 9                                   [ ]  + 54 + [ ]
tail depth: 6                       [ 60 57 59 62 56 63 61 58 ]  + 64 + [ 65 66 67 71 70 69 68 ]
tail depth: 7                           [ 58 57 59 56 ]  + 60 + [ 63 61 62 ]
tail depth: 8                               [ 56 57 ]  + 58 + [ 59 ]
tail depth: 9                                   [ ]  + 56 + [ 57 ]
tail depth: 10                                      [ ]  + 57 + [ ]
tail depth: 9                                   [ ]  + 59 + [ ]
tail depth: 8                               [ 62 61 ]  + 63 + [ ]
tail depth: 9                                   [ 61 ]  + 62 + [ ]
tail depth: 10                                      [ ]  + 61 + [ ]
tail depth: 7                           [ ]  + 65 + [ 66 67 71 70 69 68 ]
tail depth: 8                               [ ]  + 66 + [ 67 71 70 69 68 ]
tail depth: 9                                   [ ]  + 67 + [ 71 70 69 68 ]
tail depth: 10                                      [ 68 70 69 ]  + 71 + [ ]
tail depth: 11                                          [ ]  + 68 + [ 70 69 ]
tail depth: 12                                              [ 69 ]  + 70 + [ ]
tail depth: 13                                                  [ ]  + 69 + [ ]
tail depth: 4               [ 79 77 80 82 75 85 78 86 74 73 76 83 81 84 87 ]  + 88 + [ 90 91 89 ]
tail depth: 5                   [ 76 77 73 74 75 78 ]  + 79 + [ 86 82 80 87 83 81 84 85 ]
tail depth: 6                       [ 75 74 73 ]  + 76 + [ 78 77 ]
tail depth: 7                           [ 73 74 ]  + 75 + [ ]
tail depth: 8                               [ ]  + 73 + [ 74 ]
tail depth: 9                                   [ ]  + 74 + [ ]
tail depth: 7                           [ 77 ]  + 78 + [ ]
tail depth: 8                               [ ]  + 77 + [ ]
tail depth: 6                       [ 85 82 80 84 83 81 ]  + 86 + [ 87 ]
tail depth: 7                           [ 81 82 80 84 83 ]  + 85 + [ ]
tail depth: 8                               [ 80 ]  + 81 + [ 83 84 82 ]
tail depth: 9                                   [ ]  + 80 + [ ]
tail depth: 9                                   [ 82 ]  + 83 + [ 84 ]
tail depth: 10                                      [ ]  + 82 + [ ]
tail depth: 10                                      [ ]  + 84 + [ ]
tail depth: 7                           [ ]  + 87 + [ ]
tail depth: 5                   [ 89 ]  + 90 + [ 91 ]
tail depth: 6                       [ ]  + 89 + [ ]
tail depth: 6                       [ ]  + 91 + [ ]
tail depth: 3           [ ]  + 93 + [ 94 ]
tail depth: 4               [ ]  + 94 + [ ]
tail depth: 2       [ 96 ]  + 97 + [ 99 98 ]
tail depth: 3           [ ]  + 96 + [ ]
tail depth: 3           [ 98 ]  + 99 + [ ]
tail depth: 4               [ ]  + 98 + [ ]
After sort: [ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ]

Answer 3

我没有看到 lmid 变量的任何声明或初始化。那可能是个问题。