内部排序算法性能分析之数据结构课程设计

课程名称：数据结构

本科学生课程设计（论文）

题 目 内部排序算法性能分析 姓 名 阳 明 学 号 104328318117680 学 部 计算机科学与技术 专业、年级 计科1003 指 导 教 师 刘 琼

2011年12月24日

湖南涉外经济学院本科课程设计（论文）

摘 要

排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除.通过描述冒泡、选择、插入、堆和快速6种排序算法，内部排序其算法灵活方便，因此成为了程序算法中一个必不可少的应用，所以在应用之前要经过严谨的思考才不会出错，不会造成计算机运算速度的延迟，才会完全发挥内部排序的性能。

内部排序的方法种类繁多，但就其全面性能而言，很难提出一种被认为是最好的方法。但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境（如记录的初始排序列状态等）下使用。如果安排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序，选择排序，归并排序和计数排序等五类；如果按内部排序过程中所需要的工作量来区分，则可分为3类：（1）简单的排序方法，该时间复杂度为O(n*n)；（2）先进的排序方法，该时间复杂度为O（nlogn）；（3）基数排序，其时间复杂度为O（d*n）；主要介绍非常实用而算法又容易接受的的这六类排序。

由于很多人在使用的过程中，不知道那种排序适合他们的程度设计，因此导致该算法没有得到充分的应用，起泡排序最简单的排序，很容易写出代码，但运算时间复杂度稍长一些；直接排序能够很快的最大和最小的数据，但假如数据较多，操作比较繁琐；简单选择排序稳定比较次数与起泡排序一样，则相对之还要慢；快速排序速度快，数据移动少，平均性能比较好，但是性能不稳定；希尔排序是插入算法的改进，由于多次的插入造成了其稳定性不好；堆排序在最坏情况下时间复杂度也为O(nlogn)，并且它仅需一个记录大小供交换用的辅助存储空间，但在记录数较少时不提倡使用；

但本文主要介绍这6类排序（起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序）一些优点和缺陷，对缺陷加以改进。通过对传统算法的性能分析，发现其中的缺陷，对算法的设想来弥补中间的不足，以致算法的性能有所提高。

关键字: 数据结构、内部排序、算法改进、性能分析

目 录

第1章 前 言.............................................................................................................. 1 1.1分析问题............................................................................................................. 1 1.2研究背景.............................................................................................................. 1 1.3研究方向.............................................................................................................. 2 1.4研究方法.............................................................................................................. 2 1.5结构与安排.......................................................................................................... 2 第2章 系统功能分析.................................................................................................. 3 2.1 需求分析及实现目标 ......................................................................................... 3 2.1.1应用现状及存在的问题............................................................................. 3 2.1.2 实现任务.................................................................................................... 3 2.2可行性分析.......................................................................................................... 4 2.2.1技术可行性................................................................................................. 4 2.2.2 工具可行性................................................................................................ 4 2.2.3 经济可行性................................................................................................ 4 2.2.4 操作可行性................................................................................................ 4 第3章 总体设计.......................................................................................................... 5 3.1设计需求及描述.................................................................................................. 5 3.1.1设计问题描述............................................................................................. 5 3.1.2 设计需求分析.......................................................................................... 5 3.1.3 系统设计的实质功能................................................................................ 5 3.2 设计原理与设计内容 ......................................................................................... 6 3.2.1系统总体结构............................................................................................. 6 3.2.2“内部操作过程”菜单设计原理如图所示。.......................................... 6 3.2.2“排序性能分析”菜单设计原理.............................................................. 7 3.2.3设计内容..................................................................................................... 7 第4章 详细设计.......................................................................................................... 9 4.1冒泡排序.............................................................................................................. 9 4.2直接插入排序.................................................................................................... 10 4.3希尔排序............................................................................................................ 11 4.4简单选择排序.................................................................................................... 13 4.5快速排序............................................................................................................ 14 4.6堆排序................................................................................................................ 16

