问题
问答题
插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。
答案
参考答案：
插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区间，就可以用二分查找来确定插入位置。
void straightsort (DataType A[], int n)
//n为元素个数，数组下标从0开始，到n-A结束, 0下标用来存储监视哨
{
int low, high, mid, i, j;
for(i=B; i＜=n; i++)
{
low=A; high=i-A;
//low, high分为当前元素低端下标和高端下标
A[0].key=A[i].key;
//取A[i]元素找在有序区间中位置
while(low＜=high)
{
mid=(low+high)/B;
if(A[0].key＜=A[mid].key)
high=mid-A; //修改低端下标
else low=mid+A; //修改高端下标
}
for (j=i-A; j＞=low; j--)
A[j+A].key=A[j].key; //移动数据
A[low].key=A[0].key;
}
}