软件技术基础-排序1

第十四章 排序排序的目的是将一组任意的数据元素(或记录)序列， 按照人们所需要的顺序，排列成有规律的按关键字有 序的序列。 如手机电话簿、目前的各种排行榜

第十四章 排序本章主要内容： 1.排序的基本概念

2.插入排序3.选择排序 4.交换排序 5.归并排序

1.排序的基本概念预备知识： 关键字(key): 通常数据对象有多个属性域，即多个数 据成员组成，其中有一个属性域可用来区分对象，作为 排序依据，该域即为关键字。如学生这个数据对象，关 键字可以是学号或身份证号。每个数据表用哪个属性域 作为关键码，要视具体的应用需要而定。

1.排序的基本概念1)排序的概念：就是整理文件中的记录，将它们按照关键字值的递增或递减的顺序 排列起来。 假设文件中含有n个记录(R1,R2,…,Rn),它们的关键字分别为k1,k 2,…,kn,我们将这n个记录重排为Ri1,Ri2,…,Rin,使得ki1≤ki2 ≤… ≤ kin(或ki1≥ki2 ≥ … ≥ kin),这就是排序。 排序前：(R1,R2,…,Rn), k1,k2,…,kn(无序) ki1≤ki2≤… ≤ kin(或ki1≥ki2 ≥ … ≥ kin) (有序)

排序后：(Ri1,Ri2,…,Rin)

1.排序的基本概念2)排序的稳定性：存在于文件中的记录，可能含有相同的关键字。对于关键字ki=kj的 记录Ri和Rj,如果在原始文件中， Ri排在Rj之前，而排序后的文件 中Ri仍然排在Rj之前，就称排序是稳定的。反之，如果排序后变成R i排在Rj之后，就称此排序是不稳定的。

1.排序的基本概念3)排序分类–按待排序记录所在位臵分：内部排序：整个排序过程都在内存中进行的排序，适用 于记录文件个数不是很多的小文件。 外部排序：当排序的文件很大时，以至内存不足以存放 全部记录，需借助对外存进行访问的排序，适用于记 录个数太多，不能一次将其全部放入内存的大文件。

–内部排序按排序所用策略分：插入排序：直接插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序 归并排序：2-路归并排序

1.排序的基本概念4)内部排序所用的存储结构： 以一维数组作为存储结构 排序过程是对记录本身进行物理重排，即通过比较和 判定，把记录移动合适的位臵。 以链表作为存储结构 排序过程中无须移动记录，仅需修改指针即可，通常 把这类排序称为表排序。 为排序文件建立辅助表 有的排序方法难以在链表上实现，此时，若仍需要避 免排序过程记录的移动，可以为文件记录一个辅助表 (如索引表),这样，排序过程中只需对这个辅助的 表进行物理重排，而不移动记录本身。

1.排序的基本概念5)排序方法的评价：执行算法所需要的时间 执行算法所需要

的附加空间 算法本身的复杂程度 排序是一种经常使用的一种运算，其所需的附加空间量一 般都不大，所以排序的时间代价是衡量排序算法好坏的最 重要的标志。

6)排序的基本操作：比较两个关键字大小 将记录从一个位臵移动到另一个位臵 排序的时间代价主要是指执行算法中关键字的比较和记录 的移动次数，因此在下面讨论的各种排序算法时，我们将 给出各算法的比较次数和移动次数。

1.排序的基本概念7)本章排序方法所用的存储结构：本章中，假设记录数组作为文件的存储结构，关键字为整数，文件 类型说明如下: typedef struct /*定义记录为结构类型*/ {int key; /*关键字域*/ datatype other; /*记录的其它域*/ }rectype; rectype R[n]; /*R为记录类型的数组*/ 其中：n为文件的记录总数。

第十四章 排序本章主要内容： 1.排序的基本概念 2.插入排序 3.选择排序 4.交换排序 5.归并排序

2.插入排序插入排序(Insertion Sort) 将待排序的一组记录分为两个区：有序区和无序区，每 次将无序区中的第一个记录按其关键字值的大小插入到 有序区中的适当位臵，直到无序区中的全部记录都插完 为止。 插入排序的分类: 直接插入排序 希尔排序

2.插入排序-直接插入排序2.1直接插入排序 1)基本思想 直接插入排序是一种最简单的排序方法。具体做法是在 插入第i个记录时，R1,R2,…,Ri-1 已排好序，这时将Ri的 关键字ki依次与关键字ki-1,ki-2,…,k1进行比较，从而 找到应该插入的位臵，然后将ki插入。注意比较的方向 R1,R2,…,Ri-1 有序区 Ri,Ri+1,…,Rn 无序区

2.插入排序-直接插入排序2)直接插入排序实例初始关键字 i=2 (33) i=3 (61) i=4 (82) i=5 (72) i=6 (11) i=7 (25) i=8 (47’) [47] 33 61 82 72 11 25 47’ [33 47] 61 82 72 11 25 47’ [33 47 61] 82 72 11 25 47’ [33 47 61 82] 72 11 25 47’ [33 47 61 72 82] 11 25 47’ [11 33 47 61 72 82] 25 47’ [11 25 33 47 61 72 82] 47’ [11 25 33 47 47’ 61 72 82]

2.插入排序-直接插入排序3)算法设计

R0 监视哨

R1,R2,…,Ri-1 有序区

Ri,Ri+1,…,Rn 无序区

2.插入排序-直接插入排序4)算法实现 InsertSort(R) rectype R[n+1]; // R[0]备用， R[1]~R[n]为n个待排序记录 {int i,j; 为何计数器从2开始 for(i = 2;i <= n;i++) //外层循环控制进行n-1趟排序 { R[0] = R[i]; //将待插入记录存放在监视哨中 j = i - 1; 为何没有j>=0判断条件 while(R[0].key < R[j].key) //在当前有序区查找插入位臵 { R[j+1] = R[j];j--; //将关键字大于R[j].key的记录后移 } 会不会丢失R[i]的值 R[j+1] = R[0]; //插入R[i] } }

2.插入排序-直接插入排序5)算法说明算法采用的是查找比较操作和记录移动操作交替进行的 方法。 具体作法是将待插入记录R[i]的

关键字依次与有序区中 的关键字R[j](j=i-1,i-2,…,1)的关键字进行比较，若R [j]的关键字大于R[i]的关键字，则将R[j]后移一个位臵， 若R[j]的关键字小于或等于R[i]的关键字，则查找过程 结束，j+1即为R[i]的插入位臵。因为关键字比R[i]大的 记录已经后移，故只需将R[i]插入该位臵即可。