最新数据结构王红梅排序技术教学讲义ppt.ppt

《最新数据结构王红梅排序技术教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构王红梅排序技术8.1概述排序：给定一组记录的集合{r1,r2,……,rn}，其相应的关键码分别为{k1,k2,……,kn}，排序是将这些记录排列成顺序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。正序：待排序序列中的记录已按关键码排好序。逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。排序的基本概念从操作角度看，排序是线性结构的一种操作排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键

2、值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。排序的基本概念学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……8.1概述排序的分类1.基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为Ω（nlog2n）。（1）插入排序（2）交换排序（3）选择排序（4）归并排序2.不基于比较：根据关键码的分布特征。排序的基本概念

3、8.1概述1.基本操作。内排序在排序过程中的基本操作：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。排序算法的性能8.1概述排序算法的存储结构从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。假定2：将待排序的记录序列排序为升序序列。intr[n+1];//待排序记录存储在r[1]~r[n]，r[0]留做他用假定1：

4、采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。8.1概述8.2插入排序插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。直接插入排序有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……8.2插入排序基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。（1）如何构造初始的有序序列？（2）

5、如何查找待插入记录的插入位置?直接插入排序需解决的关键问题?8.2插入排序直接插入排序过程示例r0123456211825221025*212125i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5r[0]的作用?暂存单元监视哨8.2插入排序解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。关键问题(1)如何构造初始的有序序列？算

6、法描述：for(i=2;i<=n;i++){插入第i个记录，即第i趟直接插入排序；}8.2插入排序关键问题(2)如何查找待插入记录的插入位置?解决方法：在i-1个记录的有序区r[1]~r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。r[0]有两个作用：1.进入循环之前暂存了r[i]的值，使得不致于因记录的后移而丢失r[i]的内容；2.在查找插入位置的循环中充当哨兵。算法描述：r[0]=r[i];j=i-1;while(r[0]

7、}8.2插入排序voidinsertSort(intr[],intn){for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0]=r[i-1]，内层循环会出现什么情况?8.2插入排序直接插入排序算法性能分析最好情况下（正序）：12345时间复杂度为O(n)。比较次数：n-1移动次数：2(n-1)1234512345123451234523458.2插入排序直接插入排序算法性能分析最

8、好情况下（正序）：比较次数：n-1移动次数：2(n-1)最坏情况下（逆序或反序）：时间复杂度为O(n2)。54321453213452123451123454321比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(4(1-+=+ånnin2=i）（时间复杂度为O(n)。8.2插入排序平均情况下（随机排