binaryinsertsort.h

来自「有各种排序算法」· C头文件 代码 · 共 21 行

#include"DataList.h"
template <class T> 
void BinaryInsertSort (dataList<T>& L,  const int left, const int right) {
	//利用折半搜索, 在L.Vector[left]到L.Vector[i-1]中
	//查找L.Vector[i]应插入的位置, 再进行插入。
	Element<T> temp;  
	int i, low, high, middle, k;
	for (i = left+1; i <= right; i++) {
		temp = L[i];  low = left;  high = i-1;  //搜索范围初值
		while (low <= high) {	//折半搜索插入位置
			middle = (low+high)/2;	//取中点
			if (temp < L[middle])	  //插入值小于中点值
				high = middle-1;	  //向左缩小区间
			else low = middle+1;	  //否则, 向右缩小区间
		}                                        // while语句继续搜索 
		for (k = i-1; k >= low; k--) L[k+1] = L[k];
		//成块移动,空出插入位置
		L[low] = temp;	     //插入
	}
};