C++随机快速排序错误

Question

我想实现快速排序算法，但不知何故我有一个错误，我只是不能fint它，我的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。一般情况下，您的调试过程和您的编码过程会从试图保持干净和简单的事情中受益。这段代码现在有点乱，这使得它更难调试。