使用快速排序排序不会给出排序数组

Question

我在 C++ 开始学习算法并一直坚持到 Quicksort。但是我无法在我的代码中找到未正确排序数组的错误。

这里是 link 到 code 或者这里是代码：

#include <iostream>
using namespace std;

void printArray(int array[], int len) {
  for (int i = 0; i < len; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

void swap(int* a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int arr[], int lo, int hi) {
  int pivot = arr[hi];
  int i = lo - 1;
  for (int j = lo; j < hi-1; j++) {
    if (arr[j] <= pivot) {
        i +=1;
        swap(&arr[i], &arr[j]);
    }
  }

  swap(&arr[i+1], &arr[hi]);
  return i+1;
  }

  void quicksort(int arr[], int lo, int hi) {
    if (lo < hi) {
      int p = partition(arr, lo, hi);
      quicksort(arr, lo, p-1 );
      printArray(arr, 8);
      quicksort(arr, p + 1, hi);
    }
  }

 int main() {
   int len;
   int array[] = {2,8,7,1,3,5,6,4};
   len = (sizeof(array)/sizeof(array[0]));
   quicksort(array, 0, len-1);
   printArray(array, len);
   return 0;
 }

我正在打印数组元素，以便我可以看到数组元素的行为。

Answer 1

您的实现看起来非常接近 Wikipedia 上的伪代码（在您的代码中 partition(..) 中的 j 在维基百科文章中被称为 i 并且 i 在您的代码中，名称为 storeIndex)

但是有两个区别，其中之一至少会导致算法在您的示例中失败：

for (int j = lo; j < hi-1; j++)

应该是

for (int j = lo; j <= hi-1; j++)

维基百科文章说 for i from lo to hi−1, inclusive 因此 <= 而不是 <。

另一个区别是你的代码中有

if (arr[j] <= pivot)

而维基百科文章有

if A[i] < pivotValue

所以 < 而不是 <= .

Answer 2

请更改您的 for 循环：

for (int j = lo; j < hi-1; j++)

到

for (int j = lo; j < hi; j++)

或

for (int j = lo; j <= hi-1; j++)

原因是数组必须从 lo 到 hi（包含）。

但是，在您的尝试中，它只用了

{lo, low+1, ..., hi-1}

而不是

{lo, low+1, ..., hi-1, hi}

使用快速排序排序不会给出排序数组

Sorting using quicksort doesn't give sorted array

c++

sorting

quicksort