插入排序（一趟） void InsertPass(SqTable &L,int i){ L.r0]=L.r[, 川复制为哨兵 for (j=i-1;L.r[0].key L.r[j].key;--j) L.r[j+1]=L.r[jl; ∥记录后移 L.rj+1]=L.[0] ∥插入到正确位置 }/∥InsertPass ypb@ustc.edu.cn 11 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 插入排序(一趟) void InsertPass(SqTable &L, int 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
插入排序 void InsertSort(SqTable &L){ ∥对顺序表L作插入排序 for i=2;i<=L.len;++i) if (L.r[i].key <L.r[i-1].key ) L.r[0]=L.r[; 川复制为哨兵 for (j=i-1;L.r[0].key L.r[j].key;-j) L.r[j+1]=L.r[j]; ∥记录后移 InsertPass L.r[jt1]=L.r[0]; ∥插入到正确位置 }∥if }/∥InsertSort ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 插入排序 void InsertSort (SqTable &L) { // 对顺序表L作插入排序 for ( i=2; i<=L.len; ++i ) if ( L.r[i].key < L.r[i-1].key ){ 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]; // 插入到正确位置 } // if } // InsertSort InsertPass
8.3希尔排序 ·又称“缩小增量排序” 初始： 49386597761327495504 38 )7 65 9 9> 76 04 -趟排序：13274955044938659776 04 5 4型 49 97 55 38 76 二趟排序：13044938274955659776 三趟排序：04132738494955657697 ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 8.3希尔排序 • 又称“缩小增量排序” 初始： 49 38 65 97 76 13 27 49 55 04 49 13 └────────────┘ 38 27 └───────────┘ 65 49 └───────────┘ 97 55 └───────────┘ 76 04 └───────────┘ 一趟排序: 13 27 49 55 04 49 38 65 97 76 └──────┴──────┴──────┘ 27 04 65 └──────┴──────┘ 49 49 97 └──────┴──────┘ 55 38 76 └──────┴──────┘ 二趟排序： 13 04 49 38 27 49 55 65 97 76 三趟排序： 04 13 27 38 49 49 55 65 76 97