我正在研究使用向量和模板的快速排序算法。
我正在测试算法100、1000和1M次。
它可以进行一些测试,例如对随机列表进行排序,但是在对降序列表进行排序时,我在xcode中遇到以下错误,并在终端上运行时遇到细分错误:11。

Thread: EXC_BAD_ACCESS(Code=2, address0x...

我仍然是C ++初学者,我不太了解自己在做什么错。任何提示或可能的解决方案?

#include <iostream>
#include <cstdlib>
#include <vector>


template <class T>
class quickSort {

public:
    void sorting(std::vector<T>&);
    void quick(std::vector<T>&, const unsigned&, const unsigned&);
    unsigned counter;
};


template<class T>
void quickSort<T>::sorting(std::vector<T>& toSort)
{
    unsigned max = 0;
    max = (unsigned)(toSort.size()-1);
    quick(toSort, 0, max);

}

template<class T>
void quickSort<T>::quick(std::vector<T>& toSort, const unsigned& leftarg, const unsigned& rightarg)
{
  if (leftarg < rightarg) {

    T pivotvalue = toSort[leftarg];
    int left = leftarg - 1;
    int right = rightarg + 1;

  for(;;) {
      counter++;
    while (toSort[--right] > pivotvalue);
    while (toSort[++left] < pivotvalue);

    if (left >= right) break;

    T temp = toSort[right];
    toSort[right] = toSort[left];
    toSort[left] = temp;
  }

  T pivot = right;
  quick(toSort, leftarg, pivot);
  quick(toSort, pivot + 1, rightarg);
  }
}

最佳答案

leftarg是一个无符号的int。在quick()的第一次调用期间,它的值为0。如果再从中减去一个(int left = leftarg - 1),则该值溢出,并且得到UINT_MAX而不是-1。由于您使用left作为索引,并且UINT_MAX明显超出有效索引范围,因此会导致错误和分段错误。

我建议您熟悉C ++调试,并逐步在少量输入(例如5个值)上逐步执行代码,以更好地理解。

07-27 23:34