C++ 随机快速排序错误

Question

我正在尝试实现快速排序算法，但不知何故我遇到了一个错误，我就是找不到它，我的 randomizedPartition 似乎工作正常。这是代码。

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int  randomizedPartition(int *v, int start, int end);
void quickSort(int *v, int start, int end);
void swap(int *p, int *q);
void print(int *v, int len);

int main(int argc, char const *argv[]) {

  cout << "QUICK SORT:\n" << endl;
  int v[]      = {6, 4, 7, 3, 0, 1 , 2, 9, 19};
  int len = sizeof(v)/sizeof(int);

  cout << "Before Sorting: " << endl;
  print(v, len);
  cout << "After Sorting: " << endl;
  quickSort(v, 0, len - 1);
  print(v, len);

  return 0;
}

int  randomizedPartition(int *v, int start, int end) {
    int len = (int) abs(end - start + 1);
    srand (time(NULL));
    int idx      = rand() % len;
    cout << "IDX RD: " << idx << endl;
    int pivot    = v[idx];
    swap(&v[start], &v[idx]);

    int i = start - 1;
    int j = start;

    for (int posi = start + 1; posi <= end; ++posi) {
      if(v[posi] <= pivot) {
        ++i;
        ++j;
        swap(&v[posi], &v[i]);
        swap(&v[posi], &v[j]);
      }
    }

    cout << "Pivot: " << pivot << endl;
    cout << "Pivot Index: " << (i + 1) << endl;
    return ++i;
}

void quickSort(int *v, int start, int end) {
    if (start < end) {
      int idx = randomizedPartition(v, start, end);
      print(v, end - start + 1);
      cout << "Start: " << start << endl;
      cout << "End: " << end << endl;
      cout << "idx - 1: " << idx - 1 << endl;
      cout << "idx + 1: " << idx + 1 << endl;
      quickSort(v, start, idx - 1);
      quickSort(v, idx + 1, end);
    }
}

void print(int *v, int len) {
  for (int i = 0; i < len; ++i) {
    cout << *(v + i) << " ";
  }
  cout << "\n" << endl;
}

void swap(int *p, int *q) {
  int temp = *p;
  *p = *q;
  *q = temp;
}

谁能帮我找出错误？这是可能的输出之一：

Before Sorting: 
6 4 7 3 0 1 2 9 19 

After Sorting: 
IDX RD: 2
Pivot: 7
Pivot Index: 6
4 6 3 0 1 2 7 9 19 

Start: 0
End: 8
idx - 1: 5
idx + 1: 7
IDX RD: 5
Pivot: 2
Pivot Index: 2
0 1 2 6 3 4 

Start: 0
End: 5
idx - 1: 1
idx + 1: 3
IDX RD: 1
Pivot: 1
Pivot Index: 1
0 1 

Start: 0
End: 1
idx - 1: 0
idx + 1: 2
IDX RD: 2
Pivot: 2
Pivot Index: 3
0 1 6 

Start: 3
End: 5
idx - 1: 2
idx + 1: 4
IDX RD: 1
Pivot: 1
Pivot Index: 4
0 3 

Start: 4
End: 5
idx - 1: 3
idx + 1: 5
IDX RD: 1
Pivot: 3
Pivot Index: 7
0 9 

Start: 7
End: 8
idx - 1: 6
idx + 1: 8
0 9 6 2 1 4 7 3 19

Answer 1

您在 randomizedPartition 中的索引应该是 start + rand() % len，而不仅仅是 rand() % len。

此外，作为旁注，您的 print 函数实际上并没有按照您的意愿执行。您希望它打印元素 start 到 end，但它实际上打印的是 0 到 end - start。总的来说，您的调试过程和编码过程会受益于保持事情的简洁明了。现在的代码有点乱，这使得调试变得更加困难。

C++ 随机快速排序错误

C++ Randomized Quick Sort Bug

c++

sorting

algorithm

quicksort