# 排序算法

![十大排序算法](https://firebasestorage.googleapis.com/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdzWW4gUJKke6s2odrw%2Fuploads%2FCmVzJbEscxGdnTrsnpnb%2Ffile.png?alt=media)

## 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。