14、排序优化

思考：如何实现一个通用的、高性能的排序函数？

主要内容

如何选择合适的排序算法？

首先不考虑线性排序，虽然 O(n) 很诱人，但它们的适用场景太少了，所以放弃。
其次对小规模数据，可以使用 O(n2) 的；但对大规模数据就要考虑高效的 O(nlogn) 算法。
归并算法需要额外的内存，针对小数据时可以使用；而快排则不需要，常针对大数据使用

快速排序优化

快排的数据若已排序，那每次选择最后一个分区，则恶化为 O(n^2)
所以我们要合理选择分区点：尽量将数据平均分配在左右分区内

N 位数取中值法

比如：三位数取中值，从首、中间、尾取三个数，求中值最为分区点
若数据量大，则可以为“五位数、十位数”取中值

随机法

每次随机取分区点。随机比固定更容易出现好分区点

解答思考

各语言提供的排序函数，会存在根据数据量进行不同排序算法的处理。
比如：当数据量小时，会使用插入排序；当数据量大但内存少时，会使用归并排序，并且在递归到排序长度很小时，就停止递归采用插入排序；当数据量大内存也大，则使用快速排序

内容总结

不同的算法，有对应的场景。
所以各语言提供的排序函数，不会仅仅采用一种方式去实现，一定是竭尽所能的榨干性能

新的思考

JS 的数组 sort 函数使用的算法？

采用了插入、快排、归并这几种算法，会根据数据大小选择合适的或混用来实现排序