第9章 排序案例.ppt

练习： 1. 欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母升序重排，则初始步长为4的希尔排序一趟的结果是？ 答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后： 二路归并排序算法分析： 练习：若初始记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请解释理由（排序方法各列举两种即可）。 P, Q, R, A, D, H, C, F, M, S, X , Y 2. 以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行希尔排序（取d=5,3,1）算法的各趟排序结束时，关键字序列的状态。 解：原始序列: 256，301，751，129，937，863，742，694，076，438 第1趟 d=5 第2趟 d=3 第3趟 d=1 256，301，694，076，438，863，742，751，129，937 076，301，129，256，438，694，742，751，863，937 076，129，256，301，438，694，742，751，863，937 10.3 快 速 排 序 一、起泡排序 二、一趟快速排序 三、快速排序 四、快速排序的时间分析 一、起泡排序 　　假设在排序过程中，记录序列R[1..n]的状态为： 第 i 趟起泡排序 无序序列R[1..n-i+1] 有序序列 R[n-i+2..n] n-i+1 无序序列R[1..n-i] 有序序列 R[n-i+1..n] 比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上 例：关键字序列 T=(21，25，49，25*，16，08），请按从小到大的顺序，写出冒泡排序的具体实现过程。 初态： 第1趟 第2趟 第3趟 第4趟 第5趟 21，25，49， 25*，16， 08 21，25，25*，16， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49 void BubbleSort(Elem R[ ], int n) { while (i 1) { } // while } // BubbleSort i = n; i = lastExchangeIndex; // 本趟进行过交换的 // 最后一个记录的位置 if (R[j+1].key R[j].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } //if for (j = 1; j i; j++) lastExchangeIndex = 1; 注意: 2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。 例如: 2 5 5 3 1 5 7 9 8 9 i=7 i=6 for (j = 1; j i; j++) if (R[j+1].key R[j].key) … 1 3 i=2 1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。 时间分析: 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡 “比较”的次数： 0 “移动”的次数： “移动”的次数： n-1 二、一趟快速排序（一次划分） 　目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[j].key (s≤j≤i-1) 枢轴 (i+1≤j≤t)。 s t low high 设 R[s]=52 为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字 high 23 low 80 high