中南大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 数据结构与算法概述（2.8）排序

28排序 2.8.1概述 1、排序的功能:将一个数据元素(或记录)的任意 序列,重新排成一个按关键字有序的序列。 2、排序过程的组成步骤: °首先比较两个关键字的大小; 然后将记录从一个位置移动到另一个位置。 2/22 202l/2/

2021/2/22 4 2.8 排 序 2.8.1 概 述 1、排序的功能：将一个数据元素（或记录）的任意 序列，重新排成一个按关键字有序的序列。 2、排序过程的组成步骤： • 首先比较两个关键字的大小； • 然后将记录从一个位置移动到另一个位置

假设待排序的记录存放在地址连续的 组存储单元中,那么这种存储方式 下的数据类型可描述为 #define max 20 key info typedef struct int key float otherinfo: 234 MAX RetYpe; 2/22 202l/2/

2021/2/22 5 假设待排序的记录存放在地址连续的 一组存储单元中，那么这种存储方式 下的数据类型可描述为： MAX 0 1 2 3 4 … … … key info #define MAX 20 typedef struct { int key; float otherinfo; }RedType;

直接插入排序 插入排序 折半插入排序 选择排序」单选择排序 堆排序 排序方法 起泡排序 突换排序 快速排序 归并排序 2/22 202l/2/

2021/2/22 6 排序方法 插入排序 选择排序 交换排序 归并排序 直接插入排序 折半插入排序 简单选择排序 堆排序 起泡排序 快速排序

282插入排序 直接插入、折半插入 1、直接插入排序: 基本思想:从数组的第2号元素开始,顺 序从数组中取出元素,并将该元素插入 到其左端已排好序的数组的适当位置上。 举例:图8-2-1 2/22 202l/2/

2021/2/22 7 2.8.2 插入排序 直接插入、折半插入 1、直接插入排序: 基本思想：从数组的第2号元素开始，顺 序从数组中取出元素，并将该元素插入 到其左端已排好序的数组的适当位置上。 举例：图8-2-1

2.8.2插入排序 直接插入、折半插入 1、直接插入排序: 基本思想:从数组的第2号元素开始,顺序从数组中取出元素, 并将该元素插入到其左端已排好序的数组的适当位置上 待排元素序列:|532736156942 第一次排序:275336156942 对于有n个数 据元素的待排 第二次排序:1273653]156942 序列,插入操 作要进行n-1 第三次排序:15273653]6942 次 第四次排序:1152736536942 该算法适合于n较 第五次排序:152736425369小的情况,时间复 杂度为O(n2 直接插入排序示例

2021/2/22 8 2.8.2 插入排序 直接插入、折半插入 该算法适合于n 较 小的情况，时间复 杂度为O(n2 ). 1、直接插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素， 并将该元素插入到其左端已排好序的数组的适当位置上 待排元素序列：[53] 27 36 15 69 42 第一次排序： [27 53] 36 15 69 42 第二次排序： [27 36 53] 15 69 42 第三次排序： [15 27 36 53] 69 42 第四次排序： [15 27 36 53 69] 42 第五次排序： [15 27 36 42 53 69] 直接插入排序示例 对于有n个数 据元素的待排 序列，插入操 作要进行n-1 次

插入算法如下: 方法:K与K1,K12K1依次比较直到找到应插入的位置。 void insertSort(RedType ll, int n) f int i,j; for(i=2; K<n; i++) if(Ll. key<Li-1.key {L0=I[; *作为监视哨* for(j=1-1; LIO.key<Ll. key;--j) L[i+1]-L|ji;记录后移* Lj+1|=L|0l;插入* 2021/2/22

2021/2/22 9 void insertSort(RedType L[ ],int n) { int i ,j; for(i=2; i<=n; i++) if(L[i].key<L[i-1].key) { L[0]=L[i]; /* 作为监视哨*/ for( j=i-1; L[0].key<L[j].key; − −j ) L[j+1]=L[j]; /* 记录后移*/ L[j+1]=L[0]; /* 插入 */ } } 插入算法如下： 方法:Ki与Ki-1 ,K i-2 ,…K1依次比较,直到找到应插入的位置

10 2、折半插入排序 折半插入排序在寻找插入位置时,不是逐 个比较而是利用折半查找的原理寻找插入位置。 待排序元素越多,改进效果越明显。 折半插入排序的条件: 在有序序列中插入一个关键字 举例,图8-2-2 2/22 202l/2/

2021/2/22 10 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐 个比较而是利用折半查找的原理寻找插入位置 。 待排序元素越多，改进效果越明显。 折半插入排序的条件： 在有序序列中插入一个关键字。 举例，图8-2-2

2、折半插入排序 ll 折半插入排序在寻找插入位置时,不是逐个比较而是利用折半 查找的原理寻找插入位置。待排序元素越多,改进效果越明显 例:有6个记录,前5个已排序的基础上,对第6个记录排序 1527365369142 ↑low ↑mid high (42>36) 1527365369]42 ↑ow↑high ↑mid (42<53) 1527365369]42 个high↑ow( high<low!查找结束,插入位置为ow或hgh+1) 152736425369

2021/2/22 11 2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半 查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 例：有6个记录，前5个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42  low mid  high [ 15 27 36 53 69 ] 42 low  high mid [ 15 27 36 53 69 ] 42 high low [ 15 27 36 42 53 69 ] (high36 ) ( 42<53 )

void BinsertSort(RedType LI l,int n) 折半插入排序减少 i int i, low, high, mid; 了关键字的比较次 for(i=2;i=high+1; --j) L[j+1=L[l; 记录后移 Lhigh+lOI 插入* or }/折半插入排序* 2/22 202l/2/

2021/2/22 12 void BinsertSort(RedType L[ ],int n) { int i,low,high,mid; for(i=2; i=high+1; − −j ) L[j+1]=L[j]; /* 记录后移*/ L[high+1]=L[0]; /* 插入*/ } /* for*/ }/*折半插入排序*/ 折半插入排序减少 了关键字的比较次 数，但记录的移动 次数不变，其时间 复杂度与直接插入 排序相同。 /*折半后的位置*/

13 2.8.3选择排序 简单选择排序、堆排序 1、简单选择排序 思想:首先从1~n个元素中选出关键字最小的记录交 换到第一个位置上。然后再从第2个到第n个元素中 选出次小的记录交换到第二个位置上,依次类推 时间复杂度为O(m2), 适用于待排序元素较少的情况 举例:图8-2-3 2/22 202l/2/

2021/2/22 13 1、简单选择排序 思想：首先从1~n个元素中选出关键字最小的记录交 换到第一个位置上。然后再从第2 个到第n个元素中 选出次小的记录交换到第二个位置上，依次类推。 时间复杂度为O(n2 )， 适用于待排序元素较少的情况。 2.8.3 选择排序 简单选择排序、堆排序 举例：图8-2-3