4归类 通过“归芹两个或两个以上的记录有序 子序列,逐步增加记录的有序序列的长度。 5.真他方法 112插入排序 入排序的基本思想:每次将一个待排序的 记录,按其关键字大小插入到前面已经排好序的 海有序表中,直到全部记录插入完成为止 6
6 4.归并类 通过“归并”两个或两个以上的记录有序 子序列，逐步增加记录的有序序列的长度。 5.其他方法 11.2 插入排序 插入排序的基本思想：每次将一个待排序的 记录，按其关键字大小插入到前面已经排好序的 有序表中，直到全部记录插入完成为止
11.2.1直入排房 一趟直插入排序的基本思想: 有序序列R01无序序列Rin1l Ri 有序序列R[无序序列R+n1 实现“一趟入排房”可分三步进行: 在R|0.1中查找R[的插入位置 R[0.]≤R[<R[i+1.i-1 2将Rj+1i-1中的所有记录均后移一个位置; 73将复制到R+的位置上
7 11.2.1 直接插入排序 • 一趟直接插入排序的基本思想： 有序序列R[0..i-1] 无序序列R[i,..n-1] R[i] 有序序列R[0..i] 无序序列R[i+1,..n-1] • 实现“一趟插入排序”可分三步进行： 1. 在R[0..i-1]中查找R[i]的插入位置; R[0..j] ≤R[i] <R[j+1..i-1] 2. 将R[j+1..i-1]中的所有记录均后移一个位置; 3. 将R[i]复制到R[j+1]的位置上
11.2.1直入排房 利用顺序查实现“在R.i-1中查找R[的插入位置 void Insertsort(RecType ri,int n) i int i, j; RecType temp; for(i=l;<n;i++)∥进行n-1趟排序 temp=ri; j=i-1 while (i>=0 & temp. key<riil. key {Ri+l|=Rljl;记录后移 Ri计+1}=temp;/插入到正确位置
8 11.2.1 直接插入排序 利用顺序查找实现“在R[0..i-1]中查找R[i]的插入位置” void InsertSort(RecType R[],int n) { int i, j; RecType temp; for (i=1;i<n;i++) //进行n-1趟排序 {temp=R[i]; j=i-1; while (j>=0 && temp.key<R[j].key) { R[j+1]=R[j]; //记录后移 j--; } R[j+1]=temp; //插入到正确位置 } }
void InsertSort(Rec Type RIl,int n) i int i, j; Rec Type temp; for(i=l;i<n;i++)∥进行n-1趟排序 temp=ri]; j=i-1; while (j>=0&& temp. key<rii- key) iRI+l=rll; j-;) RIj+l=temp; j temp 0123456 49386597761327 i=13838496597761327 i=265(3849)6597761327 i=397(384965)97761327 =476(38496576971327 i=513(133849657697)27 9 =627(13273849657697)
9 void InsertSort(RecType R[],int n) { int i, j; RecType temp; for (i=1;i<n;i++) //进行n-1趟排序 {temp=R[i]; j=i-1; while (j>=0 && temp.key<R[j].key) { R[j+1]=R[j]; j--; } R[j+1]=temp; } } 49 38 65 97 76 13 27 i=1 (49) 38 38 65 97 76 13 27 49 temp 38 j j 0 1 2 3 4 5 6 i=3 (38 49 65） 97 76 13 27 i=2 (38 49） 65 97 76 13 27 i=4 (38 49 65 97） 76 13 27 i=5 13 (13 38 49 65 76 97) 27 i=6 27 (13 27 38 49 65 76 97) 76 76 97 65 97
·算法评价 ◇时间复杂度 若待排序记录按关键字从小到大排列正序) 关键字比较次数:∑ 记录移动次数:2(n-1) 着待排序记录按关键字从大到小排列逆序) 关键字比较次数: l 2 通记录移动次数:∑(+2=10+1= i=1 若待排序记录是随机的,取平均值 T(n)=O(n2) ◇空间复杂度:S(m)=O() 10
10 • 算法评价 ❖时间复杂度 »若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 1 1 1 1 = − − = n n i 记录移动次数：2（n-1） 若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 2 ( 1) 1 1 − = − = n n i n i 记录移动次数： »若待排序记录是随机的，取平均值 T(n)=O(n²) ❖空间复杂度：S(n)=O(1) 2 ( 4)( 1) ( 2) 1 1 + − + = − = n n i n i