《《数据结构(C／C++描述)》-阮宏一-电子教案 第9章 内排序》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-阮宏一-电子教案 第9章 内排序（95页珍藏版）》请在金锄头文库上搜索。
1、,第 9章 内 部 排 序,9.1 基 本 概 念 9.2 插 入 排 序 9.3 选 择 排 序 9.4 交 换 排 序 9.5 归 并 排 序 9.6 基 数 排 序 9.7 各 种 排 序 方 法 比 较,9.1 基本概念,一、分类： 内部排序：全部记录都可以同时调入内存进行的排序。,外部排序：文件中的记录太大，无法全部将其同时调入内存，需要多次进行内外存交换的排序。,二、定义： 设有记录序列： R1，R2 ，Rn ，其相应的 关键字序列为： K1，K2 ，Kn ; 若存在一种确定 的关系：Kp1 = Kp2 = = Kpn ，则将记录序列： R1，R2 ，Rn 排成按该关键字有序的序列
2、： Rp1，Rp2， ，Rpn 的操作，称之为排序。 关系是任意的，如通常经常使用的小于、大于等关系。,三、稳定与不稳定： 若记录序列中的任意两个记录 Ri、Rj 的关键字 Ki = Kj ； 如果在排序之前和排序之后，它们的相对位置 保持不变，则这种排序方法是稳定的，否则是不稳 定的。,插入排序的数据类型定义如下： typedef struct elemtype /待排序的数据记录类型 keytype key; /数据记录的关键字 anytype otherelem; /数据记录中的其他成份 datatype;,方法：将一个记录插入到已排好序的有序表中。 初始：有序表中只有 1 个记录。 排
3、序过程：每一遍，排好序的序列将增加一个元素。 如果序列中有 n 个元素，那么最多进行n-1 遍即可。,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,0,1,2,36,24,10,6,12,3,4,5,36,24,24,1.直接插入排序 例：,10,6,12,9.2 插 入 排 序,0,1,2,36,24,10,6,12,3,4,5,36,24,10,6,12,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,24,36,24,10,6,12,9.2 插 入 排 序,1. 直接插入排序,0,1,2,3
4、6,24,10,6,12,3,4,5,6,10,12,36,12,24,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,36,24,9.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,24,36,8.2 插 入 排 序,1. 直接插入排序,0,1,2,36,24,10,6,12,3,4,5,6,10,12,24,36,12,8.2 插 入 排 序,1. 直接插入排序,void insertsort(datatype aMaxNum+1, int n) int i,j; f
5、or(i=2;i=n;i+) /需要n-1趟才能插入所有的记录 a0=ai; /将待插入记录ai赋予监视哨a0 j=i-1; while(a0.keyaj.key) /后移记录，留出插入空位 aj+1=aj; j=j-1; aj+1=a0; /将记录插入 ,直接插入排序算法,10,20,30,40,10,20,40,50,50,30,分析: 移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 1 = n-1 j=1 移动次数 0,n-1,逆序时：比较次数 j = n (n-1)/2 j=1 移动次数 (j+2) = n(n-1)/2+2n j=1,n-1,n-1,O(n2),9.2 插
6、 入 排 序,直接插入排序算法分析：,36,24,10,6,12,36,24,12,high,10,6,12,12,方法：在已排序的序列中查找下一个元素的插入位置， 将该元素插入进去，形成更长的排序序列。 如： 12 的插入位置为下标 3。 减少了比较次数，未降低时间复杂性。,low,2.折半插入排序,9.2 插 入 排 序,36,24,10,6,12,36,24,12,high,10,6,12,12,low,12,36,24,12,high,10,6,12,12,36,24,12,10,6,12,low,2.折半插入排序,注意: 找到位置时，high 指针总是指向小于待查关键字的那个最大关键
7、字的下标地址。,退出循环,后 移,void binarysort(datatype aMaxNum+1, int n) /对顺序表s作折半插入排序 int i,j,low,high,mid; for(i=2;i=n;i+) a0=ai; /将待插入记录ai赋予监视哨a0 low=1; high=i-1; /设置初始区间 while(low=high) /该循环语句确定插入位置 mid=(low+high)/2,折半插入排序算法,if(a0.keyamid.key) low=mid+1; /插入位置在高半区中 else high=mid-1; /插入位置在低半区中 for(j=i-1;j=hig
8、h+1;j-) /high+1为插入位置 aj+1=aj; /后移记录，留出插入空位 ahigh+1=a0; /将记录插入 ,3. 希尔排序缩小增量排序,基本思想： 对待排记录序列先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是 “跳跃式”的插入排序。具体做法为：,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中，从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,例 如
9、：,16 25 12 30 47 11 23 36 9 18 31,第一趟希尔排序，设增量 d =5,11 23 12 9 18 16 25 36 30 47 31,第二趟希尔排序，设增量 d = 3,9 18 12 11 23 16 25 31 30 47 36,第三趟希尔排序，设增量 d = 1,9 11 12 16 18 23 25 30 31 36 47,1 2 3 4 5 6 7 8 9 10 11,void shellsort(datatype aMaxNum+1, int n) int d,i,j; for(d=n/2;d=1;d=d/2) /d是排序增量，每进行一趟排序，d都要
10、变小 for(i=1+d;i0 /将记录插入 ,希尔排序算法描述：,要点：对具有 n 个结点的结点序列，执行 n-1 次循环。 每次循环时挑出具有最大或最小关 键字的结点。,1. 直接选择排序,9.3 选 择 排 序,index 0 1 2 3 4 ,24 10 6 12,U N S O R T E D,直接选择排序示例：,i =1,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 2,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i =
11、2,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 3,直接选择排序示例：,index 0 1 2 3 4 ,6 10 24 12,U N S O R T E D,9.3 选 择 排 序,i = 3,直接选择排序示例：,index 0 1 2 3 4 ,6 10 12 24,9.3 选 择 排 序,直接选择排序示例：,Selection Sort: How Many Comparisons?,3 compares for values1 2 compares for values2 1 compare
12、for values 3 = 3 + 2 + 1,6 10 12 24,index 0 1 2 3 4 ,9.3 选 择 排 序,直接选择排序示例：,void selectsort(datatype aMaxNum+1,int n) datatype temp; int i,j,k; ,9.3 选 择 排 序,直接选择排序算法：,for(i=1;i=n-1;i+) /共进行n-1趟选择和交换 k=i; for(j=i;j=n;j+) if(aj.keyak.key) k=j; if (k!=i) temp=ai;ai=ak;ak=temp; ,时间复杂度 含 n 个元素的比较次数： Sum =
13、 (n-1) + (n-2) + . . . + 2 + 1 = O( n2 ),9.3 选 择 排 序,直接选择排序算法分析：,堆的定义：n 个元素的序列 k1， k2 ， ， kn ，当且仅当满足以下关系时， 称之为堆： ki = k2i ki = k2i+1 ( i = 1,2, , n/2 ) 且分别称之为小根堆和大根堆。 e.g : 序列 96, 83, 27, 11, 9 大根堆 12，36，24，85，47，30，53，91 小根堆,或,96,9,11,83,27,2,3,1,4,5,12,47,85,91,36,24,53,30,6,2,7,3,1,8,4,5,2.堆排序,大根
14、堆,小根堆,例：关键字序列 21，25，49，25*，16，08 ，试建大根堆。,怎样建堆？,先将原始序列画成完全二叉树的形式：,完全二叉树的第一个非终端结点编号必为n/2,21,i=3: 49大于08，不必调整； i=2: 25大于25*和16，也不必调整； i=1: 21小于25和49，要调整！,49,而且21还应当向下比较！,2.堆排序,交换 1号与 6 号记录,例：对刚才建好的大根堆进行排序：,2.堆排序,08 25 21 25* 16 49,从 1 号到 5 号 重新 调整为大根堆,08,25,25*,25 08 21 25* 16 49,08,25 25* 21 08 16 49,2.堆排序,从 1号到 4号 重新 调整为大根堆,2.堆排序,从 1 号到 3号 重新 调整为大根堆,2.堆排序,16 08 21 25*
