`

【排序结构5】 基于比较的内部排序总结

阅读更多

★ 基于“比较”操作的内部排序性能大PK

 

我们首先总结一下《排序结构专题1-4》中的十种方法的性能((N个关键字的待排序列)):

排序方法        平均时间   最坏时间  
辅助存储空间   稳定性  
直接插入排序
O(N^2) 
O(N^2)  
O(1)          
    √     
折半插入排序 O(N^2) O(N^2)
O(1)
    √
希尔排序
O(N*logN) O(N*logN) O(1) 
     ×
起泡排序        O(N^2) O(N^2)      O(1)                 √    
快速排序 O(N*logN) O(N^2) O(logN)       ×
简单选择排序     O(N^2)         O(N^2)         O(1)                     √      
树形选择排序 O(N*logN) O(N*logN) O(N)       √
堆排序 O(N*logN) O(N*logN) O(1)       ×
归并排序                O(N*logN)       
O(N*logN)          
O(N)                         √         

 

1、 O(N^2) 级别的普通排序算法,我们用C++ 的随机函数rand() 产生的随机数进行排序,并计算耗费时间。

其中分别随机生成1W,3W,5W... 19W(增量为2W)共十组待排序列进行测试。得到直接插入排序、折半插入排序、起泡排序、简单选择排序的耗时统计图如下所示(SPSS软件做图统计)。

 

 

从上图可以发现,起泡排序的耗时最大,其他三者的耗时差不多。其中折半插入排序在待排数据量达到19W以后,其性能要比直接插入排序,和简单排序要好一些。另外,在数据量较小的情况下,插入排序的性能要比选择排序要略好。

 

普通算法分析:在数据规模较小时(9W之内),折半插入、直接插入、简单选择插入差不多。当数据量较大时,折半插入要好一些。而起泡排序算法的时间代价是最昂贵的。 另外,普通排序算法基本上都是相邻元素进行比较,因此O(N^2)基本的排序算法都是稳定的。

 

2、O(N*logN) 级别的先进排序算法,其时间复杂度要比普通算法要快得多。由于数据本身要小的多,因此我们没有拿它们和普通算法进行比较,而是另外选择从10W——140W(增量10W)的15组数据进行测试,耗时性能比较如下(SPSS软件做图统计):

 

从上图可以发现,先进排序的耗时代价远远小于普通排序算法。而先进算法之间也有区别。其中快速排序无疑是最优秀的。其次是归并排序和希尔排序,堆排序稍微差一些,而最差的就是树形选择排序了。

 

先进算法分析:

(1) 就时间性能而言, 希尔排序、快速排序、树形选择排序、堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。


(2) 先进算法之中,快排的效率是最高的。 但其缺点十分明显:在待排序列基本有序的情况下,会蜕化成起泡排序,时间复杂度接近 O(N^2)。


(3) 希尔排序的性能让人有点意外,这种增量插入排序的高效性完全说明了:在基本有序序列中,直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案,要知道增量的选取直接影响排序的效率。


(4) 归并排序的效率非常不错,在数据规模较大的情况下,它比希尔排序和堆排序都要好。


(5)堆排序在数据规模较小的情况下还是表现不错的,但是随着规模的增大,时间代价也开始和上面两种排序拉开的距离。


(6)树形选择排序并不是较好的先进排序方法,数据规模越大,其耗时代价越高。而且它所需要的额外辅助空间较多,达到O(N)级别。想想看,排序140W数据,需要额外再开辟140W的空间,实在是无法忍受。


(7) 多数先进排序都因为跳跃式的比较,降低了比较次数,但是也牺牲了排序的稳定性。

 

 

总的来说,并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见:

(1) 数据规模很小,而且待排序列基本有序的情况下,选择直接插入排序绝对是上策。不要小看它O(N^2)级别。

(2) 数据规模不是很大,完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心),快排永远是不错的选择,当然付出log(N)的额外空间是值得的。

(3) 海量级别的数据,必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法。

 

附:以上两个图的数据测试在Pentium 4 CPU 3.06GHZ下,CPU占用率0%的情况下运行的结果。 另外,下面是我测试九种排序算法的C源代码,可供大家下载使用。

 

 

 

 

 

★ 一个关于O(N*logN)耗时下限的理论

 

这里有一个疑问:是不是O(N*logN)是排序算法时间代价最好的极限呢?

 

当然不是,但是如果排序算法是基于"关键字比较"操作的,那么在最坏情况下确实能够到达的最好效果就是O(N*logN)了。 在最好情况下就没必要说了,如果待排序列基本有序,那么直接插入排序的比较次数都非常的少。

 

下面我们来证明一下(注意:这些排序算法的基本操作就是比较,其时间主要消耗在比较次数上)。现在有三个关键字K1、K2、K3。那么下图给出了这三个关键字记录在任何可能的排序状态下的判定树,树中的内部结点都进行了一次必要的比较。

三个关键字的待排序列只有上面叶子结点所描述的6中排序状态。而判定树上的每一次比较都是必须的。因此、这个判定树足以描述通过“比较”进行的排序过程。并且,每一个待排序列经过排序达到有序序列所需要进行的"比较"次数,恰为从树根到叶子结点的路径长度。因此3个关键字的比较最少需要2次,最多需要3次。

 

扩展一下,有N个关键字序列。那么就有N!种排序状态,自然判定树就有N!个叶子节点。我们知道,二叉树的树高为h的情况下,叶子结点最多有2^(h-1)个。而现在又N!个叶子结点,那么树高至少为log(N!)+1。也就是说,描述N个记录排序的判定树必存在一条长度为[log(N!)+1]的路径。根据斯特林公式(n!的高精度近似求解公式): log(N!)=N*log(N)。因此,最少的比较次数也就是N*log(N)了。

 

基于比较操作的排序算法的时间复杂度下限确实是O(N*logN)。那么如果不比较呢,耗时代价会不会进一步减少。当然,关于这方面的排序算法,请见《桶排序 》、《基数排序 》。

 

 

 

 

2
0
分享到:
评论
2 楼 bravelinw 2013-12-25  
[size=xx-small]大牛果然牛掰[/size]
1 楼 worldterminator 2013-08-29  
shell sort O(nlogn)?
在哪看的? 最坏情况是 n^2

相关推荐

    数据结构课程设计(内部排序算法比较_C语言)

    ### 数据结构课程设计:内部排序算法比较_C语言 #### 一、课题背景与意义 排序作为数据结构中的重要组成部分,在实际开发中具有广泛的应用场景。理解不同排序算法的特点及其适用场景,对于提高程序效率和解决问题...

    C语言数据结构内部排序算法及比较

    本文将深入探讨“C语言数据结构内部排序算法及比较”这一主题,结合个人课程作业的经验,对一些核心概念进行阐述,并对常见的内部排序算法进行比较。 首先,数据结构是组织和管理数据的方式,它包括数组、链表、树...

    数据结构(严蔚敏)第十章:内部排序

    内部排序通常包括比较型排序和非比较型排序两大类,比较型排序基于元素之间的比较,如冒泡排序、插入排序、选择排序等;非比较型排序则不依赖于元素间的比较,如计数排序、桶排序、基数排序等。 2. **基本排序算法*...

    数据结构课程设计(内部排序算法比较)

    总结来说,这个课程设计是关于理解、比较和评估内部排序算法的实践项目,旨在提升学生的算法分析能力和解决问题的能力,为未来的软件开发工作打下坚实基础。通过这样的学习,学生不仅能掌握各种排序算法,还能了解到...

    课程设计,数据结构内部排序的算法比较

    根据给定的信息,本文将对数据结构中的内部排序算法进行详细的分析与比较。这些排序算法在计算机科学领域占据着极其重要的地位,它们不仅被广泛应用于实际问题解决之中,还为理解算法复杂度提供了很好的示例。 ### ...

    内部排序小结 包括几乎所有的内部排序算法

    本篇内容主要总结了多种内部排序算法,包括它们的特点、效率以及适用场景。 1. 选择排序(Selection Sort):不稳定排序,平均时间复杂度为O(n^2)。它通过反复遍历待排序的数据,每次找到最小(或最大)的元素,...

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

    在本文中,我们将深入探讨内部排序算法,包括它们的工作原理、优缺点以及如何使用Python、JavaScript、Java、Go和PHP这些编程语言来实现它们。 1. 冒泡排序:冒泡排序是一种简单的交换排序方法,通过不断比较相邻...

    内部排序算法比较

    **内部排序算法比较** 在计算机科学中,内部排序是指数据在内存中进行的排序过程,无需额外的存储设备。本报告主要关注了六种常见的内部排序算法:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆...

    MFC 数据结构 内部排序算法比较

    总结来说,理解和掌握这些内部排序算法对于开发高效且优化的MFC应用程序至关重要。在实际编程中,了解不同算法的特性可以帮助我们做出明智的选择,提高程序的执行效率。通过深入学习和比较这些排序算法,不仅可以...

    数据结构——内部排序

    数据结构中的内部排序是计算机科学中处理数据组织和优化的核心技术之一。内部排序是指在排序过程中,所有数据对象可以一次性存放在内存中的排序算法。这些算法通常用于处理相对较小的数据集,可以快速有效地完成排序...

    数据结构 排序算法的比较

    5. **基数排序**:基数排序是一种非比较型排序,通过按照数字的位数从低位到高位进行排序。它适合处理具有固定范围的整数,如电话号码或邮政编码。 在实际应用中,排序算法的选择取决于具体需求,如数据的大小、...

    数据结构 课程设计 排序算法的比较

    在这个课程设计中,我们重点关注了六种经典的内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序以及堆排序。这些算法各有优劣,适用于不同的数据特性,理解和掌握它们对于提升编程能力,优化...

    内部排序算法分析

    在计算机科学领域,内部排序是数据处理中至关重要的一部分,它涉及到如何有效地对内存中的数据进行排列。本主题将深入探讨内部排序算法,并结合C语言代码进行解析。内部排序,顾名思义,是指数据在主存储器(内存)...

    数据结构内部排序 报证运行

    根据给定的文件信息,我们可以深入探讨数据结构中的内部排序算法以及其实现方式。内部排序是在计算机内存中完成的排序过程,与外部排序相比,它处理的数据量相对较小,但效率通常更高。以下是对文件中提及的几种排序...

    数据结构六种内部算法排序比较

    根据给定文件的信息,本文将对六种不同的排序算法——冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序以及堆排序——进行详细分析,并比较它们之间的性能差异。 ### 冒泡排序(Bubble Sort) 冒泡排序...

    数据结构课程设计--十种内部排序发的比较

    数据结构课程设计是计算机科学中的一个关键环节,它涉及到如何高效地组织和处理数据,而内部排序算法则是其中的重要组成部分。在本项目中,我们主要关注十种内部排序方法的比较,包括起泡排序、直接插入排序、简单...

    各种内部排序算法的比较

    内部排序,也称为内存排序,是指数据全部存储在内存中进行的排序过程。这里我们将详细探讨各种内部排序算法,包括它们的工作原理、效率、适用场景以及优缺点。 1. **冒泡排序**:是最简单的排序算法之一,通过重复...

    西南交通数据结构内部排序-多种排序算法的实现.docx

    【内部排序】是数据结构领域中的重要概念,指的是在计算机内存中完成的排序操作。本实验涉及了四种经典的内部排序算法:希尔排序、快速排序、堆排序和归并排序。 **希尔排序**(Shell Sort)是由希尔提出的,它是一...

    数据机构综合课设内部排序算法比较.docx

    本篇文章将深入探讨10种常见的内部排序算法,包括它们的基本思想、比较次数和移动次数的计算,以便更直观地理解不同算法的效率。 1. **直接插入排序**: 直接插入排序是一种简单的排序算法,它通过比较新元素与已...

Global site tag (gtag.js) - Google Analytics