排序算法--折半插入排序（二分查找排序）

 

折半插入排序其实就是直接插入排序的一种改进，引入了二分查找算法，这样关键字的比较次数就会减少，

数量级为O(nlog^2n)，但是元素移动次数还是O(n^2)，所以折半插入排序的时间复杂度是O(n^2)。

另外，折半插入排序是稳定的排序算法；

下面是用JAVA写的算法的两种实现方式。不过原理都是一样的

第一种：

 package sort;

import java.util.Arrays;

public class BinarySearch1 {
	public static void main(String args[])
	{
		int array[]={49,38,65,97,76,13,27};
		binarySort(array,array.length);
		System.out.println(Arrays.toString(array));
	}
	
	//二分查找
	public static int binarySearch(int array[],int low,int high,int temp)
	{
		int mid=0;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(array[mid]<temp&&temp<=array[mid+1])
				return (mid+1);
			else if(array[mid]<temp)
				low = mid + 1;
			else
				high = mid -1;
		}
		return high;
	}
	
	//二分排序
	public static void binarySort(int array[],int size)
	{
		int i,j,k,temp;
		for(i=1;i<size;i++)
		{
			temp=array[i];
			if(array[i]<array[0])
				k=0;
			else
				k = binarySearch(array,0,i,temp);
			
			for(j=i;j>k;j--)
			{
				array[j]=array[j-1];
			}
			array[k]=temp;
			System.out.println(Arrays.toString(array));
		}
	}
}

 

运行结果如下：

[38, 49, 65, 97, 76, 13, 27]第一次
[38, 49, 65, 97, 76, 13, 27]第二次
[38, 49, 65, 97, 76, 13, 27]第三次
[38, 49, 65, 76, 97, 13, 27]第四次
[13, 38, 49, 65, 76, 97, 27]第五次
[13, 27, 38, 49, 65, 76, 97]第六次
[13, 27, 38, 49, 65, 76, 97]这个是最终打印的结果

 

第二种：

package sort;

import java.util.Arrays;

public class BinarySearch2 {
	public static void main(String args[])
	{
		int array[]={49,38,65,97,76,13,27};
		binaryInsertSort(array,array.length);
		System.out.println("------------排序后的结果-------------");
		System.out.println(Arrays.toString(array));
	}
	
	/**
	 * 
	 * @param array 要排序的数组
	 * @param size 数组的大小
	 */
	public static void binaryInsertSort(int []array,int size)
	{
		int i,j,temp;
		int low,high,mid;
		for(i=1;i<size;i++)
		{
			//将待插入的元素赋给temp，这个元素前面是有序数组，用于插入到有序数组中
			temp=array[i];
			low=0;
			high=i-1;
			while(low<=high)
			{
				//有序数组的中间坐标，此时用于二分查找，减少查找次数
				mid = (low+high)/2;
				//如果有序序列中的中间元素大于待排序的元素，则有序序列的中间坐标向前搜索，否则向后搜索
				if(array[mid]>array[i])
					high=mid-1;
				else
					low = mid + 1;
			}
			/**
			 * j首先赋值为要插入值的前一个元素的最后的坐标，也就是有序数组中最后一个元素的坐标
			 * 然后依次向前扫描有序数组，然后如果满足条件则向后移动数据
			 */
			
			for(j=i-1;j>=low;j--)
			{
				array[j+1]=array[j];
			}
			//将待排序的元素插入到array数组中
			array[low]=temp;
			System.out.println(Arrays.toString(array));
		}
	}
	
}

 运行结果：

[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 76, 97, 13, 27]
[13, 38, 49, 65, 76, 97, 27]
[13, 27, 38, 49, 65, 76, 97]
------------排序后的结果-------------
[13, 27, 38, 49, 65, 76, 97]