北京理工大学数据结构排序课件

END
北京理工大学数据结构查找课件（精选）
56、极端的法规，就是极端的不公。 ——西 塞罗 57、法律一旦成为人们的需要，人们 就不再 配享受 自由了 。—— 毕达哥 拉斯 58、法律规定的惩罚不是为了私人的 利益， 而是为 了公共 的利益 ；一部 分靠有 害的强 制，一 部分靠 榜样的 效力。 ——格 老秀斯 59、假如没有法律他们会更快乐的话 ，那么 法律作 为一件 无用之 物自己 就会消 灭。— —洛克60、Leabharlann 民的幸福是至高无个的法。— —西塞 罗
16、业余生活要有意义，不要越轨。——华盛顿 17、一个人即使已登上顶峰，也仍要自强不息。——罗素·贝克 18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。——马云 19、自己活着，就是为了使别人过得更美好。——雷锋 20、要掌握书，莫被书掌握；要为生而读，莫为读而生。——布尔沃

算法的空间复杂性:主要考察排序过程所需辅助存储空间的 大小。
排序算法的稳定性: 如果在对象序列中有两个对象r[i]和r[j]
，它们的关键词k[i]=k[j]，且在排序之前对象r[i]排在r[j]前面
，如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个
排序方法是稳定的，否则称这个排序方法是不稳定的。
n

1
n
d j
j2
n 1n 4
2
2019/12/5
《数据结构》国家精品课程
18
平均情况下，若待排序文件中记录所有可能排列的 概率相同，则可取上述最好情况和最坏情况的平均 情况。在平均情况下的关键词比较次数和记录移动 次数分别为
(n 1)(n 4) 4
(n 1)(n 8) 4
《数据结构》国家精品课程
21
比较次数
记录移动次数
最好
n–1
2n–2
平均
(n 1)(n 4) 4
(n 1)(n 8) 4
最坏
(n 1)(n 2) 2
(n 1)(n 4) 2
2019/12/5
《数据结构》国家精品课程
22
4.直接插入排序算法总结 优点:是算法的执行过程相当清晰，并且书写容易. 缺点:期望复杂性为O(n2) . 稳定性：直接插入排序是稳定的排序方法。 最好情况是：当被排序文件初态为正序时，算法的
12 25 25 32 36 43 48 58 65 76
d3=1
2019/12/5
《数据结构》国家精品课程
29
∟∟∟ ∟∟∟
● 希尔排序增量的取法：
d1= ∟n/2 = ∟10/2 =5 d2= ∟d1/2 = ∟5/2 =2 d3= ∟d2/2 = ∟2/2 =1

本科实验报告实验名称：排序一、实验目的2、通过编程、上机调试，进一步理解排序的方法。

3、具体尝试插入排序、快速排序、选择排序的操作步骤。

4、锻炼动手编程，独立思考的能力。

二、实验题目排序输入10个数，从插入排序、快速排序、选择排序三类算法中各选一种编程实现三、实验基础知识插入排序、快速排序、选择排序三类算法的基本思想四、实验设计方法1、概要设计（1）、插入排序（此次使用直接插入排序）void InsertionSort ( SqList &L ){ // 对顺序表L 作直接插入排序。

for ( i=2; i<=L.length; ++i )if (L.r[i].key < L.r[i-1].key){L.r[0] = L.r[i]; // 复制为监视哨for ( j=i-1; L.r[0].key < L.r[j].key; -- j )L.r[j+1] = L.r[j]; // 记录后移L.r[j+1] = L.r[0]; // 插入到正确位置}} // InsertSort（2）、快速排序（此次用的是起泡排序）V oid Bubblesort(elem R[],int n){I=n;While(i>1){lastExchangeIndex = 1;for(j=1;j<i;j++)if(R[j+1].key<R[j].key){swap(R[j],R[j+1]);lastExchangeIndex =j; //记下进行交换的记录位置}I=lastExchangeIndex ; //本趟进行过交换的最后一个记录的位置}//Bubblesort（3）、选择排序V oid selectsort(elem r[],int n){//对记录序列r[1..n]作简单选择排序。

for(i=1;i<n;++i){//选择第i小的记录，并交换到位j=selectminkey(r,i);//zai r[i..n]中选择关键字最小的记录if(i!=j) R[i] R[j];//与第i个记录交换}}//selectsort五、实验结果及数据分析数据为3 2 4 1 5 0 6 9 8 7的十个数的三种排序方法1、插入排序2、快速排序3、选择排序六、总结此次编程实验，较前几次而言稍微简单一点，并且以前用过起泡排序法，所以对排序方面比较熟悉，但是也遇到了一些问题，例如数组下标问题没处理好，让我在编程实践中花费了大量时间检查。

第九章 排序
概述
排序：将一组杂乱无章的数据按一定的规律顺 次排列起来。
文件: 它是待排序数据对象的有限集合。
关键词域(key): 通常数据对象有多个属性 域，即多个数据成员组成，其中有一个属性域 可用来区分对象，作为排序依据。该域即为关 键词域。每个文件用哪个属性域作为关键词， 要视具体的应用需要而定。即使是同一个文件 表，在解决不同问题的场合也可能取不同的域 做关键码。
( i←j–1 ． K←Kj . R←Rj . WHILE K＜Ki DO ( Ri+1←Ri ．i←i–l ) ． Ri+1←R ) ▌
k[0] k[1] k[2] k[3] k[4] k[5]
j －∞ 8
7
2
4
6
2 －∞ [8] 7
246
3 －∞ [7
8] 2 4 64 －来自 [278] 4 6
(n 1)(n 4) 4
(n 1)(n 8) 4
因此，直接插入排序的时间复杂度为 o(n2)。
比较次数
记录移动次数
最好
n–1
2n–2
平均
(n 1)(n 4) 4
排序的时间开销: 排序的时间开销是衡量 算法好坏的最重要的标志。排序的时间开销可 用算法执行中关键词的比较次数与数据的移动 次数来衡量。
各节给出算法运行时间代价的大略估算:一般 都按平均情况进行估算。对于那些受对象关键 词序列初始排列及对象个数影响较大的，需要 按最好情况和最坏情况进行估算。
排序算法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j]，它们的关键码 k[i] = k[j]， 且在排序之前，对象r[i]排在r[j]前面。如果 在排序之后，对象r[i]仍在对象r[j]的前面， 则称这个排序方法是稳定的，否则称这个 排序方法是不稳定的。