我不明白它在哪里溢出。5 个元素 [2 3 9 2 2] 的数据的输出是 [7208668 3 2 2 9] 而不是 [2 2 2 3 9]。
这个分区是从另一个函数调用的,该函数选择一个随机枢轴并调用这个分区函数。它需要这个分区函数的输出递归地调用它自己的函数来执行快速排序。
编辑:这里的 swap() 是 C++ 库中的一个内置函数。
int partition(int arr[], int l, int h){
int i = l;
int j = h;
int p= l;
int q = h;
int pivot = arr[0];
while(i<j){
while(arr[i]<pivot){
i++;
}
while(arr[j]>pivot){
j--;
}
swap(arr[i],arr[j]);
if(arr[i]==pivot){
p++;
swap(arr[i], arr[p]);
}
if (arr[j]==pivot){
q--;
swap(arr[j],arr[q]);
}
}
swap(arr[j], arr[l]);
int t = i-1;
for(int s = l; s<p; s++,t--){
swap(arr[s],arr[t]);
}
i++;
for(int s = h-1; s>q; s--, i++){
swap(arr[s],arr[q]);
}
return j;
}