数据结构中的排序算法及性能分析一、引言排序（sorting ）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

为了查找方便通常希望计算机中的表是按关键字有序的。

因为有序的顺序表可以使用查找效率较高的折半查找法。

在此首先明确排序算法的定义：假设n 个记录的序列为{ 1R ，2R ，…n R } （1）关键字的序列为：{ 1k ，2k ，…，n k }需要确定1，2，…，n 的一种排列：12,n p p p ，…，使（1）式的序列成为一个按关键字有序的序列：12p p pn k k k ≤≤≤…上述定义中的关键字Ki 可以是记录Ri （i=1,2，…，n ）的主关键字，也可以是记录i R 的次关键字，甚至是若干数据项的组合。

若在序列中有关键字相等的情况下，即存在i k =j k （1,1,i n j n i j ≤≤≤≤≠），且在排序前的序列中i R 领先于j R 。

若在排序后的序列中Ri 仍领先于j R ，则称所用的排序方法是稳定的；反之若可能使排序后的序列中j R 领先于i R ，则称所用的排序方法是不稳定的。

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。

但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

在刚才提到的时间频度中，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）将记录从一个位置移动到另一个位置。

前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。

待排记录有三种存储方式：（1）待排的一组记录存储在地址连续的一组存储单元上；（2）待排记录存储在静态链表中；（3）待排记录存储在地址连续的存储空间内，但同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”。

在此我们讨论待排序00的记录存储在一组地址连续的存储单元的情况。

在这种存储方式中，记录之间的次序关系由其存储位置决定，子序列中相邻的两个记录它们的存储位置也相邻，实现排序必须移动记录。

在以后的讨论中这记录的关键字均为整数二、插入排序2.1直接插入排序直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录曾数1的有序表。

例如，已知待排序的一组记录的初始排列如下所示：R(49),R(38),R(65),R(97),R(76),R(13)R(27)R(49)…（2-1）设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成含4个记录的有序序列{R(38)R(49)R(65)R(97)} (2-2)现要将式（2-1）中的关键字为76的记录插入到上述序列，以得到一个新的含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起往前搜索的过程中，可以同时后移记录。

整个排序过程为进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

以（2-1）中的关键字为例，按照以上算法进行直接插入排序的过程如图:[初始关键字]：（49） 38 65 97 76 13 27 49i=2: (38) (38 49) 65 97 76 13 27 49i=3: (65) (38 49 65) 97 76 13 27 49i=4: (97) (38 49 65 97) 76 13 27 49i=5: (76) (38 49 65 76 97) 13 27 49i=6: (13) (13 38 49 65 76 97) 27 49i=7: (27) (13 27 38 49 49 65 76) 49i=8: (49) (13 27 38 49 49 49 65 76)2.3希尔排序希尔排序又称为“缩小增量排序”（Diminishing Increment Sort），也是一种属于插入排序类的方法，但在时间效率上较上述有较大的改进。

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

即希尔排序是首先在直接插入排序以前加入了分出子列的直接插入排序，使得原纪录具有以下特性L.r[i].key>max{L.r[j].key} (1≤j<i)然后再对整个记录序列进行一次直接插入排序。

以（2-1）中的关键字序列为例，说明希尔排序的过程。

首先将此序列分为5个子序列{R1，R6},{R2，R7},{R3，R8},{R4，R9},{R5，R10},分别进行插入排序，产生第一趟希尔排序。

然后进行第二趟希尔排序，即分别对下列三个子序列：{R1,R4,R7，R10}，{R2,R5,R8}，{R3,R6,R9}，进行直接插入排序，最后对整个序列进行直接插入排序。

其过程如下图：49 38 65 97 76 13 27 49 55 0449 1338 2765 4997 5576 04一趟排序结果： 13 27 4955 04 49 38 65 97 7613 55 38 7627 04 6549 49 97二趟排序结果： 13 04 49 38 27 49 55 65 97 76三趟排序结果： 04 13 27 38 49 49 55 65 76 97至此，希尔排序结束，整个序列的记录已按关键字非递减有序排列。

希尔排序的特点是：子序列的构成不是简单地逐段分割，而是将某个增量的记录组成一个子序列。

例如上述过程中，第一趟排序的增量是5，第二趟排序中的增量是3。

三、快速排序3.1冒泡排序快速排序是一类借助交换进行排序的方法，其中最简单的一种就是人们所熟知的冒泡排序（Bubble Sort）冒泡排序的过程很简单。

首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1]key>L.r[2].key），则将两个记录交换，然后比较第二个记录和第三个记录的关键字。

依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。

上述过程称为第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。

然后对前n-1个记录进行同样的操作。

一般地，第i趟冒泡排序是从L.r[1]到L.r[n-i+1]依次比较相邻两个记录的关键字，并在逆序时交换相邻记录。

整个排序过程需进行k（1≤k ＜n）趟冒泡排序，判别冒泡排序结束的条件是“在一趟排序过程中没有进行过交换记录的操作”。

以下是冒泡排序的过程示意图：初始关键字： 49 38 65 97 76 13 27 49第一趟排序后： 38 49 65 76 13 27 4997第二趟排序后： 38 49 65 13 27 4976 97第三趟排序后： 38 49 13 27 4965 76 97第四趟排序后： 38 13 27 49 49 65 76 97第五趟排序后： 13 27 38 49 49 65 76 97第六趟排序后： 13 27 38 49 4965 76 973.2快速排序快序排序（Quick Sort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分的纪录继续进行排序，以达到整个序列有序。

假设待排序的序列为{L.r[s],L.r[s+1],…，L.r[r]}，们首先任意选取一个记录作为支点，然后按照以下原则重新排列其余记录：将所有关键字教它小的记录都安置在它的位置之前，将所有关键字教它大的记录都放在它的位置之后。

由此可将以上序列分割成两个子序列{L.[s],L.r[s+1],…，L.r[i-1]}和{L.r[i+1],L.r[i+2],…，L.r[t]}。

这个过程称作一趟快速排序。

一趟快速排序的具体算法是：设置两个指针low和high，它们的初始值分别是low和high，设支点记录的关键字为pointkey，首先从high所指位置向前搜索找到第一个关键字小于pointkey的记录和支点交换，然后从low所指位置起向后搜索，找到第一个关键字大于pointkey的记录和支点交换，重复这两部直至low=high为止。

但是在排序过程中对支点记记录的赋值是不必要的，因为只有在一趟排序结束时low=high的位置才是pointkey的最后位置，所以先将pointkey的值赋给r[0],一趟排序结束时在赋给相应位置整个快速排序可以递归进行，子进行一趟快速排序之后再分别对得到的两组子序列进行快速排序。

其过程如下图：Pivotkey初始关键字 49 38 65 97 76 13 27 49第一次交换后 27 38 65 97 76 13 （49）49Low high第二次交换后 27 38 （49） 97 76 13 65 49Low high第三次交换后 27 38 13 97 76 （49） 65 49Low high第四次交换后 27 38 13 （49） 76 97 65 49Low high第五次交换后 27 38 13 （49） 76 97 65 49Low=high完成第一趟排序 27 38 13 （49） 76 97 65 49一次划分之后 {27 38 13} 49 {76 97 65 49} 分别进行排序 {13 38 27} {49 97 65 76} low high low high {13 27 38} {49 76 65 97} low high low high {13 27 38} {49 65 76 97} low=high low high{49 65 76 97}low=high有序序列 {13 27 38 49 49 65 76 97}四、选择排序4.1直接选择排序选择排序（Selection Sort）的基恩思想是：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。