专栏首页用户画像7.6.2 内部排序算法的应用

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 条评论
登录 后参与评论

相关文章

  • 排序算法 归纳总结

    一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

    week
  • 7.6.1 内部排序算法的比较

    1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

    week
  • 7.7.1外部排序

    内部排序都是在内存中进行的,而在实际应用中,经常需要对大文件进行排序,因为文件中的记录很多、信号量庞大,无法将整个文件拷贝进内存中进行排序。因此,需要将待排序的...

    week
  • 算法:选择排序(SelectionSort)

    每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

    WEBJ2EE
  • 排序算法图解(插入、选择、冒泡、快速、合并、希尔等等)

    老梁
  • 什么是基数排序?

    老读者可能比较熟悉,刚开始的时候写了一个排序算法系列,把常见的排序算法都写了,有兴趣的可以在公众号内的目录菜单栏中选择数据结构与算法查看。

    用户1260737
  • 《常见排序算法》

    1.概述 常见的排序算法,虽然很基础,但是很见功力,如果能思路清晰,很快写出来各个算法的代码实现,还是需要花一点功夫的,今天,就跟大家盘点下常用的一些算法。 冒...

    企鹅号小编
  • 排序算法(1)---基本概念

    排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间、买东西会按照销量排序、查找文件会按照最近修改时间排...

    逆月翎
  • 8大排序算法图文讲解

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    昱良
  • 十大经典排序算法 -- 动图讲解

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    互扯程序

扫码关注云+社区

领取腾讯云代金券