排序算法-快排

1. 快排基本特征：

• 时间复杂度：O(nlogn)
  最坏：O(n^2)
• 空间复杂度: O(nlogn)
• 不稳定排序

2. 描述：

快速排序是基于 分治模式 处理的；

• 思路：
  对于典型子数组A[p...r]排序的分治过程的三个步骤：
  1. 分解：
     A[p...r]被划分为两个子串A[p...q-1]和A[q+1...r]使得被划分的两个子串A[p...q-1]<=A[q]<=A[q+1...r]；
  2. 解决：
     通过递归调用排序，对子序列A[p...q-1]和A[q+1...r]排序；
  3. 合并。

3. 算法

4. 时间复杂度

快排的时间复杂度跟数据序列的初始位置和枢轴的选取有关。

• 最好情况：
  每趟排序把序列分成两个长度相近的子序列；
  比较次数为O(nlogn)，时间复杂度是（nlogn）

• 最坏情况：
  每趟排序将序列分成长度差异很大的两个子序列；
  例如：
  {1，2，3，4，5，6}
  1，{2，3，4，5，6}
  当数据已排序时，如选取序列的第一个值作为基准值（枢轴），那么每一趟排序得到的两个子序列都是长度分别为0和n-1
  这样必须经过n-1趟排序才能完成，因此比较次数为：
  c=Σ(n-i)= n(n-1)/2 = n^2/2
  基准值可以有多种选法，如可以选中间值。但是由于初始序列是随机的，所以无论如何选取基准值，都存在最坏情况。

• 快排是不稳定排序；

5. 快排改进

参考：
浅谈算法和数据结构: 四 快速排序
九大基础排序总结与对比
快速排序算法
8大排序算法图文讲解