正态分布数据的排序

已知数组中的数据大致符合正态分布，哪种排序算法的效率最高？

答案是最常用的快速排序。常用的其他排序算法，如堆排序、合并排序甚至冒泡排序等都和数据的分布无关，他们的性能更多的取决于数据的具体顺序。只有快速排序涉及到对分割点的猜测，猜测的好坏对算法的效率有较大的影响。

在正态分布的数据中随机取一个数字，我们有较高的概率得到比较居中的数字，这一点只要看一眼正态分布的图形便知。如果快速排序算法通过在数据中随机选择数字，会有比较高的概率得到一个比较好的分割点。这也解释了为什么快速排序理论上的复杂度比较高，而在实际中效果很好。