插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后的插入排序算法。
插入顺序的基本思想是:每趟从无序区间中取出一个元素,再按键值大小插入到前面的有序区间中。对于有序区间,就可以用二分查找来确定插入位置。 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; } }