4.7六种排序方法讨论............................................................................................ 18 第5章 排序算法的改进............................................................................................ 20 5.1双向冒泡排序算法............................................................................................ 20 5.2双倍快速排序的算法........................................................................................ 21 5.3选择排序的算法................................................................................................ 22 5.4 堆排序的改进算法 ........................................................................................... 24 第六章 系统实现及数据测试.................................................................................... 29 6.1主界面................................................................................................................ 29 6.2“排序内部操作过程”菜单............................................................................. 29 6.2.1当用户输入0-6的数字时则会随意的进入下一级子菜单................... 30 6.2.2输入“2”进行“希尔”排序................................................................. 30 6.3“性能分析”菜单............................................................................................. 31 6.3.1当用户输入“1”时进行“插入与希尔”排序之间的性能分析比较. 31 6.3.2当用户输入“1”时进行“插入与冒泡”排序之间的性能分析比较. 32 总 结.......................................................................................................................... 33 参考文献...................................................................................................................... 34

内部算法性能分析 第1章 前 言

第1章 前 言

1.1分析问题

排序是指将一个数据元素序列排列成一个有序列的过程。排序是计算机的一个重要的领域，并广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。资料表明，在当今计算机系统中，花费在排序上的时间占了系统运行的时间的很大比重。相当多的计算机中，有50%以上的CPU时间是用在排序数据上的。因此为了提高计算机系统的工作效率，研究和发展更有效的排序算法的十分重要的。

目前人们已经提出了许多不同的排序算法，然而如果在不适应的场合的应用，那么其平均时间(averageTime)和最差时间(worstTime)就会不理想，其排序算效率就会大大的降低，如国防系统和生命支持系统，如果排序方法性能低下，将会令我们大大的失望。另外用来衡量排序算法的标准是稳定性，在那些比较复杂的排序中其稳定性不是很好，容易程序出错，就这样造成我们计算机的运算时间加长和内存地址的浪费。

1.2研究背景

由于排序是数据结构中的重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排序算法的时间消耗对于实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等，以关键码的比较次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况，排序表的数据是多种不一样的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图来表示。

然而在本文中我们将选择其中最基本也是最常用的6种内部排序（直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序）进行讨论，介绍它们的基本思想和实现过程，分析各种算法的时间、空间复杂性、比较次数、移动次数以及稳定性，以期读者能够掌握这些算法及其特点中，在实际应用中能够结合具体问题设计出正确而高效率的数据排序程序。

1

内部算法性能分析 第1章 前 言

1.3研究方向

排序算法其种类繁多，但还是有一些未解次的问题，例如：选择排序，快速排序，希尔排序，堆排序仍然面临排序后的不稳定性；从而还面临一种稳定的算法也可由不稳定的算法来实现；冒泡排序很容易实现，但是它的时间复杂度和移动次数的问题仍然存在；更让人不可思议的是有些排序这两种缺点都存在；同样每一种排序算法都有它的优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况进行选择。首先，考虑排序对稳定性的要求，若要求稳定，则只能在稳定的排序方法中选取，否则可以在所有的方法中选取；其次要考虑待排序的序列记录数目n，若n较大则可以在改进的方法中选取，否则在简单方法中选取；然后再考虑其他因素。本文主要是通过排序来从中发现的稳定性、比较次数以及移动次数等问题，从而从性能上分析得出不足并加以改进。

1.4研究方法

基于Visual C++ 6.0平台编程是当今程序者的青睐，它有着强大的性能、完全丰富的工具及高速的处理速度和完备的兼容性。不仅可以简化编程的设计并且算法应用灵活，使应用程序的开发更为简便。C++是为开发大型程序而研制的，它比C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件；本人就利用上述C++开发软件编写了《内部排序算法性能分析系统》，采用人机互动的操作模式，系统经过显示主界面功能，然后用户的需要操作，实现了两种排序相互之间的优缺点，从而从中获得一些性能分析结论让人们更好应用各种排序。

1.5结构与安排

本文主要是介绍六种排序的性能分析，首先“前言”对研究背景和研究目的作了简单的介绍；其次“系统功能分析”对本系的说明和讲解；再次“总体设计”对本系统做了一个简要引导，并且通过“总体设计”对该系统的运行懂得差不多了；“详细设计”就是对系统有了详细的设计过程，更进一步知道设计原理；“排序算法的改进” 介绍传统算法的不足，经过设想对原算法加以改进“系统实现及数据测试”不但让我们知道了系统的界面和一些操作的实施，让你知道整个算法的设计并且加以理解。

2

内部算法性能分析 第2章 系统功能分析

第2章 系统功能分析

2.1 需求分析及实现目标

2.1.1应用现状及存在的问题

