中国建设造价工程协会网站,建站公司见客户没话说,设计网名昵称,湖南省城乡建设厅网站文章来源于极客时间前google工程师−王争专栏。 几乎所有的编程语言都会提供排序函数#xff0c;比如java中的Collections.sort()。在平时的开发中#xff0c;我们都是直接使用#xff0c;这些排序函数是如何实现的#xff1f;底层都利用了哪种排序算法呢#xff1f;
问题… 文章来源于极客时间前google工程师−王争专栏。 几乎所有的编程语言都会提供排序函数比如java中的Collections.sort()。在平时的开发中我们都是直接使用这些排序函数是如何实现的底层都利用了哪种排序算法呢
问题如何实现一个通用的、高性能的排序函数
如何选择合适的排序算法 线性排序算法时间复杂度比较低使用场景比较特殊。所以如果要写一个通用的排序函数不能选择线性排序算法。
对于小规模数据进行排序可以选择O(n^2)的算法如果对大规模数据进行排序O(nlogn)的算法更加高效。所以为了兼顾任意规模数据的排序一般都会首选时间复杂度为O(nlogn)的算法。
O(nlogn)的排序算法有归并排序、快速排序、还有堆排序。快排和堆排都有比较多的应用比如java语言采用堆排序实现排序函数c语言使用快排实现排序函数。
快排比较适合来实现排序函数但是快排在最坏情况下时间复杂度为O(n^2)如何来解决这个“复杂度恶化”的问题呢
如何优化快速排序
时间复杂度退化为O(n2)的原因是数据原来就是有序的或者接近有序的每次分区点都选择最后一个数据。**实际上这种O(n2)时间复杂度出现的主要原因还是因为我们分区点选的不够合理。**
最理想的分区点是被分区点分开的两个分区中数据的数量差不多。
为了提高排序算法的性能我们也要尽可能地让每次分区都比较平均。
比较常用、简单的分区算法
1.三数取中法
从区间的首、尾、中间取出一个数然后对比大小取这3个数的中间值作为分区点。如果排序的数组比较大那么“三数取中”可能就不够了可能要“五数取中”或者“十数取中”。
2.随机法
从排序区间中随机选择一个元素作为分区点。
快排是用递归来实现的。递归要警惕堆栈溢出。
限制递归深度设定阈值超过就停止递归。堆上模拟实现一个函数调用栈手动模拟递归压栈、出栈过程这样就没有了系统栈大小的限制。
举例分析排序函数
C语言中的qsort()函数。源码解析
qsort()优先使用归并排序来排序输入数据归并排序空间复杂度为O(n)对于小数据量的排序比如1KB、2KB等归并排序额外需要1KB、2KB的内存空间问题不大。空间换时间思想。
如果数据量太大比如100MB归并排序就不合适了。所以当数据量比较大的时候qsort()会改用快速排序算法来排序。qsort()选择分区点的方法就是“三数取中法”
递归太深导致堆栈溢出的问题qsort()通过自己实现一个堆上的栈手动模拟递归来解决。
qsort()不仅仅用到了归并排序和快速排序它还用了插入排序。排序过程中当要排序的区间中元素的个数小于等于4qsort()就退化为插入排序不再继续用递归来做快速排序。在小规模数据面前O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。
复杂度分析比较偏理论深究的话实际上时间复杂度并不等于代码实际的运行时间。
如果不省略低阶、系数和常数。O(nlogn) O(knlognc)
假设K1000c200当我们对小规模数据n100排序n^2实际上比Knlognc还要小。
knlognc 1000 * 100 * log100 200 远大于 10000n^2 100*100 10000
qsort()插入排序的算法实现中使用哨兵编程技巧虽然哨兵可能只是少做一次判断但毕竟排序函数是非常常用、基础的函数性能优化要做到极致。
总结
大部分排序函数都是采用O(nlogn)排序算法实现但是为了尽可能提高性能会做很多优化。
排序中的优化策略比如合理选择分区点、避免递归太深等。
思考
学习Arrays.sort()源码
