数据结构 第09章 内排序--缩减.ppt

9.1 基本概念 Selection Sort: How Many Comparisons? 　时间复杂度 含 n 个元素的比较次数： 　　Sum = (n-1) + (n-2) + . . . + 2 + 1 = O( n2 ) 怎样建堆？ 例：对刚才建好的大根堆进行排序： 9.7 各种内部排序方法的比较 08 16 21 25* 25 49 交换 1号与3 号记录 21 16 08 25* 25 49 从 1 号到 3号 重新 调整为大根堆 21 16 25* 08 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 2.堆排序 08 16 21 25* 25 49 交换 1 号与2 号记录 16 08 21 25* 25 49 从 1 号到 2 号 重新 调整为大根堆 16 08 25* 21 25 49 1 2 3 4 5 6 08 16 25* 25 21 49 1 3 6 5 4 2 2.堆排序 void adjustheap(datatype a[ ],int n,int i) { datatype temp=a[i]; //令temp暂存待排序记录a[i] int j; j=2*i; //令j为a[i]的左孩子结点的下标 while(j=n) { if(jna[j].keya[j+1].key) //如果右孩子的关键字大于左孩子的关键字 j++; //就令j++；使j成为关键字较大的那个孩子结点的下标 if(temp.keya[j].key) //若a[i]大于其关键字较大的孩子结点的下标 { a[i].key=a[j].key;//并用关键字较大的孩子结点取代a[i] 堆排序算法 i=j;j=2*i; } else break; } a[i].key=temp.key; //调整完后，把暂存在temp中的原a[i]的值放入恰当的位置 } 堆排序算法 e.g: 将序列 49、38、65、97、76、13、27、49 用冒泡排序的方法进行排序。 0 1 2 3 4 5 6 7 8 49 49 38 38 65 65 97 97 76 76 13 13 27 27 49 49 1. 冒泡排序 9.4 交 换 排 序 0 1 2 3 4 5 6 7 8 38 49 65 76 13 27 49 97 13 27 38 49 49 65 76 97 97 76 65 49 49 38 27 13 正序时时间复杂度： O(n)， 逆序时时间复杂度： O(n2), 平均时间复杂性 O(n2)。 9.4 交 换 排 序 冒泡排序时间复杂性: 0 1 2 3 4 5 6 7 8 49 38 38 65 65 97 97 76 76 13 13 27 27 49 49 j 49 界点 e.g: 将序列 49、38、65、97、76、13、27、49 用快速排序的方法进行排序。 2. 快速排序 49 i void quicksort(datatype R[ ],int first,int end ) {//采用快速排序方法对数组R中R[first]~R[end]区间进行排序 //开始进行递归调用时first和end的初值分别为1和n int i,j; datatype temp; i=first; j=end; temp=R[i];//给first和end赋初值，temp中存放基准记录 算法描述： 2. 快速排序 while(ij) { while(ijtemp.key=R[j].key) j--;//从后往前顺序查找一