快速排序算法，一些特定输入序列的错误答案和分段错误

Question

我正在学习c++，对编程还比较陌生。我编写了一个C++程序，它使用最后一个元素作为轴心来实现快速排序算法。每当我试图执行它时，答案总是错误的，对于一些特定的输入序列，我会得到一个分段错误。

我试着玩while循环，把它改成"if"语句，看看是否发生了什么。结果有变化，但不正确。

//示例程序

#include <iostream>
using namespace std;
int partition(int a[],int l,int r)
{
//int l=0,r=p-1;
int p=r+1;
while(r>l)
{
while (a[l]<a[p])
{
l=l+1;
}
while(a[r]>a[p])
{
r=r-1;
}
//if(a[l]>a[r]){
int f=a[r];
a[r]=a[l];
a[l]=f;
//}
}
int k=a[l];
a[l]=a[p];
a[p]=a[l];
p=l;
return p;
}
void quicksort(int a[],int l,int r)
{
int p;
if (l<r){
p=partition(a,l,r);
quicksort(a,0,p-2);
quicksort(a,p+1,r);
}
}
int main(){
int k;
cout<<"enter the number of elements in array";
cin>>k;
int a[k];
for (int i=0;i<k;i++)
{
cin>>a[i];
}
//int p=k-1;
int l=0;
int r=k-2;
quicksort(a,l,r);
for (int i=0;i<k;i++)
{
cout<<a[i];
}
return 0;
}

实际结果：输入数组中的元素数4

301.2

排序结果1322

预期结果：0123

Answer 1

如果编译发布的代码时启用了警告，则会产生以下诊断：

程序cc:25:9：警告：未使用的变量'k'[-Wunused变量]int k=a[l]；^prog.cc:47:10:警告：可变长度数组是C99的一个特性[-Wvla扩展]int a[k]；^

第一个是由函数partition:中的一个拼写错误生成的

int k=a[l];
a[l]=a[p];
a[p]=a[l];  // <-- That should be 'a[p] = k;' to swap the values

当然，交换这两个值的正确方法应该是

std::swap(a[l], a[p]);

通过使用适当的数据结构(在C++中是std::vector，并将对它的引用传递给其他函数，而不是int *)，可以很容易地修复第二个警告。

这些并不是OP代码中唯一的问题，它似乎使用Lomuto分区方案实现了Quicksort算法的变体。

在OP的代码中，第一个调用类似于

quicksort(a, 0, k - 2); // k beeing the size of the VLA, it skips the last element

而使用vector并遵循通过其第一个元素和结束后的元素表示范围的惯例，我们可以将入口点写为

// Note that std::vector::size() returns an unsigned type
quicksort(a, 0, a.size());

从而使quicksort功能可以实现为

void quicksort(std::vector<int> &a, size_t low, size_t high)
{
if ( low < high) {
size_t p = partition(a, low, high);
quicksort(a, low, p);           // <- Note that OP's code uses '0' instead of 'low'
quicksort(a, p + 1, high);
}
}

如果我正确地猜测了OP试图实现的变体，那么分区函数可以简化(并固定)为

size_t partition(std::vector<int> &a, size_t low, size_t high)
{
size_t p = high - 1; // <- Assumes high > 0
size_t i = low;
for( size_t j = low; j < p; ++j )
{
if(a[j] < a[p]) {
std::swap(a[i], a[j]);
++i;
}
}
std::swap(a[i], a[p]);
return i;
}