5.2排序 基本概念 选择排序 三、插入排序 四、交换排序 五、归并排序 六、各种排序算法的比较 计算机软件技术基础 查找与排序
5.2 排序 一、基本概念 二、选择排序 三、插入排序 四、交换排序 五、归并排序 六、各种排序算法的比较 计算机软件技术基础 查找与排序
基本概念 1.排序 设有含n个记录的序列为{R1,R2…,Rn},其相应的关键字序列为 〔K1,K2……,Kn}。现要求确定一种排序p1,p2…pn,使其关键字满 足递增(或递减)的关系 Kp1≤K2≤…≤Kmn(或Kn1≥K2≥…≥Kpn) 使原序列成为一个按关键字有序的序列 计算机软件技术基础 查找与排序
一、基本概念 1. 排序 设有含n个记录的序列为{ R1,R2,…,Rn }，其相应的关键字序列为 { K1,K2,...,Kn }。现要求确定一种排序p1,p2,...pn, 使其关键字满 足递增（或递减）的关系： Kp1≤Kp2≤•••≤Kpn（或Kp1≥Kp2≥ •••≥Kpn） 使原序列成为一个按关键字有序的序列： { Rp1,Rp2,…Rpn } 计算机软件技术基础 查找与排序
基本概念 2.排序方法的稳定性 若K=K1(1≤i≤n,1≤j≤n,i≠j,在排序前R领先于R;,排序后 R仍领先于R,则称此排序方法是稳定的;反之称为不稳定的 3.排序的分类 若排序时待排序记录存放在内存中进行排序,则称为内部排序; 若待排序记录数量很大,在内存中一次不能容纳全部记录,需要在 非序过程中对外存进行访问,则称为外部排序 4.基本操作 1)对记录中关键字大小进行比较; 2)将记录从一个位置移到另一个位置。 计算机软件技术基础 查找与排序
一、基本概念 2.排序方法的稳定性 若Ki=Kj(1≤i≤n ,1≤j≤n ,i≠j)，在排序前Ri领先于Rj ，排序后 Ri仍领先于Rj ，则称此排序方法是稳定的；反之称为不稳定的。 3. 排序的分类 ▪ 若排序时待排序记录存放在内存中进行排序，则称为内部排序； ▪ 若待排序记录数量很大，在内存中一次不能容纳全部记录，需要在 排序过程中对外存进行访问，则称为外部排序。 4.基本操作 1）对记录中关键字大小进行比较； 2）将记录从一个位置移到另一个位置。 计算机软件技术基础 查找与排序
基本概念 5.排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动次数来衡量 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那 些受对象排序码序列初始排列及对象个数影响较大的,需要按最好 情况和最坏情况进行估算 5.算法执行时所需的附加存储 评价算法好坏的另一标准 计算机软件技术基础 查找与排序
一、基本概念 5. 排序的时间开销: ◼ 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动次数来衡量。 ◼ 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那 些受对象排序码序列初始排列及对象个数影响较大的，需要按最好 情况和最坏情况进行估算。 5. 算法执行时所需的附加存储 ◼ 评价算法好坏的另一标准。 计算机软件技术基础 查找与排序
基本概念 7.待排序的数据表 使用顺序存储结构存储 其数据类型定义如下 记录结点的类型定义 typedef struct I keywordtype key datatype data; F RECORDNODE 待排序的数据表是 RECORDNODE类型的数组 struct RECORDNODE a [MaxSize 计算机软件技术基础 查找与排序
一、基本概念 7. 待排序的数据表 ▪ 使用顺序存储结构存储 ▪ 其数据类型定义如下： ▪ 记录结点的类型定义： typedef struct{ keywordtype key; datatype data; }RECORDNODE; ▪ 待排序的数据表是RECORDNODE类型的数组 struct RECORDNODE a[MaxSize]; 计算机软件技术基础 查找与排序
、选择排序 ■选择排序是不断在待排序序列(无序区)中按记录关键 字递增(或递减)次序选择记录,放入有序区中,逐渐 扩大有序区,直到整个记录区为有序区为止 ⑩其基本思想是:每一趟(例如第i趟,i=1,2,…, n-1)在后面n-i个待排序对象中选出排序码最小的对 象,作为有序对象序列的第i个对象。待到第n1趟 作完,待排序对象只剩下1个,就不用再选了。 计算机软件技术基础 查找与排序
二、选择排序 ▪ 选择排序是不断在待排序序列（无序区）中按记录关键 字递增（或递减）次序选择记录，放入有序区中，逐渐 扩大有序区，直到整个记录区为有序区为止。 其基本思想是: 每一趟 (例如第 i 趟, i = 1, 2, …, n-1) 在后面 n-i 个待排序对象中选出排序码最小的对 象, 作为有序对象序列的第 i 个对象。待到第 n-1 趟 作完, 待排序对象只剩下1个, 就不用再选了。 计算机软件技术基础 查找与排序
、选择排序 1.直接选择排序 1)过程: 在当前无序序列中选择一个关键字最小的记录,并将它和最前端的 记录交换。重复上述过程,使记录区的前端逐渐形成一个由小到大 的有序区 2)基本步骤 (1)在一组对象a[门~a[m]中选择具有最小关键字的对象; (2)若它不是这组对象中的第一个对象,则将它与这组对象中的第一个 对象对调; (3)在这组对象中剔除这个具有最小关键字的对象。在剩下的对象 [计+1]~a[n中重复执行第(1)、(2)步,直到剩余对象只有一个为 止 计算机软件技术基础 查找与排序
二、选择排序 1. 直接选择排序 1) 过程： ▪ 在当前无序序列中选择一个关键字最小的记录，并将它和最前端的 记录交换。重复上述过程，使记录区的前端逐渐形成一个由小到大 的有序区。 2) 基本步骤 (1)在一组对象 a[i]～a[n] 中选择具有最小关键字的对象； (2)若它不是这组对象中的第一个对象, 则将它与这组对象中的第一个 对象对调; (3)在这组对象中剔除这个具有最小关键字的对象。在剩下的对象 a[i+1]～a[n]中重复执行第(1)、(2)步, 直到剩余对象只有一个为 止。 计算机软件技术基础 查找与排序
初始 25 49 25 16 08 2 3 5 最小者08 i=0 同同 交换21,08 21 最小者16 =1 0825/9 25 交换25,16 最小者21 =2 交换49,21 08{16 4925125 计算机软件技术基础 查找与排序
25 16 08 25* 49 21 i = 1 i = 2 49 08 16 25* 25 21 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 i = 0 21 25 25* 16 08 49 21 25 25* 16 08 1 2 3 4 5 6 初始 49 计算机软件技术基础 查找与排序
最小者25 =3 16 2 25 49无交换 08 2 5 6 最小者25 49元交换 e08 团网目 16 结果 各趟排序后的结果 计算机软件技术基础 查找与排序
16 25 08 25* 49 21 结果 49 25* 1 2 3 4 5 6 i = 3 08 16 21 25 最小者 25* 无交换 最小者 25 无交换 25* i = 4 49 16 21 25 08 各趟排序后的结果 计算机软件技术基础 查找与排序
1.直接选择排序 3)算法 void SelectSort(reCordnode all, int n)[ /*对记录数组a[1:n进行直接选择排序*/ int i,j, small; RECORDNODE swap for(i=1; iaLj] key)sma if (small=i)i /*交换米 swap=a Lsma a smal」=a1」;aL1」=swap 计算机软件技术基础 查找与排序
1. 直接选择排序 3）算法 void SelectSort(RECORDNODE a[],int n){ /*对记录数组a[1:n]进行直接选择排序*/ int i,j,small;RECORDNODE swap; for (i=1;ia[j].key) small=j; if (small!=i){ /*交换*/ swap=a[small]; a[small]=a[i]; a[i]=swap; } } } 计算机软件技术基础 查找与排序