浙江大学：《数据结构与算法》第十章 内部排序

102插入排序 1021直接插入排序 例:序列为{49,38,65,97,76,13,27,49 (49),38,65,97,76,13,27,49} 0(38){(38,49),65,97,76,13,27,49} 日(65){(38,49,65),97,76,13,27,49 (97){(38,49,65,97),76,13,27,49} (76){(38,49,65,76,97),13,27,49} (13){(13,38,49,65,76,97),27,49} 口(27){(13,27,38,49,65,76,97),49 (49){(13,27,38,49,49,65,76,97)}

10.2 插入排序 10.2.1 直接插入排序 例：序列为{49，38，65，97，76，13，27，49} {(49)，38，65，97，76，13，27，49} (38) {(38，49)，65，97，76，13，27，49} (65) {(38，49，65)，97，76，13，27，49} (97) {(38，49，65，97)，76，13，27，49} (76) {(38，49，65，76，97)，13，27，49} (13) {(13，38，49，65，76，97)，27，49} (27) {(13，27，38，49，65，76，97)，49} (49) {(13，27，38，49，49，65，76，97)}

直接插入排序算法 void InsertSort(sqlist &l) i for(i-2, K<=L length; ++i) if(T(L ri].key, L r[i-1. key)) Lr[0]=L.r[i]; ∥复制为哨兵 for(Fi-1; LT(L r[O).key, Lri]. key);--j L r[j+1-Lrll; ∥记录后移 Lr[+1]=L.r[o] ))// InsertSort 时间:最坏情形判断与移动各接近n(n+1)2 最好情形判断n次,无移动;故时间复杂度:O(n2) 间:一个辅助空间

直接插入排序算法 void InsertSort(SqList &L) { for(i=2; i<=L.length; ++i) if ( LT(L.r[i].key, L.r[i-1].key) ){ L.r[0] = L.r[i]; // 复制为哨兵 for(j=i-1; LT(L.r[0].key, L.r[j].key); --j) L.r[j+1] = L.r[j]; // 记录后移 L.r[j+1] = L.r[0]; }} // InsertSort 时间：最坏情形判断与移动各接近 n(n+1)/2; 最好情形判断n次，无移动；故时间复杂度：O(n2 ) 空间：一个辅助空间

1022She11排序算法 口基木思想: 口先将整个待排序记录序列分割成若干 子序列分别进行直接插入排序,待整个 序列“基本有序”时,再对全体记录进 次直接插入排序 口算法复杂度:0(n32

10.2.2 Shell排序算法 基本思想： 先将整个待排序记录序列分割成若干 子序列分别进行直接插入排序，待整个 序列“基本有序”时，再对全体记录进 行一次直接插入排序。 算法复杂度：O(n3/2)

She11排序举例(非稳定的) 例 {49,38,65,97,76,13,27,49,55,04} 增量取5:49 13 38 65 49 97 55 76 04 趟结果{13,27,49,55,04,49,38,65,97,76} 增量取3:13 55 38 76 27 04 65 49 49 97 二趟结果{13,04,49,38,27,49,55,65,97,76} 增量取1:13,04,49,38,27,49,55,65,97,76 三趟结果{04,13,27,38,49,49,55,65,76,97

Shell排序举例（非稳定的） 二趟结果{13，04，49，38，27，49，55，65，97，76} 增量取1：13，04，49，38，27，49，55，65，97，76 三趟结果{04，13，27，38，49，49，55，65，76，97} 一趟结果{13，27，49，55，04，49，38，65，97，76} 增量取3：13 55 38 76 27 04 65 49 49 97 例： {49，38，65，97，76，13，27，49，55，04} 增量取5： 49 13 38 27 65 49 97 55 76 04

103交换排序 1冒泡排序(其时间复杂度0(n2)) 例 49383838381313 38494949132727 65656513273838 977613274949 7613274949 13274965 274976 4997 初第第第第第第 始 关递趟超 排排 键序序序序 字后后后

10.3 交换排序 1. 冒泡排序（其时间复杂度O(n2)） 初 始 关 键 字 第 一 趟 排 序 后 第 二 趟 排 序 后 第 三 趟 排 序 后 第 四 趟 排 序 后 第 五 趟 排 序 后 第 六 趟 排 序 后 例： 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 97