快速排序是分治策略、迭代的典型示例，需要熟练掌握。
核心思想
将数组中所有元素都跟一个基准元素x比（随意选取，常取第一个或最后一个），比x小的划分成左边一块，比x大的划分成右边一块，得到两个子问题。然后递归处理这两个子问题即可。
其关键在于对数组的划分。
quick_sort.gif
代码实现
下面是C++实现代码：
代码参考：常用算法之----快速排序
#include <iostream>
using namespace std;
//数组打印
void P(int a[],int n)
{
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
}
int quickSortPartition(int s[], int l, int r){
//Swap(s[l], s[(l + r) / 2]); //若以中间数为基准，则先将中间的这个数和第一个数交换即可
int i = l, j = r, x = s[l]; //将最左元素记录到x中
while (i < j)
{
// 从右向左找第一个<x的数
// 无需考虑下标越界
while(i < j && s[j] >= x)
j--;
if(i < j)
s[i++] = s[j]; //直接替换掉最左元素（已在x中存有备份）
// 从左向右找第一个>x的数
while(i < j && s[i] <= x)
i++;
if(i < j)
//替换掉最右元素(已在最左元素中有备份）
//最左元素一定被覆盖过，若没有，则表明右侧所有元素都>x，那么算法将终止
s[j--] = s[i];
}
s[i] = x; //i的位置放了x，所以其左侧都小于x，右侧y都大于x
return i;
}
void quickSort(int s[], int l, int r)
{
//数组左界<右界才有意义，否则说明都已排好，直接返回即可
if (l>=r){
return;
}
// 划分，返回基准点位置
int i = quickSortPartition(s, l, r);
// 递归处理左右两部分，i处为分界点，不用管i了
quickSort(s, l, i - 1);
quickSort(s, i + 1, r);
}
int main()
{
int a[]= {72,6,57,88,60,42,83,73,48,85};
//int a[]= {10,9,8,7,6,5,4,3,2,1};
P(a,10);
quickSort(a,0,9);//注意最后一个参数是n-1
P(a,10);
return 0;
}
这个版本算法的优点是，不用将某两个元素互换，一次移动直接将留有备份的元素覆盖。其实，从两头交替扫描就是为了一次挪一个，腾出来坑后再填下一个。
也可以从一头单向扫描，那时就需要交换俩元素位置。（参考《算法导论》第2版第七章快速排序）
《算法导论》中的快速排序伪代码，划分过程为单向扫描
复杂度分析
以比较运算作为基本运算，衡量其时间复杂度T(n)。
由于每次将原问题划分成两个规模减半的子问题，划分的额外工作量为O(n)，所以其递推公式为：
T(n) = 2 * T(n/2) + O(n)
T(1) = 0
根据主定理（或迭代、或递归树）可得，T(n) = O( nlog(n) )。（算法复杂度中的log默认指以2为底的log2）
快排为什么快（分治策略好在哪）
相比之下，选择排序、插入排序、冒泡排序等的时间复杂度均为O(n^2)。为什么采用分治策略的快速排序能将复杂度大大减小呢？分成两个子问题后节省了哪些时间呢？
因为划分后，两个子问题之间存在某种关系，这些信息节省了后续处理时间。
以快速排序算法为例，数组中所有元素都跟基准元素x比较后，比x小的划分成左边一块，比x大的划分成右边一块。
这样，虽然左右两部分元素没有直接对比（都只和x做了对比），但已经可以知道，x左侧的所有元素都小于右侧的。
一趟对比下来，每个元素不仅确定了和x的大小关系，还有了较大、较小之分。这就比蛮力两两对比（比如选择排序、插入排序、冒泡排序）节省了时间。
扩展资料：十大经典排序算法（动图演示）
网友评论