第十章 内部排序

待排记录的数据类型: 待排记录的数据类型 #define MAXSIZE 20 typedef struct{ KeyType key; }RedType; typedef struct{ RedType r[MAXSIZE+1]; int length; }SqList; /*待排序文件中记录的个数 待排序文件中记录的个数*/ 待排序文件中记录的个数 /*待排序文件类型 待排序文件类型*/ 待排序文件类型 /*记录类型的定义 记录类型的定义*/ 记录类型的定义 /*文件中记录个数的最大值 文件中记录个数的最大值*/ 文件中记录个数的最大值 typedef int KeyType; /*定义排序码类型为整数类型 定义排序码类型为整数类型*/ 定义排序码类型为整数类型
二、堆排序 ——只需要一个记录大小的辅助空间 只需要一个记录大小的辅助空间， ——只需要一个记录大小的辅助空间，每个待排序 的记录仅占有一个存储空间 堆是一个序列{k 它满足下面的条件： 堆是一个序列{k1,k2,…,kn}，它满足下面的条件： 并且k i=1,2,…,n/2 ki≤k2i并且ki≤k2i+1，当i=1,2,…,n/2 小根堆 i=1,2,…,n/2 ki≥k2i并且ki≥k2i+1，当i=1,2,…,n/2 大根堆 k 并且k k 采用顺序方式存储这个序列， 采用顺序方式存储这个序列，就可以将这个序列的每 一个元素k 看成是一棵有n个结点的完全二叉树的第i 一个元素ki看成是一棵有n个结点的完全二叉树的第i 个结点，其中k 是该二叉树的根结点。 个结点，其中k1是该二叉树的根结点。
设待排序的7记录的排序码为{312，126，272，226， 设待排序的7记录的排序码为{312，126，272，226， {312 28，165，123}，初始让d=7/2=3 以后每次让d d=7/2=3， 28，165，123}，初始让d=7/2=3，以后每次让d缩小 一半， 一半，其排序过程如图所示

最坏情况 O(n2) O(n2)
O(nlogn) O(nlogn)
辅助存储 O(1)
O(logn) O(1) O(n)
Data Structure
33
成为一个新堆？
Data Structure
27
第十章 内部排序
3、调整新堆 输出堆顶，以最后一个代替，然后和左、右
孩子比较，找小的代替，再与被破坏的堆的左、 右孩子比较，……，直至叶子结点。
称自堆顶至叶子的调整过程为“筛选”。 4、建堆
是一个反复筛选的过程，且只需从第 n/2 个 元素开始。 5、性能分析
二、性能分析
需log2n趟、需和待排记录等量的辅助空间、
时间复杂度O(nlog2n)、稳定、但很少使用。
Data Structure
31
Data Structure
32
第十章 内部排序
各种内部排序方法的比较讨论
排序方法 简单排序 快速排序
堆排序 归并排序
平均时间 O(n2)
O(nlogn) O(nlogn) O(nlogn)
1
第十章 内部排序
2、分类 内部排序：待排记录量小、随机存储器； 外部排序：待排记录量大、随机存储器+外存。
3、排序过程中两种基本操作 1）比较两个关键字的大小；
2）将记录从一个位置移动到另一个位置。 4、待排记录的存储方式
1）存放在地址连续的一组存储单元上； 2）存放在静态链表中； 3）记录本身存放在一组地址连续的存储单元内，同时 另设一个指示各个记录存储位置的地址向量。
Data Structure
19
Data Structure
20
Data Structure

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

10.2 插入排序
1、直接插入排序:续 •实现算法
Status InsertSort ( SqList &L ) { for ( i = 2; i <= L.length ; ++i ) if ( LT( L.r[i].key, L.r[i-1].key ) ) { L.r[0].key = L.r[i].key; //复制为哨兵 for ( j=i-1; LT( L.r[0].key, L.r[j].key ) ; - -j ) L.r[j+1] = L.r[j]; //后移记录 L.r[j+1] = L.r[0]; } } //InsertSort
1 物料管理
第十章 内部排序
学习内容
10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序
SORT
2 物料管理
第十章 内部排序
10.1 概述
•定义
设有记录序列：{ R1、R2 ……….. Rn } 其相应的关键字序列为： { K1、K2 ……….. Kn }; 若存在一种确定的关系： Kx <= Ky <= … <= Kz，则将记录序列 { R1、R2 ……….. Rn } 排成按 该关键字有序的序列：{ Rx、Ry ……….. Rz } 的操作，称之为排序。
•性能分析 减少了查找比较次数，但并未降低时间复杂度，仍为O(n2)。 7
SORT
8 物料管理
第十章 内部排序
10.2 插入排序
3、 希尔(shell) 排序 •基本思想 先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列 中的记录基本有序时，再对全体记录进行一次直接插入排序。