随着社会的发展，计算机科学技术应用又迈进了一大步，然而在很多的应用过程中不时产生很多错误或延迟，尤其是在钢铁厂、天气预报的预测、火箭的发射等一些大型的场所，这无疑处理器在处理的过程中不能出一些差错，因此就要对那些已编制好的程序的算法要求比较严谨、排序就是其中之一。很多人在运用的过程中对其算法不够了解或者考虑不周，因此给处理器造成了不必的误时。就拿火箭发射来说，如果排序方法性能低下，将是非常危险的。我们将会看到有几个排序算法能够提供某种保证机制，可以消除在最差情况下不可接受的执行性能。

另外存在一个比较大的问题就是排序的稳定性。稳定排序方法保持相等元素的相关顺序。例如，假设有一个学生数组，其中的每一项由学生的姓和其品质总分数组成，根据品质总分数排序。如果排序方法稳定，并且（”balan”,28）开始时位于比(“wang”,28)小的索引位置，排序后(“balan”,28)仍然位于比(“wang”,28)小的索引位置。稳定性可以简化工程开发。例如，假设上面提到的数组已经根据排好序了，有一个根据品质总分数排序的应用程序调用，对于拥有同样品质总分数的学生，他们的顺序还是按字母顺序。稳定排序不需要附加其他确保相同品质总分数的学生按字母顺序排列的工作就可以完成了。因此，对于程序员来说这是必备的重要技能，同时掌握它是他们当前一项急迫的任务。 2.1.2 实现任务

排序数据是由系统随机产生，再通过用户根据自已所需的进行对这六种排序的操作，简洁清晰、容易理解，提高了对该六种排序性能的应用。

用户只需按界面上的提示操作。

这六种排序的性能分析由系统自动的给予分析并且可以看到整个的排序过程(如：移动的次数、比较的次数以及稳定性好坏)

在系统随机产生数据是用户最好是多采用几组数据进行比较这样的正确率要高，同时测试系统的性能好坏。

3

内部算法性能分析 第2章 系统功能分析

2.2可行性分析

所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。 2.2.1技术可行性

本系统采用人机操作进行管理，用visual C++ 6.0进行前台设计、系统随机产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C++ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系统在技术方面的可行性。 2.2.2 工具可行性

软件方面：

信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算机操作的系统等都属于软件部分。

硬件方面：

计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够满足人们的需求，而价格也能被人们所接受。 2.2.3 经济可行性

这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层次。 2.2.4 操作可行性

本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决，并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行性。

4

内部算法性能分析 第3章 总体设计

第3章 总体设计

3.1设计需求及描述

3.1.1设计问题描述

设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于10，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果.

3.1.2 设计需求分析

用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。

利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。

在主函数中调用用户自定义函数，输出比较结果。

本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。 3.1.3 系统设计的实质功能

用户启动该系统进入主菜单，在主菜单中有三个菜单命令，可以按照用户的意愿来选择他想要的命令

当你选择“排序内部操作过程”菜单时，即可进入一下子菜单，你可以看到这六种排序的内部排序过程，并且可以知道这六种排序具体的移动次数、比较次数以及稳定性的好坏。

当你选择“排序性能分析”菜单时，马上进入下一级子菜单，你可以知道这六种排序之间的一些性能相关的知识，这一级菜单是用户来安排，如果不知道那两种排序的性能那种占优势好一些，你可以输入排序的编号，然后系统给你分析，给出结论。

5

内部算法性能分析 第3章 总体设计

3.2 设计原理与设计内容

3.2.1系统总体结构 内部排序算法性能分析 系统总体结构如图4.1所示：

图3.1 系统总体结构

冒泡排序 希尔排序 直接插入排序 堆排序 简单选择排序 快速排序 冒泡性能分析 希尔性能分析 插入性能分析 选择性能分析 快速性能分析 堆性能分析 排序过程模块 性能分析模块 3.2.2“内部操作过程”菜单设计原理如图所示。

Point()开 始 Switch()进行判断 Bubblesort（）函数进行直接排序 partition()函数进行快速排序 Shllinsert()函数进行希尔排序 Selectsort()函数进行简单选择排序 Heapsort()函数进行堆排序 Insertsort()函数进行直接排序 子函数结束 图3.2“内部操作过程”菜单

6

内部算法性能分析 第3章 总体设计

3.2.2“排序性能分析”菜单设计原理

“排序性能分析”菜单的算法是调用“内部操作过程”菜单的算法，根据这一原理而成的，就不一一的介绍了，请读者自已去理解“内部操作过程”的设计过程。

