浅谈算法和数据结构 四 快速排序

上篇文章介绍了时间复杂度为O(nlgn)的合并排序，本篇文章介绍时间复杂度同样为O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。

快速排序是20世纪科技领域的十大算法之一 ，他由C. A. R. Hoare于1960年提出的一种划分交换排序。

快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。

本文首先介绍快速排序的思路，算法的实现、分析、优化及改进，最后分析了.NET 中列表排序的内部实现。

一 原理

快速排序的基本思想如下：

对数组进行随机化。

从数列中取出一个数作为中轴数(pivot)。

将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。

再对左右区间重复第三步，直到各区间只有一个数。

如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分，左边都小于这个中轴数，右边都大于该中轴数，然后对左右的子序列继续这一步骤直到子序列长度为1。

下面来看某一次划分的步骤，如下图：

上图中的划分操作可以分为以下5个步骤：

获取中轴元素

i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]

j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]

交换a[i]和a[j]

重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。