C++ 快速排序代码说明
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11975214/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Quick sort code explanation
提问by Prakhar Mohan Srivastava
This is code that I came across implementing the quick sort algorithm. Can you please explain how the recursion works here?
这是我在实现快速排序算法时遇到的代码。你能解释一下递归是如何在这里工作的吗？
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
And please note, this is not homework.
请注意，这不是家庭作业。
回答by Analog File
Not sure what you mean with "explain how the recursion is working". But here you go:
不确定“解释递归是如何工作的”是什么意思。但是你去吧：
The function you posted takes an array of ints and two indexes. It will not sort the whole array, but only the part of it between the two indexes, ignoring anything that is outside them. This means the same function can sort the whole array if you pass the first and last indexes, or just a sub array if you pass a leftvalue that is not the index of the first element of the array and/or a rightvalue that is not the index of the last element.
您发布的函数采用整数数组和两个索引。它不会对整个数组进行排序，而只会对两个索引之间的部分进行排序，而忽略它们之外的任何内容。这意味着如果您传递第一个和最后一个索引，则相同的函数可以对整个数组进行排序，或者如果您传递的left值不是数组第一个元素的索引和/或right不是数组的第一个元素的值，则只是一个子数组最后一个元素的索引。
The sorting algorithm is the well known quicksort. The as pivot it uses the central element (it could as well have used any other element). It partitions the array into the less than (or equal to) pivotsubarray and the greater than (or equal to) pivotsubarray, leaving an element equal to the pivot between the two partitions.
排序算法是众所周知的快速排序。作为枢轴它使用中心元素（它也可以使用任何其他元素）。它将数组划分为less than (or equal to) pivot子数组和greater than (or equal to) pivot子数组，留下一个元素等于两个分区之间的主元。
Then it recursively calls itself to sort the two partitions, but only does it if it is necessary (hence the ifs before the recursive calls).
然后它递归调用自己对两个分区进行排序，但仅在必要时才这样做（因此在递归调用之前是 ifs）。
The implementation works, but is sub-optimal in many ways, and could be improved. Here are some possible improvements:
该实现有效，但在许多方面都不是最佳的，可以改进。以下是一些可能的改进：
- switch to another sorting algorithm if the array is sufficiently short
- chose the pivot value as median of three values(generally first, last and mid)
- initially move one pivot value out of the array (put it in first or last position and reduce the focus to the rest of the array) then change the tests to pass over values that are equal to the pivot to reduce the number of swapsinvolving them. You'll put the pivot value back in with a final exchange at the end. This is especially useful if you do not follow suggestion 2 and chose the firs/last element instead of the mid one as in this implementation.
- 如果数组足够短，则切换到另一种排序算法
- 选择枢轴值作为三个值的中位数（通常是第一个、最后一个和中间值）
- 最初将一个主元值移出数组（将其放在第一个或最后一个位置并将焦点减少到数组的其余部分）然后更改测试以传递等于主元的值以减少涉及它们的交换次数. 您将在最后进行最终交换时将枢轴值放回原处。如果您不遵循建议 2 并选择第一个/最后一个元素而不是本实现中的中间元素，这将特别有用。
回答by Illusionist
late reply but I just added some prints and it might help whoever comes across this understand the code.
迟到的回复，但我只是添加了一些打印件，它可能会帮助遇到此问题的人理解代码。
#include<iostream>
using namespace std;
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[abs((left + right) / 2)];
cout<<"pivot is"<<pivot<<endl;
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
cout<<"i and j are"<<i<<" "<<j<<"and corresponding array value is"<<arr[i]<<" " <<arr[j]<<endl;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
cout<<"entering first big while loop"<<endl;
for(int i=0;i<7;i++)
cout<<arr[i]<<" "<<endl ;
}
}
cout<<"recursion"<<endl;
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i< right)
quickSort(arr, i, right);
}
int main(){
int arr[7]= {2,3,8,7,4,9,1};
for(int i=0;i<7;i++)
cout<<arr[i]<<" " ;
quickSort(arr,0,6);
cout<<endl;
for(int i=0;i<7;i++)
cout<<arr[i]<<" " ;
int wait;
cin>>wait;
return 0;
}
回答by necromancer
Here is your answer -- in the common case both the recursive calls will be executed because the conditions above them will be true. However, in the corner case you could have the pivot element be the largest (or the smallest) element. In which case you have to make only one recursive call which will basically attempt the process one more time by choosing a different pivot after removing the pivot element from the array.
这是您的答案——在常见情况下，两个递归调用都将被执行，因为它们上面的条件为真。但是，在极端情况下，您可以将枢轴元素设为最大（或最小）元素。在这种情况下，您只需要进行一次递归调用，在从数组中删除主元元素后，通过选择不同的主元，基本上会再次尝试该过程。
