数据结构第10章1.ppt

第10章 排序 2.希尔(shell)排序(又称缩小增量排序) 1.直接选择排序 10.4 交换排序 交换排序的基本思想是：利用交换数据元素的位 置进行排序的方法。 二路归并排序算法分析 10.6 基数排序 基数排序算法分析 作业 算法核心语句如下： while(i j temp.key = a[j].key) j--;//在数组的右端扫描 if(i j) { a[i] = a[j]; i++; } ? while(i j a[i].key temp.key) i++;//在数组的左端扫描 if(i j) { a[j] = a[i]; j--; } 60 55 48 37 10 90 84 36 36 55 48 37 10 90 84 90 90 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 90 84 36 55 48 37 10 84 36 55 48 37 10 60 84 i i i i i i i i j j j j j j j j i j 初始关键字序列: (1) (2) (3) (4) (5) (6) (7) (8) 快速排序算法一次快速排序过程 图中标有下划横线的数据元素为本次快速排序选取的标准元素。 快速排序算法各次快速排序过程 初始关键字序列: (1) (2) { 60 55 48 37 10 90 84 36 { 36 55 48 37 10} 60 { 90} { 10 } 36 { 37 55} 60 84 { } (3) { 10 } 36 { } 48 { } 60 84 90 最后结果 10 36 37 48 55 60 84 90 {37} 48 55 84 90 时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加 空间效率：O(log2n)—因为递归要用堆栈 稳 定 性： 不 稳 定 —因为有跳跃式交换。 算法分析： 10.5 归并排序 归并排序主要是二路归并排序,基本思想是：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 ?n / 2? 个长度为 2 的有序子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。 一次二路归并排序算法如下： void Merge(DataType a[], int n, DataType swap[], int k) //k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中 { int m = 0, u1,l2,i,j,u2; ? int l1 = 0; //第一个有序子数组下界为0 while(l1+k = n-1) { l2 = l1 + k; //计算第二个有序子数组下界 u1 = l2 - 1; //计算第一个有序子数组上界 u2 = (l2+k-1 = n-1)? l2+k-1: n-1; //计算第二个有序子数组上界 //两个有序子数组合并 for(i = l1, j = l2; i = u1 j = u2; m++) { if(a[i].key = a[j].key) { swap[m] = a[i]; i++; } else { swap[m]=a[j]; j++; } } //子数组2已归并完，将子数组1中剩余的元素存放到数组swap中 while(i = u1) { swap[m] = a[i]; m++; i++; } //子数组1已归并完，将子数组2中剩余的元素存放到数组swap中 while(j = u2)