选择排序时间性能分析 对n个记录进行简单选择排序,所需进行的 关键字间的比较次数总计为: n(n 2 移动记录的次数,最小值为0,最大值为3(-1)
第 16 页 选择排序时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为: 移动记录的次数，最小值为 0, 最大值为3(n-1) 2 ( 1) ( ) 1 1 − − = − = n n n i n i
32简单排序方法 简单排序算法,除前面讨论的选择排序外,常用的还 有插入排序和起泡排序。 插入排序的基本思想: 每步将一个待排序的对象,按其关键码大小, 插入到前面已经排好序的一组对象的适当位置上,直 到对象全部插入为止。 简而言之,边插入边排序,保证子序列中随时都是排好序的
第 17 页 简单排序算法，除前面讨论的选择排序外，常用的还 有插入排序和起泡排序。 3.2 简单排序方法 插入排序的基本思想： 每步将一个待排序的对象，按其关键码大小， 插入到前面已经排好序的一组对象的适当位置上，直 到对象全部插入为止。 简而言之，边插入边排序，保证子序列中随时都是排好序的
直接插入排序 算法实现 当插入第i(i≥1)个对象时,前面的r0,r1 r[i-1已经排好序。这时,用r的排序码与ri-1,ri 2],…的排序码顺序进行比较,找到插入位置即将r插 入,原来位置上的对象向后顺移 利用“顺序查找”实现“在Ri-1查找R[的插入位置 二第8
第 18 页 利用 “顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置” 直接插入排序 算法实现： 当插入第i (i 1) 个对象时, 前面的r[0], r[1], …, r[i-1]已经排好序。这时, 用r[i]的排序码与r[i-1], r[i- 2], …的排序码顺序进行比较, 找到插入位置即将r[i]插 入, 原来位置上的对象向后顺移
趟直接插入排序的基本思想: 有序序列R-1无序序列R[i.nl R 有序序列R1.i无序序列Ri+1n
第 19 页 有序序列R[1..i-1] R[i] 无序序列 R[i..n] 有序序列R[1..i] 无序序列 R[i+1..n] 一趟直接插入排序的基本思想：
趟插入排序 【算法33】 void InsertPass( SqList &L, int i) ∥已知Lr[1.J-们中的记录已按关键字非递减的顺序有序排列,本算法实现 ∥将Lr[插入其中,并保持Lr[1.中记录按关键字非递减顺序有序 L.r[o]=L.r可 ∥复制为哨兵 for(j=i-1; L r[o]. key <Lr0. key;-j) Lr[+1]=Lr0 ∥记录后移 rT+们=L.r[o] ∥插入到正确位置 }∥ InsertPass 注意:“哨兵”的作用
第 20 页 【算法3.3 】 void InsertPass( SqList &L, int i ) { // 已知 L.r[1..i-1]中的记录已按关键字非递减的顺序有序排列，本算法实现 // 将L.r[i]插入其中，并保持L.r[1..i]中记录按关键字非递减顺序有序 L.r[0] = L.r[i]; // 复制为哨兵 for ( j=i-1; L.r[0].key < L.r[j].key; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; // 插入到正确位置 } // InsertPass 注意：“哨兵”的作用 一趟插入排序