数据结构中的内部排序算法及性能分析

《数据结构中的内部排序算法及性能分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构中的排序算法及性能分析一、引言排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。在此首先明确排序算法的定义：假设n个记录的序列为{，，…}（1）关键字的序列为：{，，…，}需要确定1，2，…，n的一种排列：，使（1）式的序列成为一个按关键字有序的序列：上述定义中的关键字Ki可以是记录Ri（i=1,2，…，n）的主关键字，也可以是记录的次关键字，甚至是若干数

2、据项的组合。若在序列中有关键字相等的情况下，即存在=（），且在排序前的序列中领先于。若在排序后的序列中Ri仍领先于，则称所用的排序方法是稳定的；反之若可能使排序后的序列中领先于，则称所用的排序方法是不稳定的。一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。在刚才提到的时

3、间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。通常，在排序的过程中须进行下列两种基本操作:(1)比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。

4、前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。待排记录有三种存储方式：（1）待排的一组记录存储在地址连续的一组存储单元上；（2）待排记录存储在静态链表中；（3）待排记录存储在地址连续的存储空间内，但同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”。在此我们讨论待排序00的记录存储在一组地址连续的存储单元的情况。在这种存储方式中，记录之间的次序关系由其存储位置决定，子序列中相邻的两个记录它们的存储位置也相邻，实现排序必须移动记录。在以后的讨论中这

5、记录的关键字均为整数二、插入排序2.1直接插入排序直接插入排序（StraightInsertionSort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录曾数1的有序表。例如，已知待排序的一组记录的初始排列如下所示：R(49),R(38),R(65),R(97),R(76),R(13)R(27)R()…（2-1）设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成含4个记录的有序序列{R(38)R(49)R(65)R(97)}(2-2)现要将式（2-1）中的关键字为76的记录插入到上述

6、序列，以得到一个新的含5个记录的有序序列，则首先要在式（2-2）中查找以确定R（76）所应插入的位置，然后进行插入。假设从R(97)开始从左向右比较，由于65<76<97，所以R(76)应插入到R(65)和R(97)之间从而形成新的有序序列{R(38),R(49),R(65),R(76),R(97)}(2-3)一般情况下，第i趟直接排序的操作为：在含有i-1个记录的有序子序列r[1…i-1]中插入一个r[i]后，变成一个含有i个记录的有序子序列r[1…i]；并且，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。在自i-1起往前

7、搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。以（2-1）中的关键字为例，按照以上算法进行直接插入排序的过程如图:[初始关键字]：（49）386597761327i=2:(38)(3849)6597761327i=3:(65)(384965)97761327i=4:(97)(38496597)761327i=5:(76)(3849657697)1327i=6:(13)(133849657697)27i=7

8、:(27)(13273849496576)i=8:(49)(13273849496576)2.3希尔排序希尔排序又称为“缩小增量排序”（