快速排序

[1] 快速排序实例

幼儿园老师安排小朋友按照身高排成一列，最矮的小朋友站在最左侧，最高的小朋友站在最右侧，老师应该如何指示小朋友自动站好位置呢？

图片来源于网络

（1）第一个小朋友举起手，所有比这个小朋友矮的都站到他的左侧去，所有比这个小朋友高的都站到他的右侧。
（2）所有站到左侧的小朋友重复这一步骤，所有站到右侧的小朋友也重复这一步骤。

假设小盆友身高：{102, 100, 98, 95, 96, 99, 101, 97}

站队过程：
100，98，95，96，99，101，97，102
98，95，96，99，97，100，101，102
95，96，97，98，99，100，101，102

[2] 基本形式

对序列 L 进行排序时：
(1) 若 L 为空，则排序结果为空，这是边界情况。
(2) 否则，若 L 中任选一个元素作为基准，然后递归地将 L 中不大于基准的元素排序，将结果置于基准的左侧。同时递归地将所有大于基准的元素排序，将结果置于基准的右侧。

公式：

sort(L) = null ; L = null
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                      ++ [pivot] ++ 
                      sort [y | y <- rest, y >=pivot]

[3] Java 代码实现

2017-9-11

[4] 性能分析

（1）最好的情况：每次划分都能将序列均匀分成两段长度相同的子序列。

2017-9-11

递归深度 O（lg n）, 花费时间 O（ n lg n）.

(2) 最坏的情况：划分过程极不平衡，部分为0（1），另部分为0（n），则递归深度为0（n）,花费时间为0（n^2）.

如所有元素都相同
或序列有序

[5] 优化

（1）双向划分 ： i>=基准；j<=基准
（2）三分划分 ： 小于，等于，大于

[6] 总结

最近买了一本刘新宇的《算法新解》，以上的内容参考书中的多知识点，加上我自己的总结，感谢作者。
喜欢把复杂的算法通过现实中很简单的例子讲的让人觉得亲近。