10-1排序.ppt

关键问题⑴：如何由一个无序序列建成一个堆？ 28 25 16 32 18 36 16 32 16 28 25 18 36 25 32 16 28 18 36 25 28 32 36 28 16 18 25 10.4.3 堆排序(Heap Sort) 算法描述： for (i=n/2; i=1; i--) sift(r, i, n) ; 关键问题⑴：如何由一个无序序列建成一个堆？ 最后一个结点（叶子）的序号是n， 则最后一个分支结点即为结点n的双亲， 其序号是n/2。 10.4.3 堆排序(Heap Sort) 关键问题⑵：如何处理堆顶记录？ 32 36 28 16 18 25 36 28 32 25 18 16 1 2 3 4 5 6 对 应 交换 16 28 32 25 18 36 1 2 3 4 5 6 对 应 32 16 28 36 18 25 10.4.3 堆排序(Heap Sort) 算法描述： r[1]←→r[n-i+1]; 关键问题⑵：如何处理堆顶记录？ 解决方法： 第 i 次处理堆顶是将堆顶记录r[1]与序列中第n-i+1个记录r[n-i+1]交换。 堆排序 32 16 28 36 18 25 关键问题⑶：如何调整剩余记录，成为一个新堆？ 16 堆排序 ? 解决方法： 第 i 次调整剩余记录，此时，剩余记录有n-i个，调整根结点至第n-i个记录。 关键问题⑶：如何调整剩余记录，成为一个新堆？ 算法描述： sift(r, 1, n-i); 堆排序 初始序列：{49,38,65,97,76,13,27,49} 堆排序 49 38 65 13 27 76 97 49 初始堆 typedef SqList HeapType; void HeapAdjust(HeapType H, int s, int m){ rc = H.r[s]; for(j=2*s;j=m;j++){ //沿key较大的孩子结点向下筛选 if(jm LT(H.r[j].key, H.r[j+1].key)) j++; //j为key较大的记录的下标 if(!LT(rc.key, H.r[j].key)) break; //rc应插在位置s H.r[s] =rc; } void HeapSort(HeapType H){ for(i = H.length/2; i0; --i) //把H.[1..H.length]调成大顶堆 HeapAdjust(H,i,H.length); for(i=H.length;i1;--i){ H.r[1] H.r[i]; HeapAdjust(H,1,i-1); //把H.[1..i-1]调成大顶堆 }//for } 堆排序算法的性能分析 第1个for循环是初始建堆，需要O(n)时间； 第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第 i 次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间； 因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。 10.4.3 堆排序(Heap Sort) 05 98 12 69 38 53 81 起泡排序过程示例 05 98 12 69 38 53 81 05 98 12 69 38 53 81 05 98 12 69 38 53 81 10. 3 快速排序 第i趟起泡：r[1]~r[n-i+1] 如何确定起泡排序的范围？ 如何判别冒泡排序结束条件？ 设置标志flag 冒泡排序中有交换，flag=1 flag=0程序结束 10. 3 快速排序 起泡排序的时间性能分析 最好情况（正序）： 比较次数：n-1 移动次数：0 1 2 3 4 5 时间复杂度为O(n)。 1 2 3 4 5 10. 3 快速排序 最坏情况（反序）： 起泡排序的时间性能分析 最好情况（正序）： 比较次数：n-1 移动次数：0 5 4 3 2 1 时间复杂度为O(n)； 时间复杂度为O(n2)。 4 3 2 1 5 3 2 1 4 5 2 1 3 4 5 1 2 3 4 5 比较次数： 移动次数： 2 ) 1 ( 1 - = ? = n n (n-i) n-1 i 2 ) 1 ( 1 - = ? = n 3n 3(n-i) n-1 i 平均情况：时间复杂度为O(n2)。 10. 3 快速排序 快速排序：在冒泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单