三、排序

排序这一研究领域在计算机科学中占有相当重要的地位,不仅仅是因为它有着广阔的应用场前景,其本身也具有理论研究意义。

排序的基本概念

对于文件而言,排序就是根据记录关键字值的递增或者递减关系将记录的次序进行重新排序,使得原来一组次序任意的记录转变为按其关键字值有序排列的一组记录。排序过程理解为一个按值无序的数据元素序列转换为一个按值有序排序的数据元素序列的过程。从小到大称为升序或者正序关系;从大到小称为逆序或者降序关系。排序又称为分类。排序能够作为提高查找时间效率的手段。

排序的分类

可以从不同观点角度将排序操作分为不同的种类。

1.内排序 和 外排序

根据排序过程中所使用的 内、外存储器情况的不同,可以将排序分为 内部排序 和 外部排序两大类。简称 内排序外排序
内排序是指,当参加排序的数量不大是,在排序过程中将全部信息存放在内存中处理的排序方法。当参加排序的数据量较大,以至于内存不足以依次存放全部信息,在排序过程中需要通过内存与外存之间的数据交换来达到排序目的,这种排序方式成为外排序
外排序的速度要比内排序的速度慢很多。

2.稳定性排序 和 非稳定性排序

通常把参加排序的项称为排序码或者排序项。对于具有同一排序码的多个记录而言,若采用的排序方法使得排序后记录的相对位置保持不变,则称此排序为稳定的,否则为不稳定的,相应的排序方法为稳定性排序方法 和 非稳定排序方法,这种特性是有用的。

3.连续顺序文件排序 和 链表排序

根据 文件在存储介质上的组织方式划分排序的种类,可以分为连续顺序文件排序 和 链表排序
连续顺序文件排序:由于记录之间的逻辑顺序是通过物理地址的先后来映射,因而在排序过程中需要移动记录的位置。
链表排序:文件中的一个记录对应着链表中的一个链结点,记录之间的逻辑顺序是通过指针来反映的,因而排序过程中不必移动记录,只需修改相应指针的指向。

内排序

内排序方法的种类很多,如果按照完成排序所需的工作量来划分,还可以将排序方法分为简单排序法、先进排序法、基数排序法3类。如果按照排序过程中采用的策略不同,还可以将排序归纳为插入排序、选择排序、交换排序、归并排序、基数排序几类。
内排序的方法虽然很多,但就其全面性而言,很难说哪一种或者哪一类方法最好,每一种方法都有它自己的优势和不足,使用者应该根据不同的环境和情况(如参加排序的序列数量的大小或者序列的初始状态等)选择较为合适的方法。

无论何种排序方法,衡量其性能的主要指标不外乎两个:其一、执行排序算法所需要的时间;另一个,执行排序算法所需要的附加空间。
对于前者,排序过程中要进行的基本动作包括:1、比较两个元素的大小,2、将元素从一个位置移动到另一个位置(采用链表排序时可以不必移动元素)。因此,排序的工作量取决于这两种动作的执行次数,尤其是前一个动作。

下面具体来介绍几种内排序方法

  1. 插入排序
  2. 选择排序
  3. 泡排序
  4. 谢尔排序
  5. 快速排序
  6. 堆积排序
  7. 二路归并排序
  8. 基数排序

各种内排序方法的比较

各种排序算法之间的比较主要从下面几个方面综合考虑。

  1. 算法的时间复杂度
  2. 算法的空间复杂度
  3. 排序稳定性
  4. 算法结构的复杂度
  5. 参加排序的数据规模
稳定性比较

插入排序、泡排序、二路归并排序、基数排序 方法是稳定排序方法。
选择排序、谢尔排序、快速排序、堆积排序 方法是不稳定排序方法。

复杂性比较

各种内排序算法的时间复杂度和空间复杂度如下表所列:

排序方法 平均时间 最坏情况 辅助空间
插入排序 O(n2) O(n2) O(1)
谢尔排序 O(nlog2n) O(nlog2n) O(1)
冒泡排序 O(n2) O(n2) O(1)
快速排序 O(nlog2n) O(n2) O(log2n)
选择排序 O(n2) O(n2) O(1)
堆积排序 O(nlog2n) O(nlog2n) O(1)
归并排序 O(nlog2n) O(nlog2n) O(n)
基数排序 O(d(n+r)) O(d(n+r)) O(n+r)

综上所述,得出如下结论:

  1. 在平均情况下,谢尔排序、快速排序、堆积排序、归并排序 都能达到较快的排序速度。进一步可知,快速排序最快。从空间消费来看,堆积排序最省。
  2. 在平均情况下,插入排序、冒泡排序方法的排序速度较慢,但当参加排序的序列开始就局部有序时,这两种排序方法能达到较快的排序速度。最好情况下,时间复杂度为O(n),比情况1中叙述的4种方法要好一些,而且这两种方法辅助空间消费较少。所以当n较小、或者序列开始就局部有序时,可选择这两种方法。多数情况下可以根据不同情况与1中的4种方法结合使用。
  3. 基数排序方法消费的空间较多,但其时间复杂度可简化成O(dn);当元素的位数较少时,可进一步简化成O(n), 在这种情况下也能达到较快的排序速度。另外,归并爱旭方法也需要的辅助空间较多。
  4. 从算法结构的简单性来看,插入排序法、选择排序法、冒泡排序法 比较简单和直接;而谢尔排序法、快速排序法、堆积排序法、归并排序法 都可以看做是对某一种排序法的进一步改进。相对而言,改进后的排序法所对应的算法可能都比较复杂。
  5. 从参加排序的数据序列的规模大小来看,n越小,采用简单排序方法就越合适;n越大,采用改进的排序方法越合适。这是因为n越小,n2与log2n的差距越小,并且简单排序方法的时间复杂度的系数均小于1(泡排序法的最坏情况以外),而改进后的排序方法的时间复杂度的系数均大于1,因而也使得他们之间的差距变小。

从上面的分析可以看到,很难说哪一个排序方法绝对好。每一种排序方法都有其优缺点,适合于在不同的环境下使用。因此在实际应用中,要根据具体情况选择合乎实际情况的方法。下面给出综合考虑以上几方面后所得出的大致结论,仅供在选择内排序方法是参考:

  1. 当参加排序的数据规模n较大,关键字元素分布比较随机,并且不要求排序稳定性时,宜选用快速排序法。
  2. 当参加排序的数据规模n较大,内存空间又允许,并且有排序稳定性要求,宜采用归并排序法。
  3. 当参加排序的数据规模n较大,元素分布可能出现升序或者逆序的情况,并且对排序稳定性不要求时,宜采用堆积排序方法或者归并排序方法。
  4. 当参加排序的数据规模n较小(如小于100),元素基本有序(升序),或者分布也比较随机,并且有排序稳定要求时,宜采用插入排序方法。
  5. 当参加排序的数据规模n较小,对排序稳定性又不要求时,宜采用选择排序方法。

向插入排序、选择排序、归并排序 都比较容易在链表上实现,避免将大量时间花费在元素的位置移动上。像快速排序、堆积排序就很难在链表上实现。

外排序

(待完成)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
禁止转载,如需转载请通过简信或评论联系作者。
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 196,397评论 5 462
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 82,585评论 2 373
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 143,521评论 0 325
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,645评论 1 267
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,489评论 5 358
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,366评论 1 274
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,787评论 3 387
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,432评论 0 255
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,732评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,775评论 2 314
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,550评论 1 326
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,393评论 3 315
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,802评论 3 300
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,036评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,324评论 1 253
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,757评论 2 342
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 40,958评论 2 336