Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 12 6 10 24 36 21 SORT
21 物料管理 SORT Algorithms and DataStructures:Sorting 21 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 3 4 5 12 24 36 i 6 10 12
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。 0 1 2 3 4 5 36 24 10 6 12 12 6 10 12 24 36 22 SORT
22 物料管理 SORT Algorithms and DataStructures:Sorting 22 2、插入排序 e.g: 36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直接插入法将 其排序。结果仍保存在下标为 1 至 5 的元素之中。 1、直接插入排序 0 1 2 36 24 10 6 3 4 5 12 24 36 i 6 10 12 12
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 0 1 2 3 4 5 10 20 30 40 50 50 40 30 20 10 0(n2) 分析：移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 1=n-1 92 移动次数0 逆序时：比较次数 =a+20n-12 2 移动次数 ,t1)=+40n-12 后 23 SORT
23 物料管理 SORT Algorithms and DataStructures:Sorting 23 2、插入排序 1、直接插入排序 0 1 2 10 20 30 40 3 4 5 50 40 20 10 50 30 分析: 移动、比较次数可作为衡量时间复杂性的标准 正序时：比较次数 ∑ 1 = n-1 i=2 移动次数 0 n 逆序时：比较次数 ∑ i = (n+2)(n-1)/2 i=2 移动次数 ∑ (i+1) = (n+4)(n-1)/2 i=2 n n O(n2 )
Algorithms and DataStructures:Sorting 2、插入排序 1、直接插入排序 0 2 3 5 36 24 10 6 12 6 10 24 36 12 12 6 10 12 24 36 程序实现： Status InsertSort(SqList &L) for(i=2:i<=L.length ++i) if (LT(L.rfi].key,L.rfi-1].key ) L.rfo].key L.r[i].key; for j=i-1;LT(L.r[o].key,L.r[i].key);-j) L.t1小=L.l L.i+1]=L.0j } }//InsertSort 24 SORT
24 物料管理 SORT Algorithms and DataStructures:Sorting 24 2、插入排序 1、直接插入排序 0 1 2 36 24 10 6 3 4 5 12 6 10 24 36 12 12 Status InsertSort ( SqList &L ) { for ( i = 2; i <= L.length ; ++i ) if ( LT( L.r[i].key, L.r[i-1].key ) ) { L.r[0].key = L.r[i].key; for ( j=i-1; LT( L.r[0].key, L.r[j].key ) ; - -j ) L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; } } //InsertSort 程序实现: 6 10 24 36 12 i
Algorithms and DataStructures:Sorting 2、插入排序 2、折半插入排序 方法：在已排序的序列中查找下一 36 24 10 6 12 元素的插入位置，将该元素插入进 ↓hgh 去，形成更长的排序序列。如：12 low 的插入位置为下标3。 12 6 10 24 36 12 减少了比较次数，未降低时 间复杂性。 程序实现： Status BInsertSort(SqList &L) for(i=2;i<=L.length ++i) L.rfo]=L.rli];low =1 high =i-1; while low <high {m=low high )/2 if (LT(L.r[o].key,L.r[m].key))high=m-1 else low =m+1; for j=i-1;j>=high+1;-j)L.rj+1]=L.r]; L.r[high+1]=L.r[o]: }∥BInsertSort SORT
25 物料管理 SORT Algorithms and DataStructures:Sorting 25 2、插入排序 2、折半插入排序 Status BInsertSort ( SqList &L ) { for ( i = 2; i <= L.length ; ++i ) { L.r[0] = L.r[i]; low = 1 ; high = i-1 ; while ( low <= high ) { m = ( low + high ) / 2 ; if ( LT( L.r[0].key , L.r[m]. key ) ) high = m -1 ; else low = m + 1; } for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j]; L.r[high+1] = L.r[0]; } } // BInsertSort 程序实现: 36 24 10 6 12 24 36 12 high 6 10 12 12 方法：在已排序的序列中查找下一 元素的插入位置，将该元素插入进 去，形成更长的排序序列。如：12 的插入位置为下标3。 减少了比较次数，未降低时 间复杂性。 i low