3.2.3设计内容

内部排序系统具体实现的功能包括：快速排序，冒泡排序，希尔排序，简单选择排序，堆排序，直接排序等这六大排序的集成六个主要的函数如下：

快速排序函数：partition();

希尔排序函数：Shellsort(); 简单选择排序函数：selectsort(); 堆排序函数：heap(); 直接排序函数：insertsort(); 起泡排序函数：Bubblesort();

排序数据类型定义：

ADT paixu{

数据对象：D={aij|aij属于{1，2，3…},i,j>0} 数据关系：R={|ai-1,ai∈D，i=2,...,n} 基本操作：

Insertsort();

初始条件：数组已经存在。

操作过程：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。

Bubblesort();

初始条件：数组已经存在。

操作过程：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，知道全部满足顺序要求为止。

Shellsort();

初始条件：数组已经存在。

操作过程：先取定一个正整数d1

7

内部算法性能分析 第3章 总体设计

组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。 Selectsort();

初始条件：数组已经存在。

操作过程：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已经排序的记录序列的最好，直到全部排完。 heapsort ();

初始条件：数组已经存在。

操作过程：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。

partition()；

初始条件：数组已经存在。

操作过程：在待排序的n个记录中任取一个记录，以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的放在一边，大的放另一边，并把该记录放在中间，然后重复至完成。

} ADT 排序

8

内部算法性能分析 第4章 详细设计

第4章 详细设计

4.1冒泡排序

冒泡排序（BubbleSort）是我们大家都熟知的排序，其基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i。

算法：for(i=1;i<=L-6;i++)/*外循环：控制比较趟数*/

