打卡Day12
学习内容 :排序优化：如何实现一个通用的、高性能的排序函数？
大部分排序函数都是采用 O(nlogn) 排序算法来实现，掌握这3个方面，就能实现一个工业级的通用的、高效的排序函数。
一、如何选择合适的排序算法
如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
2.为什选择快速排序？
1）线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。
2）为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。
3）同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。
二、何用优化快速排序
1.三数取中法
(1)从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。
(2)如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“五数取中”或者“十数取中”
2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。
3.警惕快排的递归发生堆栈溢出，有2中解决方法，如下：
(1)限制递归深度，一旦递归超过了设置的阈值就停止递归。
(2)在堆上模拟实现一个函数调用栈，手动模拟递归压栈出栈过程。
三、分析qsort()函数的底层实现原理
1.qsort() 会优先使用归并排序来排序输入数据，排序的数据量比较大的时候，qsort() 会改为用快速排序算法来排序。
2.在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长。
3.对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法。
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论