插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序算法。
【正确答案】：插入顺序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区间，就可以用二分查找来确定插入位置。 viod straightsort(DataType A[]，int n) ／／n为元素个数，数组下标从0开始，到n一1结束，0下标用来存储监视哨 { int low，high，mid，1，j； for(i=2；i<=n；i++) { low=1；high=i一1； ／／low，high分为当前元素低端下标和高端下标 A [0]．key=A E i]．key； ／／a AEi]TL素找在有序区间中位置 while(10w<一high) { mid=(10w+high)／2； if(A[0]．key<=A[mid]．key)high=mid-1； ／／修改低端下标 else low=mid+1； ／／修改高端下标 } for(j=i-1；j>=low；j一一)A[j+1]．key=A[j]．key； ／／移动数据 A[low]．key=A[0]．key； } }
