模板建站优点/网站建设报价单

快速排序是分治策略、迭代的典型示例，需要熟练掌握。

核心思想

将数组中所有元素都跟一个基准元素x比（随意选取，常取第一个或最后一个），比x小的划分成左边一块，比x大的划分成右边一块，得到两个子问题。然后递归处理这两个子问题即可。

其关键在于对数组的划分。

代码实现

下面是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都大于xreturn 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-1P(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的大小关系，还有了较大、较小之分。这就比蛮力两两对比（比如选择排序、插入排序、冒泡排序）节省了时间。

扩展资料：十大经典排序算法（动图演示）