选择排序void SelectSort (SqList &L) RcdType W ;for (i=l; i<L.length; ++i) j=i;for (k=i+1; k<=L.length;, k++ )if(L.r[k].key <L.r[i].key) j =k ;if (i!=i ) W-L.r[il;L.r[i] =L.r[il;L.r[i] = W;)1 // SelectSort6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 选择排序 void SelectSort (SqList &L) { RcdType W； for (i=1; i<L.length; ++i) { j = i； for ( k=i+1; k<=L.length; k++ ) if ( L.r[k].key < L.r[j].key ) j =k ； if ( i!=j ) { W=L.r[j];L.r[j] =L.r[i];L.r[i] = W;} } } // SelectSort
10.2.2插入排序voidInsertPass(Sqlist &L,int i)复杂度o(n)voidInsertSort(Sqlist&L)复杂度o(n2)数据的有序性影响算法最差比较移动（n+4）（n-1）/2一是稳定排序R[i]有序序列R[1..i-1]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1.n]中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 void InsertPass(Sqlist &L,int i)复杂度 O(n) void InsertSort(Sqlist &L) 复杂度 O(n2) –数据的有序性影响算法 最差比较移动 (n+4)(n-1)/2 –是稳定排序 R[i] 有序序列R[1.i-1] 无序序列R[i.n] 有序序列R[1.i] 无序序列R[i+1.n] 10.2.2插入排序
插入排序（一趟void InsertPass( SqList &L, int i) //复制为哨兵L.r[0] = L.r[i];for (j=i-1; L.r[O].key < L.r[i].key, --j )//记录后移L.r[i+1] = L.r[i];/插入到正确位置L.r[j+1] = L.r[O];?// InsertPass8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 插入排序(一趟) void InsertPass( SqList &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 ( SqList &L) /对顺序表L作插入排序for (i=2; i<=L.length; ++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];/插入到正确位置L.r[j+1]= L.r[0]; // if // InsertSort9ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 插入排序 void InsertSort ( SqList &L) { // 对顺序表L作插入排序 for ( i=2; i<=L.length; ++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
其他插入排序折半插入：插入时因为有序区可以使用折半查找，从而提高插入速度2路插入：一为了减少移动，分两个半区插入，可以和折半一起使用表插入：一通过静态链表形式存储数据元素，通过修改指针的方式避免元素的移动，不可以使用折半插入。10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 其他插入排序 折半插入： – 插入时因为有序区可以使用折半查找，从而提 高插入速度 2路插入： – 为了减少移动，分两个半区插入,可以和折半一起 使用 表插入： – 通过静态链表形式存储数据元素，通过修改指针 的方式避免元素的移动，不可以使用折半插入