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

Question

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

这是 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 上的伪代码(在您的代码中，j 中的 partition(..) 在维基百科文章中被称为 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

所以 <而不是 <= .