文档介绍：数据结构之树和图算法
第1页，本讲稿共70页
假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；
若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的。
若在排序后的序列中 Rj 仍领先于 Ri ，则入排序
第10页，本讲稿共70页
算法:
void BinaryInsertSort(ElemType R[],int n)
{ for(int i=1; i<n; i++) //共进行n-1次插入
{ int left=0,right=i-1;ElemType temp=R[i];
while(left<=right)
{ int middle=(left+right)/2; //取中点
if(temp<R[middle]) right=middle-1;
//取左区间
else
left=middle+1;
} //取右区间
for(int j=i-1;j>=left;j--)
R[j+1]=R[j]; //元素后移空出插入位
R[left]=temp;
}
}
第11页，本讲稿共70页
折半插入效率分析
二分插入算法与直接插入算法相比，
需要辅助空间与直接插入排序基本一致；
时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，
两种方法的元素的移动次数相同，
因此二分插入排序的时间复杂度仍为O(n2)。
二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。
第12页，本讲稿共70页
分析直接插入排序
1. 若待排序记录序列按关键字基本有序，则排序效率可大大提高；
2. 待排序记录总数越少，排序效率越高；
希尔(shell)排序
第13页，本讲稿共70页
思想:
先将待排序记录序列分割成为若干子序列分别进行直接插入排序；
待整个序列中的记录基本有序后，再全体进行一次直接插入排序。
例，序列 49 38 65 97 76 13 27 48 55 4 19
第一趟排序
49 13 19
38 27
65 48
97 55
76 4
13 19 49
27 38
48 65
55 97
4 76
第14页，本讲稿共70页
第二趟排序
13 19 49
27 38
48 65
55 97
4 76
13 55 38 76
27 4 65 49
48 19 97
13 38 55 76
4 27 49