插入排序（一趟void InsertPass(SqTable &L, int i) /复制为哨兵L.r[0] = L.r[i];for (j=i-1; L.r[O].key < L.r[ij].key; --j )//记录后移L.r[i+1] = L.r[i];/插入到正确位置L.r[j+1] = L.r[O];?// InsertPass11中国科学技术大学ypb@ustc.edu.cn
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[O] = L.r[i];for (j=i-1; L.r[O].key< L.r[i].key; --j)//记录后移L.r[j+1] = L.r[i];InsertPass/插入到正确位置L.r[j+1]= L.r[0]; // if // InsertSort12ypb@ustc.edu.cn中国科学技术大学
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希尔排序“缩小增量排序·又称初始：4938659776132749550449133738496597557004一趟排序：49381327 4955046597.766594274997423876554955二趟排序：13044938276597 76三趟排序：0413273849556576.974913中国科学技术大学ypb@ustc.edu.cn
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