算法自学笔记:系统排序

发布时间:2023-10-14 15:00

排序算法在程序开发中有大量应用。有时是直接使用,如对音乐播单里的歌曲进行排序,有时是使用排序简化问题,如convex hull 问题中使用排序优化比暴力求解快很多,而有时是不明显的应用。

java语言提供了封装好的排序方法 Arrays.sort() 该方法接受基础数据类型和实现Comparable 或 Comparator的对象。其参数为要进行排序的数组,也可以加上指定的Comparator 该方法对于基础数据类型使用快速排序以提高速度,而对于对象进行归并排序以保证稳定性和保证nlogn时间下限。

三向切分快速排序被广泛用于C C++ java等多个语言内部封装的排序方法,这一排序法包括三向切分(和之前我们讲的狄克斯特拉三向切分差不多),不过这一方法选择基准值,避免时间复杂度提示为nlogn的方法不是通过把输入数组随机打乱,而是使用一个叫Tukey’s ninther的方法。

Tukey’s ninther方法首先在原数组里随机抽9个元素,并分成3组,取每一组的中位数元素。然后再取这三个中位数的中位数作为基准值。这样抽样可以保证得到的基准值位于数组中位数左右。这样相对于直接打乱可以节省一定时间,因为打乱数组,如使用Knuth’s shuffle, 需要遍历整个数组,而Tukey’s ninther只需要进行12次选取。

但是java系统排序也不是完全没有漏洞的,一些极端输入(在网课附件里有一个例子)会导致时间复杂度提升,这主要是Tukey’s ninther导致的失误,因而完全打乱数组才能保证百分比无差错。另外,如果数据量过大可能导致栈溢出(快速排序和归并排序依靠递归)。

现在已有的排序算法可能有上百种,除了常规对时间复杂度和空间复杂度的比较,选取合适的排序算法一般还会有以下考虑:
1 稳定性
2 出现较多相同键时的性能
3 最糟时间复杂度
4 对输入依赖
没有排序算法是完美的,而系统提供排序算法一般可以解决大多数情况

对之前介绍的排序算法比较
算法自学笔记:系统排序_第1张图片

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号