9内部排序.pptVIP

9 内部排序 （1）构造堆的方法 按堆的定义将r[1]..r[n]调整为堆。 （２）调整方法（筛选法） 　　　--左右孩子比较 　　　--父子比较 四、各种内部排序方法的比较　 排序方法 　平均时间 最坏情况 辅助存储空间 稳定性 直接插入排序 O(n2) O(n2) O(1) Y 冒泡排序 O(n2) O(n2) O(1) Y 简单选择排序 O(n2) O(n2) O(1) N 快速排序 O(nlog2n) O(n2) O(log2n) N 堆排序 O(nlog2n) O(nlog2n) O(1) N 归并排序 O(nlog2n) O(nlog2n) O(n) Y 基数排序 O(n) O(n) O(rd) Y   * * 各排序方法的排序思想 选择排序、冒泡排序、直接插入排序算法 快速排序Partition算法设计及排序过程 Ｓhell排序、归并排序、基数排序的排序过程 堆的判断及构造过程 一、 什么是排序 将一组任意顺序的数据，重新排列成按关键字有序的序列。 二、各种排序方法的策略 1、插入排序：在有序序列中插入一个新记录，使这个有序表 　　　　　　 仍保持有序。 2、交换排序：对待排序的两个数据进行比较，将较小数换到 前面，将较大数换到后面。 3、选择排序：在待排序的序列中，选择最小值。 4、归并排序：将两个有序表归并为一个新的有序表。 5、基数排序：从低位开始，按位进行排序。 例9.1 对{ 278, 109, 63, 930, 589, 184, 505, 269, 8, 83 } 用基数排序方法进行排序。 初始状态： 278, 109, 063, 930, 589, 184, 505, 269, 008, 083 第一趟排序后（个位有序）： 930, 063, 083, 184, 505, 278, 008, 109, 589, 269 第二趟排序后（在个位有序的基础上使拾位有序）： 505, 008, 109, 930, 063, 269 , 278, 083, 184, 589 第三趟排序后（在拾位有序的基础上使百位有序）： 008, 063, 083, 109, 184, 269, 278, 505, 589, 930 三、执行排序过程 Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 队列 278 008 109 589 269 063 083 930 184 505 从队列 0 到队列 9 进行收集，得： 930, 063, 083, 184, 505, 278, 008, 109, 589, 269 考察{278, 109, 063, 930, 589, 184, 505, 269, 008, 083}个位 放入相应的队列中（如：２７８,　入队列８） * 例9-2 对 { 49,38,65,97,76,13,27,38,49,04 }进行 Shell排序。 d=5 d=3 d=1 * 例9.3 写出{49,38,65,97,76,13,27,49}进行一趟快速 排序的过程和结果。 一趟快速排序的结果：27，38，13，49，76，97 ，65，49 * 例9.4 对{27，88，57，09，23，41，65，19}进行 归并排序。 　　　　 27，88，09，57，23，41，19，65 27，88，09, 57，23，41，19, 65 09, 27，57, 88，19, 23，41，65 09, 19, 23, 27，41