c++ - 迭代快速排序方法的分区算法问题

Question

原始问题的简短版本:我正在尝试转换此示例:http://programmertech.com/program/cpp/quick-sort-recursive-and-iterative-in-c-plus-plus迭代快速排序使用 vector 而不是数组并开始简化一些事情。本来直接转换失败了，所以我试着一行一行地看，以便更好地理解，但是我的逻辑卡住了，坏了。

编辑:删除了问题中的所有内容，提供了我正在尝试的最小(不太有效)示例。这是我到目前为止的一切。我已经在纸上手工解决了这个问题，但我接触得越多，情况就越糟糕，现在陷入了无限循环(最初排序不正确)。

这是我的想法:getMedian 正如我所写的那样，它应该交换枢轴值以及左右值，以便它们有序:left <= med <= right 。当我们进入 partition 算法中的 while (right > left) 循环时，它应该不断交换元素以将所有大于主元的元素放在它的右边, 以及左边较少的那些。堆栈跟踪仍然需要分区的 Sub(vectors)(在本例中)。但这似乎不起作用。我觉得我好像错过了一些对这项工作非常重要的东西。

#include <iostream>
#include <vector>

class QuickSort {
public:
    QuickSort(std::vector<int> toBeSorted) : toBeSorted(toBeSorted) {}
    void sortVector();
    void print();
private:
    int partition(int left, int right);
    int getMedian(int left, int right);

    std::vector<int> toBeSorted;
};

// Iterative method using a stack
void QuickSort::sortVector() {
    int stack[toBeSorted.size()];
    int top = 0;
    stack[top++] = toBeSorted.size() - 1;
    stack[top++] = 0;

    int left, right, pivIndex;

    while (top > 0) {
        // Popping values for subarray
        left = stack[--top];
        right = stack[--top];
        pivIndex = partition(left, right);

        if (pivIndex + 1 < right) {
            stack[top++] = right;
            stack[top++] = pivIndex+1;
        }

        if (pivIndex - 1 > left) {
            stack[top++] = pivIndex-1;
            stack[top++] = left;
        }
    }
}

int QuickSort::partition(int left, int right) {
    int pivotValue = getMedian(left, right);

    if (right - left > 1) {
    while (right > left) {
        while (toBeSorted[left] < pivotValue) { left++; }
        while (toBeSorted[right] > pivotValue) { right--; }

        if (toBeSorted[right] < toBeSorted[left]) {
            std::swap(toBeSorted[right], toBeSorted[left]);
            left++;
            right--;
        }
    }
    } else {
        if (toBeSorted[right] < toBeSorted[left]) {
            std::swap(toBeSorted[right], toBeSorted[left]);
        }
    }
    return 0;
}

int QuickSort::getMedian(int left, int right) {
    int med = (right - left)/2;
    // if there are an even number of elements, instead of truncating
    // goto the rightmost value.
    if ((right - left)%2 != 0) {
        med = (right-left)/2 + 1;
    }

    // Organise the elements such that 
    // values at indexes: left <= med <= right.
    if (toBeSorted[med] < toBeSorted[left]) {
        std::swap(toBeSorted[left], toBeSorted[med]);
    }
    if (toBeSorted[right] < toBeSorted[left]) {
        std::swap(toBeSorted[left], toBeSorted[right]);
    }
    if (toBeSorted[right] < toBeSorted[med]) {
        std::swap(toBeSorted[right], toBeSorted[med]);
    }

    return toBeSorted[med];
}

void QuickSort::print() {
    for (int i = 0; i != toBeSorted.size(); i++) {
        std::cout << toBeSorted[i] << ",";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> values = {5, 8, 7, 1, 2, 5, 3};
    QuickSort *sorter = new QuickSort(values);
    sorter->sortVector();
    sorter->print();
    return 0;
}

Answer 1

在partition 方法中，您不应该在每次迭代中都swap(data[low], data[high])。你的错误是这部分。你可以这样做:

void partition(int left, int right) {
  // listOfNums is a vector
  int middle = getMidPiv(left, right);
  int low = left;
  int high = right-1;

  while (low < high) {
    while (listOfNums[low] < middle) {
      lower++;
    }

    while (listOfNums[high] > middle) {
      high--;
    }

    if (low < high) {
       swap(data[low], data[high]);
       low++;
       high--;
    }
  }

  // swap(data[low], data[high]); it is incorrect
  return low;
}