首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


第九章
【实验目的】

内部排序算法的实现

1. 熟练掌握各种排序的算法思想、方法及稳定性; 2. 掌握快速排序、堆排序、归并排序的方法实现; 3. 对已知一组数据,能写出其具体的排序过程、算法及完整程序,并上机调试; 4. 了解每一种排序的时间及空间复杂度。

第一节 知识准备

一、 基本概念和术语 1. 排序(Sorting)是计算机程序设计中的一种重要操作,其功能是对一个数据元素集合或序列重新排列成 一个按数据元素的某个数据项有序的序列。 2. 排序码或关键码:数据元素可以有多个数据项,而作为排序依据的数据项称为“排序码”,也即数据 元素的关键码。 表 9-1 是一个职工登记表,若以每个记录的职工号为关键字,并作为排序码,则所有 7 条记录可简记为: {(101,348),(102,374),(103,324),(104,305),(105,429),(106,284),(107, 324)}

表 9-1

职工数据表

职工号 姓名 基本工资 出生日期 车间号 101 王英 348 51/04/25 3 102 吴进 374 61/03/12 2 103 赵飞 324 53/06/28 4 104 刘晓 305 70/03/26 3 105 李平 429 59/12/20 1 106 卢明 284 75/01/05 5 107 李敏 324 64/10/01 1

若按基本工资为排序码,并以递增次序对记录进行重排,则结果为:{(106,284), (104,305), (103, 324),(107,324),(101,348),(102,374),(105,429)}

若以每个记录的车间号码为排序码,并以递减次序对记录进行重排,则结果为:{(106,5),(103,4), (101,3),(104,3),(102,2),(105,1),(107,1)}。 一组记录按排序码的递增或递减次序排列得到的结果称为有序表;而把排序前的表称之为无序表。若有序 表是按排序码递增的顺序排列的,则称为升序表或正序表;反之则称之为降序表或逆序表。 3. 排序的稳定性:对于具有同一排序码的多个记录来说,若对任意的数据元素序列,使用某种排序方法 按关键码进行排序,具有相同关键码的不同元素间的位置领先关系,排序前与排序后保持一致,称此排序方 法是稳定的。 4. 排序的不稳定性:若对任意的数据元素序列,使用某种排序方法按关键码进行排序,具有相同关键码的 不同元素间的位置领先关系,排序前与排序后不能保持一致的排序方法则称为不稳定的。 5. 内部排序:待排序列完全在内存中进行的排序过程,称为内排序。 6. 外部排序:排序过程需要不断在内存和外存之间进行数据交换,这种排序过程叫外排序。 二、内部排序的分类 1. 插入排序 设有 n 个记录,存放在数组 r 中,重新安排记录在数组中的存放顺序,使得按关键码有序。即: r[1].key≤r[2].key≤??≤r[n].key。 按照插入一个元素到一个有序表中的方法不同,可以分为:直接插入排序、折半插入排序(2-路插入排序) 及希尔排序(Shell’s Sort)。 (1) 直接插入排序 是一种最简单的排序方法,其基本操作是每次从无序表中取出一个元素,将之插入到已排好序的表中的适 当位置,从而得到一个新的、记录数增 1 的 1 有序表。 对 n 个记录的表,可从第 2 个记录开始直到第 n 个记录,逐个向有序表中进行插入操作,从而得到 n 个记 录按关键码有序的表。 设 r[1] ,r[2],??,r[j-1]为长为 j-1 的有序表,现要将 r[j]插入这个有序表,形成长为 j 的新的有 序表,算法过程如下: 【算法描述】 Step1: i=j-1; Step2: Step3: r[0]=r[j]; //设置 r[0]为哨兵 //从第 j-1 个记录向前测试插入位置 若 r[0].key≥r[i].key,转 Step4。 若 r[0].key < r[i].key 时, //调整待插入位置 //插入位置确定

r[i+1]=r[i];i=i-1;转 Step2。

Step4:

r[i+1]=r[0];结束。

//存放待插入记录

【例题分析】向有序表中插入一个记录的过程如下: 初始情况:设 r[1],r[2],r[3],r[4]已经有序,现插入 r[5] r[1] 2 j=5 r[0]=r[j];i=j-1; 2 1]为待插入位置 i=4,r[0] < r[i],r[i+1]=r[i];i--; 2 i=3,r[0] < 10 //调整待插入位置 18 □ 25 10 18 25 //初始化,设置待插入位置 □ //r[i+ r[2] 10 r[3] 18 r[4] 25 r[5] 9

r[i],r[i+1]=r[i];i--; 2 10

//调整待插入位置 □ 18 25

i=2,r[0] <

r[i],r[i+1]=r[i];i--; 2 □

//调整待插入位置 10 18 //插入记录 25

i=1,r[0]

≥r[i],r[i+1]=r[0]; 2 9 10

18

25

//

插入过程结束

(2) 希尔排序:先将待排序记录的序列按某个间隔长度分割成为若干个子序列分别进行直接插入排序, 重复进行数据分割,每次分割的间隔长度逐步缩小,直到最后间隔长度为 1 时,对全体记录进行一次直接 插入排序,这时所有记录按关键字有序,排序结束。具体排序过程如下: ① 选择一个步长序列 t1,t2,?,tk,其中 ti<ti+1,tk=1; ② 按步长序列个数 k,对序列进行 k 趟排序; ③ 每趟排序,根据对应的步长 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子系列进行直接 插入排序。当步长因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。 【例题分析】待排序列为 39,80,76,41,13,29,50,78,30,11,100,7,41,86。

步长因子分别取 5、3、1,则排序过程如下: p=5 39 80 76 41 13 29 50 78 30 11 100 7 41 86

└─────────┴─────────┘

└─────────┴──────────┘ └─────────┴──────────┘ └─────────┴──────────┘ └─────────┘ 子序列分别为{39,29,100},{80,50,7},{76,78,41},{41,30,86},{13,11}。 第一趟排序结果: p=3 29 7 41 30 11 39 50 76 41 13 100 80 78 86

└─────┴─────┴─────┴──────┘ └─────┴─────┴─────┴──────┘ └─────┴─────┴──────┘ 子序列分别为{29,30,50,13,78},{7,11,76,100,86},{41,39,41,80}。 第二趟排序结果: p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100

此时,序列基本“有序”,对其进行直接插入排序,得到最终结果: 7 11 13 29 30 39 41 41 50 76 78 80 86 100

希尔排序的效率是非常高的,因为它有效地利用了直接插入排序的优点:开始分组的时候,每组 的元素比较少,排序速度比较快;到后来,每组元素比较多时,元素已经基本有序了,这样排序速度也比 较快。 (3)2-路插入排序: 设在一个已排好序的序列中 v[0],v[1],?,v[i-1]中,在插入 v[i]时,利用折半查找法寻找 v[i]的插 入位置来完成的排序过程。 2. 交换排序:主要是通过两两比较待排记录的关键码,若发生与排序要求相逆,则交换之。根据交换记录 的不同,可分为:快速排序、冒泡排序。 (1) 快速排序(Quick Sort)是通过比较关键码、交换记录,以某个记录为界(该记录称为支点),将待 排序列分成两部分。其中,一部分所有记录的关键码大于等于支点记录的关键码,另一部分所有记录的关 键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程,称为一次划分。对 各部分不断划分,直到整个序列按关键码有序,整个排序结束。 此种排序方法是不稳定的,且其时间复杂度在平均状况时为 ,最坏情况其时间复杂度为 。

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