一、简介
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另外一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的.
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
二、步骤
在数组A中选取一个关键字,称之为枢轴(pivot),作用就是以这个枢轴为基准,把数组分为两部分,枢轴左边的值全部比枢轴的值小,右边比其小.一般选取数组中的第一个元素当作这个数组的枢轴,(当然,后面的可能枢轴是会发生变化的,例如上图中,如果再对a部分进行排序,枢轴就会变为a部分中元素的第一个).
设置两个变量i、j，排序开始的时候：i=0，j=n-1；(n待排序的部分的元素个数)
从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于枢轴的值A[j]，将A[j]和A[i]互换;(这里需要注意的是,交换完成之后直接跳到第四步,不会再去寻找第二个比枢轴的值小的元素,同时,要记住j的值是发生变化的).
从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于枢轴的A[i]，将A[i]和A[j]互换；
重复第三、四步，直到i=j；
(三,四步中，没找到符合条件的值，即三中A[j]不小于枢轴的值,4中A[i]不大于枢轴的值的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
三、示例
-
选原数组第一个元素为v，作为l端
- 数组分为v、<v、>v三部分，刚开始只有v一个元素，>v和<v的都没有元素
-
选<v的最后一个元素坐标为j
-
当前元素e的坐标为i，在>v元素的后面
-
<v的元素区间为[l+1...j]，>v的元素区间为[j+1...i-1]
-
如果e>v，则很简单，直接把该元素e放到紫色的>v的元素区间最后面，i往后移一个位置(i++)
-
如果e<v，则要把该元素e放到橙色的<v的元素区间最后面，即把该元素e与紫色的>v的头元素(a[j+1])进行交换，然后j往后移一个位置(j++)
-
i继续往后加1(i++)，考察下一个元素
-
最后遍历交换后数组分成三部分：v >v <v
-
最后还要把l位置的元素v与j位置的元素交换，交换后数组分成三部分：<v v >v
四、代码实现
#include <iostream>
using namespace std;
// 对arr[l...r]部分进行partition操作
// 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r){
T v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr[j] , arr[i] );
}
swap( arr[l] , arr[j]);
return j;
}
// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){
if( l >= r )
return;
int p = __partition(arr, l, r);
__quickSort(arr, l, p-1 );
__quickSort(arr, p+1, r);
}
template <typename T>
void quickSort(T arr[], int n){
__quickSort(arr, 0, n-1);
}
int main()
{
int a[10] = { 2,8,7,1,3,5,6,4,12,0 };
quickSort(a, 10);
for (int i = 0; i < 10; ++i) {
cout << a[i] << " ";
}
}
五、评价
时间复杂度：排序效率在同为O(NlogN)的几种排序方法中效率较高
应用场景：特别常用
