C++随机快速排序错误
我想实现快速排序算法,但不知何故我有一个错误,我只是不能fint它,我的randomizedPartition似乎工作正常。这是代码。C++随机快速排序错误
#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
你在randomizedPartition
指数应start + rand() % len
,不只是rand() % len
。
另外,作为一个附注,你的print
函数实际上并没有做你想要的。您希望它打印元素start
到end
,但它实际上是打印0
到end - start
。一般情况下,您的调试过程和您的编码过程会从试图保持干净和简单的事情中受益。这段代码现在有点乱,这使得它更难调试。
还没有运行它,但我认为这个修复会产生正确的答案。尽管如此,仍然无法实现快速排序。太多掉期 – user4581301
非常感谢,我唯一需要改变的就是那一个,现在一切正常。 –
@ user4581301,即使我有这些额外的掉期,运行时间仍然是线性的,因为这组掉期在恒定时间内执行。而且一旦我使用随机版本的最差情况qSort是n log(n) –
从来没有见过这样的快速排序。通常在循环中有一个交换,而不是两个交换,最后一个交换。 – user4581301
'srand'应该每个程序调用一次,通常在'main'的顶部,而不是重复。 srand重新生成随机数生成器。如果你不知道这意味着什么,或者你为什么不想这样做,[开始阅读](http://en.cppreference.com/w/cpp/numeric/random/srand)。 – user4581301
以上都不会解决你的bug(并且要小心,这要归功于使用命名空间标准;你可能不会调用你认为是的swap),所以我认为有人需要通过算法一个调试器。也许是你。 – user4581301