时间效率：0125)~0(1.6125)—由经验公式得到 空间效率：0(1)— 因为仅占用1个缓冲单元（与算法有关） 算法的稳定性：不稳定— 因为49排序后却到了49的前面 希尔排序算法（主程序） 参见教材P272 void ShellSort(SqList &L,int dlta[,int t) /按增量序列dlta0.t-1对顺序表L作Shel排序 for(k=0 k<t ++k) dk值依次装在dta[t]中 ShellSort(L,dlta[k]); /增量为dtak的一趟插入排序 //ShellSort
6 void ShellSort(SqList &L，int dlta[ ]，int t){ //按增量序列dlta[0.t-1]对顺序表L作Shell排序 for(k=0；k<t；++k) ShellSort(L，dlta[k])； } // ShellSort 时间效率： 空间效率：O（1）——因为仅占用1个缓冲单元(与算法有关） 算法的稳定性：不稳定——因为49*排序后却到了49的前面 希尔排序算法（主程序） 参见教材P272 O(n 1.25）～O（1.6n 1.25）——由经验公式得到 dk值依次装在dlta[t]中 //增量为dlta[k]的一趟插入排序
希尔排序算法（其中某一趟的排序操作） void ShellInsert(SqList &L,int dk){ 参见教材P272 /对顺序表L进行一趟增量为dk的Shel排序，dk为步长因子 for(i=dk+1 i<=L.length ;++i) if(r[il.key r[i-dk].key) /开始将r]插入有序增量子表 r[O]=r[i] /暂存在r01,此处r01仍是哨兵 for(j=i-dk;j>0&&(r[0].key<r[jl.key);j-=dk)r[j+dk]=r[j] /关键字较大的记录在子表中不断后移 r[j+dk]=r[0] /在本趟结束时将插入到正确位置 //if 理解难点：整理动作是二合一的，r0] //ShellInsert 仍是每个dk子集的哨兵，用于子集的彻 底排序」
7 理解难点：整理动作是二合一的， r[0] 仍是每个dk子集的哨兵，用于子集的彻 底排序！ for(i=dk+1；i<=L.length； ++ i) if(r[i].key < r[i-dk].key) { r[0]=r[i]； for(j=i-dk; j>0&&(r[0].key<r[j].key); j-=dk) r[j+dk]=r[j]； r[j+dk]=r[0]； }//if } //ShellInsert void ShellInsert(SqList &L，int dk) { 希尔排序算法（其中某一趟的排序操作） 参见教材P272 //对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子 //开始将r[i] 插入有序增量子表 //暂存在r[0] ，此处r[0]仍是哨兵 //关键字较大的记录在子表中不断后移 //在本趟结束时将r[i]插入到正确位置
对前页程序中间for循环的理解： 空间效率与算法设计有关 for(i=dk+1 i<=L.length ++i) if(r[i].key r[i-dk].key) 大者后移 r[O]=r[i] for(j=i-dk;j>0&&(r[0].key<r[jl.key);j-=dk)r[j+dk]=r[jl r[j+dk]=r[0] 如果没有此句，就只能实现相临的两个数之间的比较，而不 能两两都比较到，所以有可能达不到排序的目的。 例如当dk=5时，第一趟比较之前的原始子集是： 5 7 4 i=1 i+dk=6 i+2dk=11 如果不用for循环，比较的结果是5,4,7 只有执行fo循环后，比较结果才会是4,5,7
8 对前页程序中间for循环的理解： 如果没有此句，就只能实现相临的两个数之间的比较，而不 能两两都比较到，所以有可能达不到排序的目的。 例如当dk=5时，第一趟比较之前的原始子集是： for(j=i-dk; j>0&&(r[0].key<r[j].key); j-=dk) r[j+dk]=r[j]； r[j+dk]=r[0]；} 5 7 4 i=1 i+dk=6 i+2dk=11 如果不用for循环，比较的结果是 5，4，7 只有执行for循环后，比较结果才会是 4，5，7 for(i=dk+1；i<=L.length； ++ i) if(r[i].key < r[i-dk].key) { r[0]=r[i]； 大者后移 空间效率与算法设计有关
10.3交换排序 交换排序的基本思想是： 两两比较待排序记录的关键码，如果发生逆序 (即排列顺序与排序后的次序正好相反)，则交换之， 直到所有记录都排好序为止。 交换排序的主要算法有： 1)冒泡排序 2)快速排序 区
9 10.3 交换排序 两两比较待排序记录的关键码，如果发生逆序 （即排列顺序与排序后的次序正好相反），则交换之， 直到所有记录都排好序为止。 交换排序的主要算法有： 1) 冒泡排序 2) 快速排序 交换排序的基本思想是：
1)冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大” (或“前大后小”)规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列T=(21,25,49,25*,16,08),请写出 冒泡排序的具体实现过程。 初态：21,25,49,25*，16， 08 第1趟21,25,25*，16,08,49 第2趟21,25,16,08,25*，49 第3趟21,16,08,25,25*，49 第4趟16,08,21， 25, 25*,49 第5趟08,16,21,25， 25*,49 区 10
10 1) 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大” （或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列 T=(21，25，49，25* ，16，08），请写出 冒泡排序的具体实现过程。 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 初态： 第1趟 第2趟 第3趟 第4趟 第5趟