{

for(j=L;j>=i+1;j--)/*内循环：进行每趟比较*/

{

times++;/*比较次数*/

if(R[j]

}

changes+=3;/*移动次数*/

冒泡排序的最好 、最坏 、平均情况下的时间复杂度都为 O (n2 ) ,故算法的平均时间复杂度也为 O (n2 ) 。但是若在某趟排序中未发现气泡位置的交换 ,则

9

内部算法性能分析 第4章 详细设计

说明待排序的无序区中所有气泡均满足轻者在上、重者在下的原则 ,即为正序 ,则冒泡排序过程可在此趟扫描后就终止 ;在每趟排序过程中 ,无序区 R [ i. . n]的范围可能会有较大改变 ,而不是递减 ;对某些不对称性情况 ,在排序过程中 ,可改变其扫描方向。

4.2直接插入排序

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法，它基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

算法：for(i=2;i<=L;i++)

{

if(R[i]

{ R[0]=R[i];j=i-1;//复制哨兵

while(R[0]

{

times++; changes++;

R[j+1]=R[j];j--;//记录后移

10

内部算法性能分析 第4章 详细设计

}

R[j+1]=R[0];//插入到正确位置

changes++; ｝

按以上算法进行直接插入排序的过程如图4.1所示： 初始序列：i=1 [46] 58 15 45 90 18 10 62

i=2 [46 58] 15 45 90 18 10 62 i=3 [15 46 58] 45 90 18 10 62 i=4 [15 45 46 58] 90 18 10 62 i=5 [15 45 46 58 90] 18 10 62 i=6 [15 18 45 46 58 90] 10 62 i=7 [10 15 18 45 46 58 90] 62

i=8 [10 15 18 45 46 58 62 90] 图4.1直接插入排序过程

从算法的实现过程可见，在最坏情况下，线性插入排序每插入一个元素需要进行i-1次比较，需要插入元素为N-1个，所以最大比较次数为：N(N-1)/2,该算法的时间复杂性为O(N*N) 空间复杂度为O(1)，因此，直接插入排序属于稳定的排序

4.3希尔排序

希尔排序(Shell Sort)又称“缩小增量排序”(Diminishing Increment Sort)，它也是一种属于插入排序类的方法，但在时间效率上跟其他的几种排序方法有了较大的改进。

希尔排序基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

先看一下希尔排序的过程。初始关键字序列如下面所示。首先将该序列分成5个子序列{R1,,R6},{R2,R7}??{R5,R10},如下面所示，分别对每个子序列进行直接插入排序，排序完后，然后进行第二趟希尔排序，即分别对下列3个子序列：

11

内部算法性能分析 第4章 详细设计

再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。

大根堆排序算法的基本操作：

初始化操作：将R[1..n]构造为初始堆；

每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

算法：

for(i=(L/2);i>=1;i--)//将二叉树转换成堆 CreateHeap(i,L);//建堆

for(i=L-1,k=1;i>=1;i--,k++)

{

temp=R[i+1];//堆（heap）的root值和最后一个值交换 R[i+1]=R[1];

R[1]=temp; changes+=3;

}

CreateHeap(1,i);

从上述分析：堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用CreateHeap实现的。

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)，由它是不稳定的排序方法。

17

内部算法性能分析 第4章 详细设计

4.7六种排序方法讨论

综合比较上述的各种内部排序方法，大致有如下结果（见下表）

表4.1

排序方法 直接插入排序 简单选择排序 n(n-1)/2 n*(n-1)/2 简单 快速排序 O(nlogn) n*(n-1)/2 ) O(nlognn(n-1)/2 O(n*n) O(nlogn) O(nlogn) O(logn) 是 较复杂 希尔排序 冒泡排序 堆排序 O(nlogn) 复杂 简单 较较

n-1 (n+2)(n-1)/2 最少比较次数 最多比较次数 最少移动次数 最多移动次数 最坏情况 时间复杂度 最好情况 平均情况 空间复杂度 稳定复杂性 度 简单 0 n+4(n-1)/2 O(n*n) O(n) O(n*n) O(1) 是 0 3(n-1) O(n*n) O(n*n) O(n*n) O(1) 否 O(nlogn) O(nlogn) O(1) 否 n-1 n*(n-1)/2 0 n(n-1)/2 O(n*n) O(n) O(n*n) O(1) 是 O(nlogn) O(nlogn) O(nlogn) O(1) 否 复杂 附注：

1、 堆排序、冒泡排序、希尔排序和快速排序中，在待排序的数据已经基本

有序是，花费时间最多的反而是快速排序，此是最不利于发挥其特长。 2、 在以比较为基础的排序方法中，“比较关键字的大小”和“将关键字从

一个位置移动到另一个位置”这两种操作的次数决定了算法的时间复杂性，它们是算法的时间复杂性的两项指标。

3、 在局部有序和待排序的关键字序列数目较小时，最佳的内部排序方法是

直接插入排序。

4、 在冒泡排序的每一趟中，只能将关键字最大或最小的元素移动到正确的

置，其他关键字有可能在交换的过程中朝着与最终排序相反方向移动；快速排序的每一趟中，不仅能将枢轴的元素移动到正确的位置，而且其他关键字所移动的方向也与其最终排序的位置方向一致。

5、 设有一个堆，取出堆中最大元素后，将它重新调整为堆，所需要的时间

18

内部算法性能分析 第4章 详细设计

复杂度为O(nlogn)

6、 假设待排序的关键字序列有n（例如，n=10000）个元素，若仅找出其中

最大的k（例如k=10）个元素，则采有堆排序最省时间；若仅找出其中第k个最小元素，则采用快速排序最省时间

如何选择好的排序方法：

没有哪一种排序方法是绝对好的。每一种排序方都有优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况进行选择。首先，考虑排序对稳定性的要求，若要求稳定，则只能在稳定的排序方法中选取，否则可以在所有的方法中选取；其次要考虑待排序列的记录数目n，若n较大，则可以在改进的方法中选取，否则在简单方法中选取；然后再考虑其他因素。综上所述，可得以上结论：

1、当待排序的序列的记录数目n较大，记录按关键字的值分布比较随机，并且对排序稳定必不作要求时，宜选用快速排序。

2、当待排序的序列的记录数目n较大，记录按关键字的值分布可能出现升序或逆序的情况，并且对排序稳定性不作要求时，宜选用堆排序。

3、当待排序的序列的记录数目n较小，记录的关键字的排列基本有序，分布比较随机且对排序有稳定性要求时，宜选用插入排序。

4、当待排序的序列的记录数目n较小，并且对排序有稳定性要求进，宜选用选择排序；若记录的关键字的值不接近逆序，也可选用直接插入排序。

19

内部算法性能分析 第1章 前 言

第5章 排序算法的改进

5.1双向冒泡排序算法

对于输入的子序列 L [ low…High ]看成竖着排列的“气泡”,然后分别从上端 (Low)向底端 ( High)扫描。在扫描的过程中时刻注意两个相邻元素的顺序 ,保证上端的元素小于下端的元素 ,这样经过一趟扫描后就使较大的元素沉到下面。然后再从底端向上端扫描 ,由于在前一趟扫描过程中最大的元素已经沉到最底端 ,所以这次扫描最大的元素不再参加排序 ,将剩下的元素进行排序 ,排序的过程中保证使得底端元素大于顶端元素。这样反复的扫描 ,并不断缩小排序空间 ,直到整个序列有序位置。这样直观上看 ,双向冒泡排序法先让重的气泡沉到底下 ,然后让轻的气泡浮上来 ,然后再让大的气泡沉下去 ,让次轻的气泡浮上来 ,依次反复 ,直到带排序列有序为止。

算法是利用两个指针 low和 high记录带排序列区域 L [ low…high ] ,用指针变量 t记录在每趟扫描过程中最近一次交换记录的位置 ,在每次扫描开始 t的初始值分别为 Low或 high ,并且在扫描结束后再让 t和 low或 high进行比较 ,如果发现某次 t值没有改变 ,则说明序列已经有序 ,并且用 break跳出循环 ,提前结束排序。 代码实现：

While (low < high)

{

t=low;//t指向带排序区间的离最底端

For (i = low ; i < high ; i + + )

{

if (L [ i ] > L [ i + 1 ] )

{m=l[i];l[i]=l[i+1];l[i+1]=m;

t=i;} //记录最近一次移动的关键字的位置 if(t==low) break; //检查是否待排关键字有序，如有序则退出循环，结束排序

else high=t; //缩小待排序列的范围 for (i = high ; i > low ; i + + ) { if (L[ i ] < L [ i - 1 ])

m=l[i];l[i]=l[i+1];l[i+1]=m;t=i;} //记录最近一次移动的关键字的位置

If(t==high) break; //检查是否排关键字有序，如有序则退出循环，

结束排序

20

内部算法性能分析 第5章 排序算法的改进

else low=t; ｝ //缩小待排序列的范围

算法分析：双向冒泡排算法是原地置换算法，并且由于 L [ i ]〉L [ i + 1 ]或者 L [ i ] < L [ i - 1 ]时才进行交换，所以说该算法也是稳定的排序方法，但如果改为 L [ i ]〉= L [ i + 1 ]或者 L [ i ] < = L [ i - 1 ]时才进行交换 , 则改变其的稳定性。该算法在执行一趟排序后同时确定两个记录的位置 ,即待排区域的最大和最小的记录，而书中提到的冒泡排序在执行行一趟排序后仅能确定一个记录的位置，即最大或最小的，显然该算法更可取。

5.2双倍快速排序的算法

快速排序的基本思想是基于分支策略的思想。即对于输入的子序列 L [ low…High ] ,如果规模足够小则直接进行排序 ,否则分三步处理 :

分解 (Divide) :设输入的序列 L [ low…High ] ,确定支点元素 L [ low ]和 L [ High ] ,并使 L [Low ] . key < = Ll[ High ] . key ,然后分解 (Divide) :将序列 L [ low…High ]划分成三个子序列 L [Low. . L - 1 ]、[L + 1. . H -1 ]和 L [ H + 1. . High ] ,使 L [ low…High ]中元素的关系为 L [Low. . L - 1 ] < L [L ] < L [L + 1. . H - 1 ] < L[ H] < L [ H + 1. . High ]。

递归求解 (Conquer) :通过递归调用快速排序算法分别对 L [Low. . L - 1 ]、[L + 1. . H - 1 ]和 L [ H + 1. .High ]分别进行分解排序。

合并 (Merge) :由于对分解出的三个子序列的排序是就地进行的 ,所以在 L [Low. . L - 1 ]、[L + 1. . H- 1 ]和 L [ H + 1. . High ]都排好序后不需要执行任何计算 L [ low…High ]就已排好序。

算法描述：

该算法首先用QSort对序的L [ low…high ]区间进行分解 ,把此序列区间分解为五部分 ,其中 L [L ]和L[H]是两个分界点，并从这两个分界点处将整个序列分解为三个部分，分别为L [ low… - 1 ]、[L + 1…H-1]、[ H + 1…high ] ,然后再递归调用 QSort分别对三个序列进行分解 ,这样直到递归到最后 ,L [ low…high ]便成为一个有序的序列。然后再对给定序列 L [ 1…L. lengh ]进行快速排 QuickSort ( Sqlist &L) )时即直接调用QSort即可。

算法实现： n=high-low; if(r[row]>r[high])

{

t=r[row]; //确保区间内第一个元素的值不大于区间内最后一个元素的值 r[row]=r[high];r[high]=t;

l=low; //小于区间内第一个元素的值数组边界下标

21

内部算法性能分析 第5章 排序算法的改进

对于数组

A[0]，??，a[low],??，a[start-1],a[start],??a[end],??，a[n-1]

0<=low

其中a[0]，??，a[low],??，a[start-1]为已排好序的部分，a[start],??，a[end],??，a[n-1]为待插入的部分，在原来的插入算法中，当我们找到待插入元素a[start]应该插入的位置low后，先将a[start]暂存，然后将a[low],??，a[start-1]后移一位，再将暂存的a[strat]插入a[low]处；在改进的插入算法中，我们还要考察在a[start]之后，是否还存在一个序列a[start+1]，??，a[end],使得

a[start]<=a[start+1]<=??<=a[end]]<=a[low]

如果确实存在这样的的一个序列，则我们可以一次性将a[start],??，a[end]插入a[low]处。在原有的的基础上作一些改进得出如下算法：

for(start=1;start

{ low=0;

high=start-1;

while(low<=high) {

moddle=int((low+high)/2); if(a[moddle]<=a[start])

low=moddle+1; else high=moddle-1; end=start+1;

while(enda[end]) end++; end--;

newmove(a,low,start,end); start=end;

} }

新的循环移位插入算法如下：

L=start-low;

p=end-low+1; n=p; m=L; { }

for(i=0;i

27

r=p%m;

while(r!=0) n=m;m=r;r=n%m;

内部算法性能分析 第5章 排序算法的改进

}

outpos=i; inpos=i;

temp=a[i+low];

while((outpos=(inpos+L)%p)!=i) {

a[inpos+low]=a[outpos+low]; inpos=outpos;

}

a[inpos+low]=temp;

性能分析：在比较插入过程中，若出现一次可插入的部分有序段a[start],??,a[end],设插入位置在a[low]开始位置处，则涉及移动的序为a[low],??，a[start],??，a[end]，需插入的元素个数为Q=end-start+1,涉及移动的元素总数为P=end-low+1，插入间距为L =start-low；在原插入算法中，每插入一个元素需移动start-low+2次，故总共需移动(start-low+2)(end-start+1)次，而在改进插入算法中，只需移动end-low+m=(end-start+1)+(start-low+m-1)次，其中m=gcd(P,L),两者比值为：

改进插入算法动次数 1 1 原插入算法移动次数 Q P

一般情况下，插入间距L远大于待插入的元素个数Q，所以上式主要取于1/Q，由此可见，只要出现一次有Q个元素的可插入的部分有序段，该部分的插入效率可提高Q倍；整个改进插入算法的效率提高取决于出现可插入的部分有序段的概率和可插入的部分有序段的长度，而且后者比前者更为积极作用。

改过算法的稳定性取决于找到有序的a[start],??，a[end]时的判断条件，如果我们采用

Enda[end]

作为判断条件，则改进的算法是稳定的；如果为了一次尽可能多的插入元素，提高排序速度采用：

Enda[end] 作为判断条件，则改进算是不稳定的。

28

内部算法性能分析 第1章 前 言

第六章 系统实现及数据测试

6.1主界面

当用户启动该程序时进行测试，进入主菜单如图6.1所示：

图6.1主菜单

6.2“排序内部操作过程”菜单

当用户输入“1”时进入“排序内部操作过程”菜单如图6.2所示：

图6.2“排序内部操作过程”菜单

29

内部算法性能分析 参考文献

6.2.1当用户输入0---6的数字时则会随意的进入下一级子菜单

输入“1”进行“直接插入”排序，如图6.3所示：

图6.3“直接插入”排序操作过程

6.2.2输入“2”进行“希尔”排序

如图6.4所示：

图6.4“希尔”排序操作过程

30

内部算法性能分析 参考文献

6.3“性能分析”菜单

当用户输入“2”时进入“性能分析”菜单，如图6.5所示：

图6.5 “性能分析”菜单

6.3.1当用户输入“1”时进行“插入与希尔”排序之间的性能分析比较

如图6.6所示：

图6.6“插入与希尔”排序分析

31

本文来源：https://www.bwwdw.com/article/21sf.html