7.6.2 内部排序算法的应用

(1)选取排序方法需要考虑的因素

1)待排序的元素数目n。

2)元素本身信息量的大小。

3)关键字的结构及其分布情况。

4)稳定性的要求。

5)语言工具的条件,存储结构及辅助空间的大小等。

(2)排序算法小结

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序较好。

2)若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。

3)若n较大,则应采用时间复杂度为O(nlog2N)的排序方法:快速排序、堆排序或归并排序。

快速排序被认为是目前基于比较的内部排序中最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短。堆排序所需的辅助空间小于快速排序,并且不会出现快速排序可能出现的最坏情况,这两种排序都是不稳定的。

若要求排序稳定且时间复杂度为O(nlog2N),则可采用归并排序。但从单个记录起进行两两归并的排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并。直接插入排序是稳定的,因此改良后的归并排序仍是稳定的。

4)在基于比较的排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于“比较”的排序算法,至少需要O(nlog2N)的时间。

5)若n很大,记录的关键字位数较少且可以分解时,采用基数排序较好。

6)当记录本身信号量较大时,为了避免消耗大量时间移动记录,可用链表作为存储结构。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之调整数组顺序使奇数位于偶数前面找(九度OJ1516)

题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和...

2256
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

1203
来自专栏赵俊的Java专栏

奇偶分割数组

1584
来自专栏蜉蝣禅修之道

算法考试填数字问题

2022
来自专栏数据结构与算法

23:二维数组回形遍历

23:二维数组回形遍历 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个row行col列的整数数组array,要求从array[0][0...

5096
来自专栏小小挖掘机

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包,它的部分功能如下: 1)ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

3184
来自专栏java工会

java冒泡排序和快速排序

3053
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

3484
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

982
来自专栏五分钟学算法

五分钟学会一个很有用的排序:归并排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

1794

扫码关注云+社区

领取腾讯云代金券