|
思路：
选出一个key，一般是最左边或是最右边的。定义一个begin和一个end，begin从左向右走，end从右向左走。在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。此时key的左边都是小于key的数，key的右边都是大于key的数将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
代码：
void QuickSort(int* arr, int begin, int end)
{
?? ?if (begin >= end)?//只有一个数或区间不存在
?? ??? ?return;
?? ?int left = begin;
?? ?int right = end;
?? ?
?? ?int keyi = begin;//选左边为key
?? ?while (begin < end)
?? ?{
?? ??? ?
?? ??? ?while (arr[end] >= arr[keyi] && begin < end)//右边选小?
?? ??? ??? ?--end;
?? ??? ?while (arr[begin] <= arr[keyi] && begin < end)//左边选大
?? ??? ??? ?++begin;
?? ??? ?swap(&arr[begin], &arr[end]);?//小的换到右边，大的换到左边
?? ?}
?? ?swap(&arr[keyi], &arr[end]);
?? ?keyi = end;
?? ?QuickSort(arr, left, keyi - 1);
?? ?QuickSort(arr,keyi + 1,right);
}
|