我的 quickSort() 程序不能正常工作，为什么？

Question

如果能帮到我，真的非常感谢！下面是我对数字向量（双精度类型）进行排序的代码。 vec中的元素个数为200,000.

程序在几秒钟后停在绿线处。错误信息是

"Thread 1: EXC_BAD_ACCESS (code = 2, address=0x7fff5f3fffd8)".

如图：

/*This is block to call quickSort*/
void VectorDoubleSort:: sort(std::vector<double>& vec){
      int start = 0;
      int end = vec.size() - 1;
      quickSort(vec, start, end);
}




/*This block to fulfill the quickSort method*/
    void VectorDoubleSort:: quickSort(std::vector<double>& vec, int start, int end)
    {
        int pivot = (start + end) / 2;
        int smallIndex = start;

        if (start < end) {
            double tempA = vec[start];
            vec[pivot] = tempA;

            for (int i = start + 1; i <= end; i++) {
                if (vec[i] <= vec[start]) {
                    smallIndex += 1;
                    double tempB = vec[i];
                    vec[i] = vec[smallIndex];
                    vec[smallIndex] = tempB;
                }
            }

            double tempC = vec[start];
            vec[start] = vec[smallIndex];
            vec[smallIndex] = tempC;

            pivot = smallIndex;

            quickSort(vec, start, pivot - 1);
            quickSort(vec, pivot + 1, end);
        }
    }

Answer 1

首先这里是错误的：

int pivot = (start + end) / 2;
double tempA = vec[start];
vec[pivot] = tempA;

你丢失了 vec[pivot] 的内容，然后在这里 if (vec[i] <= vec[start]) 你按 vec[start] 的值排序向量，然后 pivot 开始，那到底为什么，您将枢轴设置为 (start + end) / 2;？当你在比较中使用 NOT 保存值，但从 vec[start] 重新读取它，可以通过 vector 中的 swap 操作来更改。毕竟你针对 start 进行了排序，但是你的索引在排序周期 for (int i = start + 1; i <= end; i++) 中增加了，所以在迭代之后你有（当然，如果以前的错误已修复）： {pivot, sub array <= pivot, sub array > pivot}，所以如果从 end 到 start + 1 做索引，你需要移动 [ 而不是 swap =22=] 到 start 并插入 pivot 之间，因此，如果尽可能多地重用您的代码，正确的解决方案将是：

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <vector>

namespace VectorDoubleSort {
void sort(std::vector<double> &vec);
void quickSort(std::vector<double> &vec, int start, int end);
}

void VectorDoubleSort::sort(std::vector<double> &vec) {
  if (vec.empty())
    return;
  int start = 0;
  int end = vec.size() - 1;
  quickSort(vec, start, end);
}

/*This block to fulfill the quickSort method*/
void VectorDoubleSort::quickSort(std::vector<double> &vec, int start, int end) {
  if (start < end) {
    const double pivotVal = vec[start];
    int smallIndex = end;

    for (int i = end; i > start; --i) {
      if (vec[i] >= pivotVal) {
        std::swap(vec[i], vec[smallIndex]);
        --smallIndex;
      }
    }
    std::swap(vec[start], vec[smallIndex]);

    const int pivot = smallIndex;
    quickSort(vec, start, pivot - 1);
    quickSort(vec, pivot + 1, end);
  }
}

bool test(const std::vector<double> &arr) {
  std::vector<double> good = arr;
  std::sort(good.begin(), good.end());
  std::vector<double> my = arr;
  VectorDoubleSort::sort(my);
  std::copy(my.begin(), my.end(),
            std::ostream_iterator<double>(std::cout, ", "));
  std::cout << "\n";
  return my == good;
}

int main() {
  assert(test({}));
  assert(test({3., 1., 2., 17., 18., -1., -5.}));
  assert(test({3., 1., 2.}));
  assert(test({3., 2.}));
  assert(test({3.}));
  assert(test({3., 532523, 5235, 05325, 535, 5738157, 535, 501, 9780, 14}));
}

注意： 我使用 c++11(initializer_list)，但仅用于测试，因此如果没有测试，您可以重复使用 c++98 或 c++03

我的 quickSort() 程序不能正常工作，为什么？

My quickSort() program cannot work well, why?

c++

sorting

algorithm

debugging

quicksort