数据结构(c语言版)第9章排序

《数据结构(c语言版)第9章排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章内部排序排序：调整记录表中记录次序，使之按关键值有序(增序)。记录表结构：SeqList类内部排序记录集全部在内存中（战术问题）外部排序记录集部分在内存中，排序过程中，需访问外存（战略问题）稳定性：关键值相同的记录，排序前后的相对次序不变。排序前排序后5143413445稳定排序13445不稳定排序1插入排序思路：起源于数据陆续达到的思路，摸牌的行为。1.1直接插入1.1.1算法思路与步骤设已存在一个有序子序列；每趟将一个记录按关键值大小插入到有序子序列中。初始化时，有序子序列只有一个记录；n-1趟后，有序子序列有n个记录。初始21254925*816第1趟21254925*816第

2、2趟21254925*816第3趟212525*49816第4趟8212525*4916第5趟816212525*491.1.2算法实现//直接插入排序templatevoidSeqList::InsertSort(){intn=m_Data.size();for(inti=1;i=0&&m_Data[j]>tmp;j--)m_Data[j+1]=m_Data[j];//记录移1位m_Data[j+1]=tmp;}}1.1.3性能分析属于稳定排序。时间复杂度是O(n2)。KCN：关键值比较次数

3、RMN：记录移动次数比较移动最好情况记录集有序1次/趟=>KCN=n-12次/趟=>RMN=2(n-1)最坏情况记录集逆序i次/趟=>KCN=n(n-1)/2i+2次/趟=>RMN=(n+4)(n-1)/21.2希尔排序发明人：D.L.Shell，发明于1959年。1.2.1算法思路与步骤直接插入排序的缺点：每个记录被一步一步地挪到目标位置。将记录较快地挪到目标位置的方法：加大步长。仅仅加大步长的值，可行吗？缩小增量法：最后一次的步长一定为1。希尔排序：将记录序列按某个步长分成若干子序列；分别对各子序列排序。步长的取值方法之一：n/2,n/4,……,8,4,2,1。初始561748329第

4、1趟步长=4461258379第2趟步长=2123647589第3趟步长=11234567891.2.2算法实现templatevoidSeqList::ShellSort(){intn=m_Data.size();for(intstep=n/2;step>0;step=step/2){for(inti=step;i=0&&m_Data[j]>tmp;j=j-step)m_Data[j+step]=m_Data[j];//记录移step位m_Data[j+step]=tmp;}}}1.2

5、.3性能分析属于不稳定排序。(各子序列彼此独立的交换)时间复杂度：O(n1.5)…O(n1.3)。第9章内部排序3选择排序思路：“比较”比“赋值”速度快得多3.1直接选择排序3.1.1算法思路与步骤每趟：在剩余序列中找到最小值，将之交换到目标位置。n-1趟选出n-1个极值，置于相应目标位置。初始561748329第1趟165748329第2趟1257483693.1.2算法实现templatevoidSeqList::SelectSort(){intn=m_Data.size();for(inti=0;i

6、1;j

7、.2树排序3.2.1算法思路减少比较次数的方法：锦标赛的赛制。选出冠军的过程：（比较次数=n-1）选出亚军的方法：将冠军值改为∞。（比较次数=log2n）3.2.2性能分析时间复杂度：O(nlog2n)空间复杂度：O(n)3.3堆排序3.3.1堆的定义60年代Williams首先提出堆排序算法。有n个记录的序列,其关键值序列为(K0,K1,……Kn-1)若2i+1