基本概念 冒泡排序 选择排序 插入排序 希尔(Shell)排序 快速排序 堆排序 归并排序 基数排序10.1 基本概念什么是排序(Sort
ing)？ 排序是计算机中经常遇到的操作。排序分为内排序和外排序.struct Record{ int key;
…;};struct Record r[n];2. 排序的几个基本概念(1)内排序与外排序 区分标准：排序过程是否全部在
内存进行。(2) 排序算法的评价标准: 稳定性，时间复杂性，空间复杂性 假设在待排序列中存在多个具有
相同关键字的记录，设ki=kj，若排序前ri排在rj的前面，排序后ri仍在rj的前面，则称这种排序方法是稳定的，否则称这种排序方法
是不稳定的。 3. 常用的排序算法(8种) 冒泡排序 选择排序 插入排序 希尔(Shell)排序 快速排序 堆排序 归并排序 基数
排序10.2 冒泡排序基本思想: (1) 两两相邻元素依次进行比较, 让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)
。(2) 在整个排序过程中，最多执行(n-1)趟。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现数据交换时
，就不用进行下一趟比较。冒泡排序示例 21 25 49 25 16 08
21 25 25 16 08 49
21 25 16 08 25 49
21 16 08 25 25 49
16 08 21 25 25 49 08 16
21 25 25 49基本冒泡排序算法void BubbleSort (Record r[ ], in
t n){ for (i=1;ir[
j+1].key) { temp=r[j]; r[j]=r[j+1];
r[j+1]=temp; }}改进冒泡排序算法void BubbleSort1(Record r[ ], int n
){ exchange=1; i=1; while (exchange) { exchange=0; fo
r (j=0; jr[j+1].key) { temp=r[j]; r[
j]=r[j+1]; r[j+1]=temp; exchange=1; } i++;
}}冒泡排序的时间复杂度考虑关键字的比较次数和对象移动次数1、在最好情况下，初始状态递增有序，一趟扫描就可完成排序，关键字的比较次
数为n-1，没有记录移动。2、最坏情况:初始状态反序，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需移动记录
3次，因此，最大比较次数和移动次数分别为：时间复杂度为O(nn),冒泡排序方法是稳定的.10.3 选择排序基本思想:
在一组元素r[i]到r[n-1]中选择最小关键字的元素, 将它与r[i]对调。 选择 排序 示 例49386597761327
4913386597764927491327659776493849132738977649654913273849769
76549132738494997657613273849496597761327384949657697选择排序算法vo
id SelectSort (Record r[ ], int n){ for (i=0; i k=i;for (j=i+1; j mp=r[i]; r[i]=r[k]; r[k]=temp; } }}选择排序的时间复杂度2. 当数据序列为正序时，移动次数为
0，数据初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。选择排序是不稳定的排序方法。1、无论初始状态如何
，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：10.4 插入排序 基本原理:（1） 将数据序列
分为2个部分, 前面已排序, 后面未排序。（2）依次考察未排序的每个数据，将其按其关键字大小，插入到前面已经排好序的适当位置上。
插入排序举例： [21] 25 49 25 16 08 [21 25
] 49 25 16 08 [21 25 49] 25 16
08 [21 25 25 49] 16 08 [16
21 25 25 49] 08 [08 16 21 25
25 49] 两种插入排序方法： 直接插入排序和折半插入排序。直接插入排序:利用顺序查找方法确定记录的插入位置
折半插入排序: 利用折半查找方法来确定记录的插入位置直接插入排序算法: void InsertSort(Record r[
], int n){ for (i=1; i= 0
&& temp.key 折半插入排序算法: void BinInsertSort(Record r[ ], int n){ for (i=1; i<
n; i++) { temp=r[i], low=0; high=i-1; while (low
<=high) { mid=(low+high)/2 if (temp.key y) high=mid-1; else low=mid+1; } for (j=i-1;
j>=low; j--) r[j+1]=r[j]; r[low]=temp; }}算法分析插入排序算法由
两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。时间复杂度为O(nn) 若初
始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。若初始时关键字递减有序，这是最坏
情况。插入排序的稳定性插入排序是一种稳定的排序方法。原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。10.5
希尔(shell)排序1959年由D.L. Shell提出，又称缩小增量排序. (Diminishing-increme
nt sort)基本思想： 插入排序的改进。 按一定的间隔将表分成若干子表,每个子表分别进行插入排序。希尔
排序示例 21 25 49 25 16 08 (1)
21 - - 25
25 - - 16 49
- - 08 21 16 08 25 25 4
9(2) 21 - 08 - 25
16 - 25 - 49 08 16
21 25 25 49(3) 08 16 21 25 25
49 08 16 21 25 25 49希尔排序中增
量d的取法：Shell最初的方案是 d= n/2, d=d/2，直到d=1。Knuth的方案是d = d/3+1。希尔排序算法:
void ShellSort(Record r[ ], int n){ for (d=n/2;d>=1;d=d/2)
//以增量d进行直接插入排序 { for (i=d; i { temp=r[i]; //暂存被插入记录 for (j=i-d; j>
0 && temp.key j=j-d) r[j+d]=r[j];
//记录后移 d个位置 r[j+d]=temp } }} 为什么shell排序的时
间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较
少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在sh
ell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐
增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。希尔排序的时间复杂度对希尔排序的复杂度的分析
很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到
。Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。希尔排序的稳定性：希尔排序是一种不稳
定的排序方法。如序列 3, 2, 2, 510.6 快速排序1962年，伦敦Elliot Brothers Ltd公
司的Tony Hoare发明了快速排序（Quick Sort）方法。实际上快速排序名副其实，它几乎是最快的排序算法，被评为20世纪
十大算法之一。其思想是： 取待排序列中某个元素的值作为基准值，将待排序列划分为两个部分，左边部分的所有元素都小于等于
这个基准值，而右边部分的所有元素都大于等于这个基准值。 然后,对左右两个子表用同样的方法(递归)进行划分.快速排序示
例(第一趟划分)4938659776132749 38659776132749273865977613 492738
97761365492738139776 6549273813 76976549273813 49 76 49 6549
49temp划分算法int Partition(Record r[ ], int i, int j){ temp= r[i
]; while (i= temp.key) j--；
if (i key) i++; if (i eturn i;}void QuickSort (Record r[ ], int i, int j ){ if (i<
j) { pivot=Partition(r, i, j); QuickSort(r, i, pivot-
1); QuickSort(r, pivot+1, j); }} 初始调用为QuickSort(r, 1, n)
快速排序的时间复杂度2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。考
虑关键字的比较次数和对象移动次数1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边
（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为
设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加
上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有： 快
速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(nn)；最好时间复杂度为O(nlog2n)。
可以证明，快速排序的平均时间复杂度也是O(nlog2n)。 快速排序是不稳定的排序方法。10.7 堆排序堆排
序是选择排序的改进（1964提出）。在排序过程中，将r[1]到r[n]看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和
孩子结点之间的内在关系来选择最小元素。堆的定义： n个数据序列K1, k2, ... ,Kn称为堆，当且仅当该序列满
足特性： 此种情况称为小顶堆。或者，均大于也可以。 此种情况情况称为大顶堆。 从堆的定义可以看出，堆实质上是满足如下性质
的二叉树：树中任一非叶子结点的值均小于等于它的孩子结点的值。或者，树中任一非叶子结点的值均大于等于它的孩子结点的值。1015562
53070101556253070小顶堆示例705630251510705630251510大顶堆示例堆排序的过程：（1）将无序序
列建成一个堆。（2）输出堆顶元素，将剩余元素调整为一个新堆。 堆排序的第一个工作是建堆，即把整个记录数组r[1]到r[n]调
整为一个堆。显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i >= low(n/2)的结点都是叶子，因此以这些结点为根的子
树都已是堆。这样，我们只需依次将序号为low(n/2)，low(n/2)-1，...，1的结点作为根的子树都调整为堆即可。
下面以大顶堆为例进行说明： 若已知结点r[i]的左右子树已是堆，如何将以r[i]为根的完全二叉树也调整为堆？ 解决这一
问题可采用“筛选法”，其基本思想是：因为r[i]的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在r
[i]和它的左右孩子中选取关键字最大的结点放到r[i]的位置上。若r[i]的关键字已是三者中的最大者，则无须做任何调整，以r[i]
为根的子树已构成堆，否则必须将R[i]和具有最大关键字的左孩子r[2i]或右孩子r[2i+1]进行交换。假定r[2i]的关键字最大
，将r[i]和r[2i]交换位置，交换之后有可能导致r[2i]为根的子树不再是堆，但由于r[2i]的左右子树仍然是堆，于是可以重复
上述过程，将以r[2i]为根的子树调整为堆，...，如此逐层递推下去，最多可能调整到树叶。例子：关键字序列为 42，13，91，2
3， 24， 16，05，88，n=8，故从第四个结点开始调整4213912324160588421391232416058842
139188241605234213918824160523不调整42139188241605234213918824160523
4288912324160513428891232416051391884223241605139188422324160513建
成的堆筛选算法: (假设r[k]的左右子树均为堆，将以r[k]为根的完全二叉树建成大顶堆）void Sift(Record r[
], int k , int m){ i = k ; j = 2 i ; //置i 为要筛选的结点，j为i的左
孩子 while (j<=m) //筛选还没有进行到叶子结点 { if (j & r[j].key ，j为较大者 if (r[i].key>r[j].key) break;
//根结点已经大于左、右孩子中的较大者 else {
r[i]←→r[j]; //将根结点与结点j交换 i=j ; j=2i;
//被筛结点位于原来结点j的位置 } }} 上述算法只是对一个指定的结点进
行调整。有了这个算法，则将初始的无序区r[1]到r[n]建成一个大顶堆，可用以下语句实现：for (i = n/2; i>=1;
i--) Sift(r, i, n) 由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所
以，应该将r[1]和r[n]交换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区r[1]到r[n-1]调整为堆
。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用Sift函数将r[1]到r[n-1]调整为大根堆，选出最大关键字放入堆顶
，然后将堆顶与当前无序区的最后一个记录r[n-1]交换，如此反复进行下去。9188422324160513918842232416
0513（1）初始堆R[1]到R[8]13884223241605911388422324160591（2）第一趟排序之后（3）重
建的堆r[1]到r[7]88244223131605918824422313160591052442231316889105244
22313168891（4）第二趟排序之后（5）重建的堆r[1]到r[6]4224162313058891422416231305
8891（6）第三趟排序之后05241623134288910524162313428891（7）重建的堆r[1]到r[5]242
31605134288912423160513428891（8）第四趟排序之后13231605244288911323160524
428891（9）重建的堆r[1]到r[4]23131605244288912313160524428891（10）第五趟排序之后
05131623244288910513162324428891（11）重建的堆r[1]到r[3]1613052324428891
1613052324428891（12）第六趟排序之后05131623244288910513162324428891（13）重建
的堆r[1]到r[2]13051623244288911305162324428891（14）第七趟排序之后05131623244
288910513162324428891堆排序算法：void HeapSort(Record r[ ], int n){
for ( i= n/2; i >=1; i - -) Sift(r, i, n); //初
始建堆，从最后一个非终端结点至根结点进行筛选 for (i=1; i 堆的操作 { r[1]←→r[n-i+1]; Sift(r, 1, n?i); }}堆排序的时间
复杂度堆排序的时间复杂性为O(n log2n) 空间复杂性为 O(1)堆排序是不稳定的排序方法。1
0.8 归并排序基本原理，通过对两个有序数据序列的归并来实现排序。所谓归并是指将若干个已排好序的部分合并成一个有序的部分。归并分
类： 二路归并、三路归并、多路归并归并排序的实现有两种方法： 非递归方法和递归方法。二路归并的基本思
想: 设有两个有序表A和B，变量i和j分别是两表的当前指针。 设表C是归并后的新有序表，变量k是它的当
前指针。 当对A和B进行遍历时，依次将关键字小的数据放到C中，当A或B遍历结束时，将另一个表的剩余部分拷贝到新表中。
归并排序就是利用“二路归并”操作实现排序的。其基本思想是： 将待排序列r[0]到r[n-1]看成n个长度为1的有序子序
列，把这些子序列两两归并，便得到(n/2)个有序的子序列。然后再把这(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长
度为n的有序序列。非递归实现归并排序示例(25) (57) (48) (37) (12)
(92) (86)(25 57) (37 48) (12 92)
(86)(25 37 48 57) (12 86
92)(12 25 37 48 57 86 9
2)二路归并算法:void Merge(Record r[ ], Record r1[ ], int s, int m, int
t){ i=s; j=m+1; k=s;while (i<=m && j<=t) if (r[i].key<=r[j]
.key) r1[k++]=r[i++]; else r1 [k++]=r[j++]; if (i<=m)
while (i<=m) r1[k++]=r[i++]; //若第一个子序列没处理完，则进行收尾处理 else
while (j<=t) r1[k++]=r[j++]; //若第二个子序列没处理完，则进行收尾处理}一趟归并算法:void
MergePass(Record r[ ], Record r1[ ], int n, int h){ i=1;whi
le (i≤n-2h+1) //待归并记录至少有两个长度为h的子序列{ Merge(r, r1, i, i+h-1,
i+2h-1); i+=2h;} if (i 待归并序列中有一个长度小于h else for (k=i; k<=n; k++) r1[k]=r[k]; //待归并序列中
只剩一个子序列}归并排序非递归实现算法：Void MergeSort1(int r[],int n){ int r1[]; h
=1; while (h ss(r1,r,n,h); h=2h; }} 归并排序递归实现算法：void MergeSort2(int r[],
int r1[ ],int s,int t){ if (s==t) r1[s]=r[s]; // 排序结果放在r1中 els
e { m=(s+t)/2; MergeSort2(r,r2,s,m); MergeSort2(r,r2,
m+1,t); Merge(r2,r1,s,m,t) }} 算法复杂性分析 归并排序是稳定的排序方法。
归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做(log2n)趟归并，
每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O (n log2n)，辅助数组所需的空间为O(n)。10.9
基数排序基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。下面先介绍多关键字排序多
关键字排序方法示例如：对扑克牌的排序。每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，也
可以先对面值排序。多关键字排序原理：根据组成关键字的各位的值进行排序。 实现基数排序的两种方法： 1 最高位优先(MSD
)排序：从关键 字的高位到低位依次排序 2 最低位优先(LSD)排序：从关键字 的低位到高位依次排序
多关键字排序（续）LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：
(Ki1,Ki2,..., Kid)如：对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的
组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3 ,K2 , K1的顺序对所有对象排序。基数排序基数排序是
一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键字进行排序。此时可将单关键字K看成是一个子关键字组：
(Ki1,Ki2,..., Kid)排序过程： 设关键字共有d位，让j= d, d-1
,...,1, 依次执行d次“分配”与“收集”。 示例:1792083069385998455927133B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 27193339845530620817985992719333984553062081798599B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 33984306208955859271179933062089335585927117998493B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e 17930698485993355932082719335593179208271306859984各种排序方法的性能比较1. 时间复杂性： 最好情况、最坏情况、平均情况2. 空间复杂性3. 稳定性End.希望同学们认真复习，争取期末考试好成绩！ |
|
