数据结构(C语言版) 第9章 排序.doc

第9章 内部排序 排序：调整记录表中记录次序，使之按关键值有序(增序)。 记录表结构：SeqList类 内部排序 记录集全部在内存中（战术问题） 外部排序 记录集部分在内存中，排序过程中，需访问外存（战略问题） 稳定性：关键值相同的记录，排序前后的相对次序不变。 排序前 排序后 5 1 4 3 4 1 3 4 4 5 稳定排序 1 3 4 4 5 不稳定排序 1 插入排序 思路：起源于数据陆续达到的思路，摸牌的行为。 1.1 直接插入 1.1.1 算法思路与步骤 设已存在一个有序子序列；每趟将一个记录按关键值大小插入到有序子序列中。 初始化时，有序子序列只有一个记录； n-1趟后，有序子序列有n个记录。 初始 21 25 49 25* 8 16 第1趟 21 25 49 25* 8 16 第2趟 21 25 49 25* 8 16 第3趟 21 25 25* 49 8 16 第4趟 8 21 25 25* 49 16 第5趟 8 16 21 25 25* 49 1.1.2 算法实现 //直接插入排序 templateclass T void SeqListT::InsertSort() { int n=m_Data.size(); for(int i=1; in; i++) { T tmp=m_Data[i]; for(int j=i-1; j=0 m_Data[j]tmp; j--) m_Data[j+1]=m_Data[j]; //移位 m_Data[j+1]=tmp; } }O(n2)。 KCN：关键值比较次数 RMN：记录移动次数 比较移动有序1次趟KCN=n-1 2次趟RMN=2(n-1) 最坏 情况 记录集逆序次趟KCN=n(n-1)/2 i+2次趟RMN=(n+4)(n-1)/2 1.2 希尔排序 发明人D.L.Shell，发明于1959年 直接插入排序的缺点：每个记录被一步一步地挪到目标位置。 将记录较快地挪到目标位置的方法：加大步长。 仅仅加大步长的值，可行吗？ 缩小增量法：最后一次的步长一定为1。 希尔排序：将记录序列按某个步长分成若干子序列；分别对各子序列排序。 步长的取值方法之一：n/2,n/4,……,8,4,2,1。 初始 5 6 1 7 4 8 3 2 9 第1趟 步长=4 4 6 1 2 5 8 3 7 9 第2趟 步长=2 1 2 3 6 4 7 5 8 9 第3趟 步长=1 1 2 3 4 5 6 7 8 9 1.2.2 算法实现 templateclass T void SeqListT::ShellSort() { int n=m_Data.size(); for(int step=n/2; step0; step=step/2) { for(int i=step; in; i++) { T tmp=m_Data[i]; for(int j=i-step; j=0 m_Data[j]tmp; j=j-step) m_Data[j+step] = m_Data[j]; // 记录移step位 m_Data[j+step]=tmp; } } } 1.2.3性能分析 属于不稳定排序。(各子序列彼此独立的交换) 时间复杂度：O(n1.5)…O(n1.3) 。 第9章 内部排序 3 选择排序 思路：“比较”比“赋值”速度快得多 3.1 直接选择排序 3.1.1 算法思路与步骤 每趟：在剩余序列中找到最小值，将之交换到目标位置。 n-1趟选出n-1个极值，置于相应目标位置。 初始 5 6 1 7 4 8 3 2 9 第1趟 1 6 5 7 4 8 3 2 9 第2趟 1 2 5 7 4 8 3 6 9 3.1.2 算法实现 templateclass T void SeqListT::SelectSort() { int n=m_Data.size(); for(int i=0; in-1; i++) { int min_i=i; for(int j=i+1; jn; j++) if(m_Data[j]m_Data[min_i]) min_i=j; if(i!=min_i) { T tmp=m_Data[i]; m_Data[i]=m_Data[min_i]; m_Data[min_i]=tmp; } } } 3.1.3 性能分析 时间复杂度：O(n) 空间复杂度：O( 一趟后 1 4 5 3 3