各种排序算法的实现-2(折半插入排序）

这种算法 比起 直接插入算法的好处是 减少了比较次数，因为你当前插入的前面的列表中肯定是有序的，那么可以通过折半查找来 得来 你应该插入的位置，再把元素集体完后面挪动。

比如 当前列表是 1， 3 ， 9 ，7, 123.当你遍历到7的时候 前面的1,3， 9 实际上已经有序，那么根据折半查找算法可以很容易找到我们应该插入的位置是 9的前面，那么只需要把9 往后面挪动一位，再把7 放到9的位置即可。

这是我自己写的测试例子。 工作了这么多年了， 现在在家没事温习一下以前的排序，大家可以给出更优的解决办法，或者参与群 C语言/C++/STL/linux/MFC/WTL 77278127 去探讨。

下一篇继续介绍排序算法。

template
  
   
int get_pos(int start_pos, int end_pos, T * src, T value)
{
	if (start_pos == end_pos - 1)
	{
		if (value >= *(src + start_pos))
		{
			return end_pos;
		}
		else
		{
			return start_pos;
		}
	}
	else if (value < *(src + ((start_pos + end_pos) / 2)))
	{
		get_pos(start_pos, (start_pos + end_pos) / 2, src, value);
	}
	else if (value > *(src + ((start_pos + end_pos) / 2)))
	{
		get_pos((start_pos + end_pos) / 2, end_pos, src, value);
	}
	else if (value == *(src + ((start_pos + end_pos) / 2)))
	{
		return ((start_pos + end_pos) / 2);
	}
}

template 
   
     void sort(T *temp, int len) { for (int i = 1; i < len; i++) { if (*(temp + i) > *(temp + i - 1)) { continue; } else { int pos = get_pos(0, i, temp, *(temp + i)); T t = (*(temp + i) ); memcpy(temp + pos + 1, temp + pos, sizeof(T) * (i - pos)); *(temp + pos) = t; } } } int main(int argc, char* argv[]) { int src[10] = {1000, 3456, 200, 134, 2342342, 40, 80, -1, 0, 21 }; sort(src, 10); for (int i = 0; i < 10; i++) { printf("%d ", src[i]); } system("pause"); return 0; }