《[经济学]第10章 内部排序》由会员分享，可在线阅读，更多相关《[经济学]第10章 内部排序（92页珍藏版）》请在金锄头文库上搜索。
1、1,9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较,第9章 内部排序,2,本章重点难点,重点：插入排序、快速排序、选择排序、堆排序、归并排序、基数排序的思想和算法。,难点：堆排序的思想和算法，在实际应用中如何根据实际情况，选择最优的排序算法。,3,9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较,第9章 内部排序,4,9.1 概述,排序方法的稳定和不稳定,张三 80分 李四 75分 王五 85分 陈六 90分,李四 75分 张三
2、80分 王五 85分 陈六 90分,陈六 90分 王五 85分 张三 80分 李四 75分,当需要排序的关键字都不相同时,排序的结果是唯一的;,5,当排序的关键字中存在相同的情况时,排序方法不唯一;,张三 80分 李四 75分 王五 85分 陈六 80分,李四 75分 张三 80分 陈六 80分 王五 85分,李四 75分 陈六 80分 张三 80分 王五 85分,在排序前后，含相等关键字的记录的相对位置保持不变，称这种排序方法是稳定的；,9.1 概述,反之，含相等关键字的记录的相对位置有可能改变，称这种排序方法是不稳定的。,6,内部排序和外部排序,9.1 概述,排序期间文件的全部记录不能同时
3、存放在计算机的内存中，要借助计算机的外存才能完成排序，称之为“外部排序”。,在排序过程中，只使用计算机的内存存放待排序记录，称这种排序为内部排序。,内外存之间的数据交换次数就成为影响外部排序速度的主要因素。,7,#define MAXSIZE 1000 / 待排顺序表最大长度,typedef int KeyType; / 关键字类型为整数类型,typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型,typedef struct RcdType rMAXSIZE+1; / r0闲置 int le
4、ngth; / 顺序表长度 SqList; / 顺序表类型,存储结构,9.1 概述,8,效率分析,9.1 概述,(1) 时间复杂度： 关键字的比较次数和记录移动次数。 (2) 空间复杂度： 执行算法所需的附加存储空间。 (3) 稳定算法和不稳定算法,9,9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较,第9章 内部排序,10,9.2、插入排序,9.2.1 直接插入排序 9.2.2 其他插入排序 /自学 9.2.3 希尔排序,11,插入排序的思想,9.2.1 直接插入排序,(1)一个记录是有序的； (2)从第二个记
5、录开始，将每个记录插入到已排好序的序列中； (3)一直进行到第n个记录。,12,算法概述,9.2.1 直接插入排序,(1)将序列中的第1个记录看成是一个有序的子序列; (2)从第2个记录起逐个进行插入，直至整个序列变成按关键字有序序列为止； 整个排序过程需要进行比较、后移记录、插入适当位置。从第二个记录到第n个记录共需n-1趟。,13,9.2.1 直接插入排序,直接插入排序示例演示,14,void InsertionSort ( SqList / 插入到正确位置 / InsertSort,9.2.1 直接插入排序,直接插入排序算法,15,算法分析,9.2.1 直接插入排序,(1)稳定性 直接插
6、入排序是稳定的排序方法。 (2)算法效率 a.时间复杂度 最好情况:比较O(n),移动O(1); 最坏情况:比较O(n2),移动O(n2); 平均O(n2) b.空间复杂度 O(1)。,16,折半插入排序思想,9.2.2 其它插入排序,(1)在直接插入排序中，r1i-1 是一个按关键字有序的有序序列; (2)可以利用折半查找实现“在r1i-1中查找ri的插入位置”; (3)称这种排序为折半插入排序。,17,0 1 2 3 4 5 6 7 8 9 10 查22 05 13 19 21 37 56 64 75 80 88 90,low,high,mid= (low+high)/2,high=mid
7、-1,mid,low=mid+1,mid,low=mid+1,high=mid-1,9.2.2 其它插入排序,折半插入排序的演示过程,18,void BiInsertionSort ( SqList / 插入 / for / BInsertSort,9.2.2 其它插入排序,折半插入排序算法,19,low = 1; high = i-1; while (low=high) m = (low+high)/2; / 折半 if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区 else low = m+1; / 插入点在高半区 ,9.2.2 其它插入排序,折半插入
8、排序算法,20,9.2.3 希尔排序,(1)对待排记录序列先作“宏观”调整，再作“微观”调整。,(2)所谓“宏观”调整，指的是，“跳跃式” 的插入排序。,希尔排序的思想,21,(1)将记录序列分成若干子序列，分别对每个子序列进行插入排序。,(2)其中，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.2.3 希尔排序,希尔排序概述,22,16 25 12 30 47 11 23 36 9 18 3
9、1,第一趟希尔排序，设增量 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,9.2.3 希尔排序,希尔排序演示,23,void ShellInsert ( SqList / 插入 ,希尔排序算法,9.2.3 希尔排序,24,void ShellSort (SqList /一趟增量为dltak的插入排序 ,希尔排序算法,9.2.3 希尔排序,25,(1)稳定性 希尔排序是不
10、稳定的排序方法。 (2)算法效率 (1)时间复杂度 平均O(n1.3)到平均O(n1.5) (2)空间复杂度 O(1)。,希尔排序算法分析,9.2.3 希尔排序,26,9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序 9.7 内部排序方法的比较,第9章 内部排序,27,9.3 快速排序,9.3.1、起泡排序 9.3.2、快速排序,28,基本思想,9.3.1 起泡排序,(1)从第一个记录开始，两两记录比较，若L.r1.keyL.r2.key，则将两个记录交换； (2)第1趟比较结果将序列中关键字最大的记录放置到最后一个位置，称为“沉底”，而最
11、小的则上浮一个位置; (3)n个记录比较n-1遍(趟)。,29,6 1 2 3 4 5,1 6 2 3 4 5,1 2 6 3 4 5,1 2 3 6 4 5,1 2 3 4 6 5,1 2 3 4 5 6,第一趟,1 2 3 4 5 6,第二趟,示例演示,9.3.1 起泡排序,30,算法,void BubbleSort(SqList ,9.3.1 起泡排序,31,算法分析,(1)稳定性 起泡排序是稳定的排序方法。 (2)时间是复杂性 最好情况：比较O(n),移动O(1) 最坏情况：比较O(n2),移动O(n2) 平均情况：O(n2) (3)空间复杂性 O(1),9.3.1 起泡排序,32,基
12、本思想,任取待排序对象序列中的某个对象v(枢轴，基准，支点)，按照该对象的关键字大小，将整个序列划分为左右两个子序列； (1)左侧子序列中所有对象的关键字都小于或等于对象v的关键字； (2)右侧子序列中所有对象的关键字都大于或等于对象v的关键字； (3)对象v则排在这两个子序列中间(也是它最终的位置)。,9.3.2 快速排序,33,初始关键字 49 49* 65 97 17 27 50,i,j,一次交换 27 49* 65 97 17 49 50,二次交换 27 49* 49 97 17 65 50,三次交换 27 49* 17 97 49 65 50,四次交换 27 49* 17 49 97
13、 65 50,完成一趟排序,j,i,j,i,j,i,i,j,j,i,示例演示,9.3.2 快速排序,34,初始关键字 49 49* 65 97 17 27 50,low,high,一次交换 27 49* 65 97 17 49 50,high,low,high,low,while (low=pivotkey) -high; L.rlow L.rhigh;,pivotkey=L.rlow.key;,while (lowhigh),算法关键语句,9.3.2 快速排序,35,int Partition(SqList / 返回枢轴位置 / Partition,算 法,9.3.2 快速排序,36,初始关
14、键字 49 49* 65 97 17 27 50,i,j,一次交换 27 49* 65 97 17 50,j,i,j,i,9.3.2 快速排序,一次交换 27 49* 97 17 65 50,37,int Partition(SqList / 返回枢轴位置 / Partition,9.3.2 快速排序,38,void QSort(SqList / 对高子表递归排序 / QSort,9.3.2 快速排序,39,算法分析,9.3.2 快速排序,(1)稳定性 快速排序是不稳定的排序方法。 (2)时间复杂度 最坏情况： 1,2,3,n n,n-1,2,1。 比较O(n2), 移动O(n2) n,n-1,2,1。,40,时间复杂性最好情况是每次选择的基准把左右分成相等两部分： C(n)n+2C(n/2) n+2(n/2+2C(n/4)=2n+22C(n/22) kn+2kC(n/2k) 最后组中只有一个元素：n=2k,k=log2n, C(n)nlog2n+nC(1) 最好情况的时间复杂度为O(nlog2n) 平均时间复杂度也是O(nlog2n),9.3.2 快速排序,算法分析,41,(3)空间复杂度 由于快速排序是一个递归过程，需一个栈的附加空间，栈的平均深度为O
