今天来学一下排序优化。如何实现一个通用的、高性能的排序函数?
如何选择合适的排序算法
时间复杂度 | 稳定排序 | 原地排序 | |
---|---|---|---|
冒泡排序 | \(O(n^2)\) | 是 | 是 |
插入排序 | \(O(n^2)\) | 是 | 是 |
选择排序 | \(O(n^2)\) | 否 | 是 |
快速排序 | \(O(nlogn)\) | 否 | 是 |
归并排序 | \(O(nlogn)\) | 是 | 否 |
桶排序 | \(O(n)\) | 是 | 否 |
计数排序 | \(O(n+k)\) k是数据范围 | 是 | 否 |
基数排序 | \(O(dn)\) d是维度 | 是 | 否 |
这里计数排序和基数排序的时间复杂度为什么是\(O(n+k)\)和\(O(dn)\)?
线性排序算法的时间复杂度比较低,适用场景比较特殊。如果要写一个通用的排序函数,不能选择线性排序算法。
如果对小规模数据进行排序,可以选择时间复杂度是\(O(n^2)\)的算法;如果对大规模数据进行排序,时间复杂度是\(O(nlogn)\)的算法更加高效。所以,为了兼顾任意规模数据的排序,一般都会首选时间复杂度是\(O(nlogn)\)的排序算法来实现排序函数。
时间复杂度是\(O(nlogn)\)的排序算法不止一个,除了快速排序和归并排序,还有堆排序。堆排序和快速排序都有比较多的应用。比如Java
语言采用堆排序实现排序函数、C
语言采用快速排序实现排序函数。
快速排序在最坏情况下的时间复杂度是\(O(n^2)\),而归并排序可以在平均情况、最坏情况下的时间复杂度都是\(O(nlogn)\),但是由于归并排序并不是原地排序算法,空间复杂度是\(O(n)\),因此没有得到广泛应用。
如何优化快速排序
如果数据本身就是有序或者接近有序的,每次分区点选择最后一个数据,那么快速排序算法时间复杂度就会退化成\(O(n^2)\)。这种情况的出现的主要原因是分区点选的不够合理。
最理想的分区点:被分区点分开的两个分区中,数据的数量差不多。
三数取中法
从区间的首、尾、中间,分别取出一个数,然后对比大小,取这3个数的中间值作为分区点。这样每间隔某个固定的长度,取数据出来比较,将中间值作为分区点的分区算法,肯定要比单纯取某一个数据更好。但是,如果要排序的数组比较大,那“三数取中”可能就不够了,可能要“五数取中”或者“十数取中”。
随机法
随机法就是每次从要排序的区间中,随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好,但是从概率的角度来看,也不大可能出现每次分区点都选得很差,所以,平均情况下,这样选的分区点是比较好的。时间复杂度退化为\(O(n^2)\)的情况,出现的可能性不大。
快速排序是用递归来实现的,递归要警惕堆栈溢出。
举例分析排序函数
C
运行库Glibc
中的qsort()
函数举例说明。
qsort()
会优先使用归并排序来排序输入数据。因为归并排序的空间复杂度是\(O(n)\),对于小数据量的排序,比如1KB、2KB等,归并排序需要的空间可以忽略。
但如果数据量太大,比如说100MB,qsort()
会改为快速排序算法来排序。qsort()
选择分区点的方法就是“三数取中法”。对于递归太深会导致堆栈溢出的问题,qsort()
是通过自己实现一个堆上的栈,手动模拟递归实现的。
实际上,qsort()
并不仅仅用到了归并排序和快速排序,还用到了插入排序。在快速排序的过程中,当要排序的区间中,元素的个数小于等于4时,qsort()
就会退化为插入排序,不再继续使用递归来做快速排序。
在小规模数据中,\(O(n^2)\)时间复杂度的算法并不一定比\(O(nlogn)\)的算法执行时间长。
算法的性能可以通过时间复杂度来分析,但是,这种复杂度分析是比较偏理论的,实际上时间复杂度并不等于代码实际的运行时间。
时间复杂度代表的是一个增长趋势,如果画成增长曲线,会发现\(O(n^2)\)比\(O(nlogn)\)增长趋势更猛一些,但是,在大O
复杂度表示法中,会忽略低阶、系数和常数。也就是说,\(O(nlogn)\)在没有省略低阶、系数、常数之前可能是\(O(knlogn+c)\),而且k
和c
有可能还是一个比较大的数。
对于小规模数据的排序,\(O(n^2)\)的排序算法并不一定比\(O(nlogn)\)排序算法执行的时间长。对于小数据量的排序,选择比较简单、不需要递归的插入排序算法。
同时,qsort()
排序算法中还通过哨兵来简化代码、提高执行效率。
看来,一个优秀的源码是把各种细节做到了极致。不仅仅用到了三种排序算法,还考虑到递归潜在风险,通过手动实现堆来模拟递归以及哨兵模式。真的赞。
课后思考
所熟悉的语言中的排序函数都是用什么排序算法实现的?有哪些优化技巧?
Python
中列表排序是在CPython
中listobject.c
来实现的。说明文档:listsort.txt。