应用最广泛的排序算法：1：适用于各种不同的输入数据且在一般应用中比其他算法都要快。
它是原地排序（只需一个很小的栈），且将数组排序的运行时间是NlogN级别。
主要缺点：非常脆弱。
快速排序与归并排序对比
1.都是一种分治的排序算法
2.归并是将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序
快排是当两个子数组都有序时，整个数组也就有序了。
3.归并是递归调用发生在处理数组之前，快排是发生在处理数组之后。
4.归并是稳定排序，快排不稳定
二 性能特点
简洁性：切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。归并排序和希尔排序一般比快速排序慢，其原因就是它们还在内循环移动数据。
比较次数很少。
基本实现有一个潜在的缺点：在切分不平衡时可能会极为低效。所以我们在快排前将数组随机排序。
总得来说，算法2.5的运行时间在1.39NlogN的某个常数因子的范围之内。归并排序也能做到这一点，但是快排一般会更快，因为它移动数据的次数更少。
三 算法改进
3.1 切换到插入排序
排序小数组用插入排序
3.2 三取样切分
使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要 计算中位数。
人们发现将取样大小设为3并用大小居中的元素切分的效果最好。
3.3 熵最优的排序
Dijkstra 三向切分的快速排序
对于只有若干不同主键的随机数组，归并排序的时间复杂度是线性对数的，而三向切分快速排序则是线性的。
答疑
1.随机地将数组打乱似乎占了排序用时的一大部分，这么做值得吗？
值得。这能够防止出现最坏情况并使运行用时可以预计。
2.为什么都将注意力放在重复元素上？
这个问题直接影响到实际应用中的性能，一些老的实现对含有大量重复元素的数组排序时用时超过平方级别。
网友评论