|
快速排序法（Quick Sort）是剑桥大学教授在读大学时发明的排序算法，也是当今使用最广泛的高效排序算法之一。QuickSort思路直观而精巧，值得我们反复吟唱 算法动画演示 
基本思想 对于从小到大排好序的数列中的任何一个元素，我们可以说： 这个数前面的所有数都不比它大 这个数后面的所有数都不比它小
反过来， 是不是也成立？ 对于序列中的一个数， 如果： 这个数前面的所有数都不比它大 这个数后面的所有数都不比它小
那么： 这个数已经放在从小到大的升序数列中的最终的正确位置了。
快速排序法就是用这个直观的事实来给数组中的每一个数字排序。 我们来看个例子： 现在有9个数字 [ 31 2 7 48 4 10 17 52 61 ], 我们任意选取一个数字17，下面来确定17的位置。 
17现在位于数组的第5位，也是整个数组排序后的最终位置：
在QuickSort中： 任意选取的这个数字（17）叫做“基准”（pivot）。 所有元素比基准pivot值小的摆放在基准pivot前面，比基准pivot值大的摆在基准pivot的后面（相同的数可以到任一边）。这样该基准pivot就处于数列的最终正确位置上。这个操作称为分区（partition）
分区操作结束后，原来的数组被分割为2个小数组。 3 在这2个小数组上分别用递归（recursive）的办法来重复同样的操作（pivot， partition）。 
Partition算法实现 现在有长度为9的整数数组，我们选取第一个元素做为pivot。同时创建两个“指针”变量，一个指向数组的头，一个指向数组的尾巴。
j向左移动，直到遇到小于pivot(10)的数。 
把这个值（4）放到i指向的位置 
然后i向右移动，直到遇到大于pivot(10)的数 
把这个值（61）放到j指向的位置
反复重复以上1-4步骤，那么： i和j最后一定会相遇 i左边的数字都比pivot(10)小 j右边都数字都比pivot(10)大
那么：
没有代码的实现都是耍流氓 现在我们来看看代码实现。先定义一个函数partition，然后声明2个变量来记录头尾的位置， 同时声明一个变量来记录pivot的值。
下面是partition的逻辑：
从右到左移动“指针”变量j，找到第一个小于pivot的值
从左到右移动“指针”变量i，找到第一个大于pivot的值
最后来实现QuickSort的第3步：
在Partition后产生的2个小数组上分别用递归（recursive）的办法来重复同样的操作（pivot， partition）
算法复杂度 每次pivot-partition的时间复杂度为O(n). 逐渐递归划分更小的范围内进行pivot-partition。在最终排序完毕前，每次二分划分，一共划分了logn次，故快速排序时间复杂度为O(nlogn)。
这里我们来解释一下为什么QuickSort比冒泡排序法快。 两个算法都需要扫描整个数列来确定一个数据的最终位置。 但是冒泡排序法每次只能挑出最大的数字，放在最终的位置，而QuickSort不仅把pivot放到正确的位置，同时附带按大小做了简单的分类（比pivot小，比pivot大），每次扫描数列后保留了和排序有关的更多的信息。
算法系列： 10大常见排序算法（1） 冒泡
算法系列： 10大常见排序算法（2） 选择排序
算法系列： 10大常见排序算法（3）插入排序
算法系列： 10大常见排序算法（4）希尔排序
|
