插入排序--折半插入排序

一，实现方法一

public  void sort(int[] a)
	{
		int temp,low,mid,height,k;
		for(int i=1;i<a.length;i++)
		{
			low=0;
			height=i-1;
			mid=i;
			while(low<=height)
			{
				mid=(low+height)/2;
				if(a[i]>=a[mid])
					low=mid+1;
				else
					height=mid-1;
			}

			temp=a[i];
			for(k=i-1;k>=low;k--)
				a[k+1]=a[k];
			a[k+1]=temp;
		}
	}

二，实现方法二

public void sort(int[] a)
	{
		int temp;
		int low,height,mid;
		for(int i=1;i<a.length;i++)
		{
			low=0;
			height=i-1;
			mid=i;
			while(low<height)
			{
				mid=(low+height)/2;
				if(a[i]>a[mid])
					low=mid+1;
				else
					height=mid;
			}
			if(a[i]<=a[low])
			{
				temp=a[i];
				for(int k=i-1;k>=low;k--)
					a[k+1]=a[k];
				a[low]=temp;
			}
		}
	}

三，方法三

	public void  sort(int[] a)
	{
		int temp;
		int loc;
		int j;
		for(int i=1;i<a.length;i++)
		{
			loc=middle(a,0,i-1,a[i]);
			if(a[loc]>=a[i])
			{
				temp=a[i];
				for(j=i-1;j>=loc;j--)
					a[j+1]=a[j];
				a[j+1]=temp;
			}
		}
	}
	
	private int middle(int a[], int low, int height, int key)
	{
		int mid = (low+height)/2;
		if(a[mid]==key)
			return mid;
		if(a[mid]<key && low<height)
		{
			low=mid+1;
			return middle(a,low,height,key);
		}
		if(a[mid]>key && low<height)
		{
			height=mid;
			return middle(a,low,height,key);
		}
		return height;
	}

数据结构排序算法总结，C++版，参看地址http://www.cnblogs.com/mingcn/archive/2010/10/17/Sort.html#4