排序算法

十大排序算法

JS中Array.prototype.sort的排序方式

对于 JS 来说，数组长度大于 10 会采用快速排序，否则使用插入排序。选择插入排序是因为虽然时间复杂度很差，但是在数据 量很小的情况下和 O(N * logN) 相差无几，然而插入排序需要的常数时间很小，所以相对别的排序来说更快。

性能

1. 快速排序在完全无序的情况下效果最好，时间复杂度为O(nlogn)，在有序情况下效果最差，时间复杂度为O(n^2)。

2. 外部排序常用的算法是归并排序。

3. 数组元素基本有序的情况下，插入排序效果最好，因为这样只需要比较大小，不需要移动，时间复杂度趋近于O(n)。

4. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用堆排序方法最快。

5. 对长度为 n 的线性表作快速排序，在最坏情况下，比较次数为 n(n-1)/2。