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

 

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

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

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

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

第一种：

  package sort;

Java代码  

1. import java.util.Arrays;   
2.   
3. public class BinarySearch1 {   
4.     public static void main(String args[])   
5.     {   
6.         int array[]={49,38,65,97,76,13,27};   
7.         binarySort(array,array.length);   
8.         System.out.println("---------排序后的结果----------");   
9.         System.out.println(Arrays.toString(array));   
10.     }   
11.        
12.     //二分查找   
13.     public static int binarySearch(int array[],int low,int high,int temp)   
14.     {   
15.         int mid=0;   
16.         while(low<=high)   
17.         {   
18.             mid=(low high)/2;   
19.             if(array[mid]<temp&&temp<=array[mid 1])   
20.                 return (mid 1);   
21.             else if(array[mid]<temp)   
22.                 low = mid   1;   
23.             else  
24.                 high = mid -1;   
25.         }   
26.         return high;   
27.     }   
28.        
29.     //二分排序   
30.     public static void binarySort(int array[],int size)   
31.     {   
32.         int i,j,k,temp;   
33.         for(i=1;i<size;i )   
34.         {   
35.             temp=array[i];   
36.             if(array[i]<array[0])   
37.                 k=0;   
38.             else  
39.                 k = binarySearch(array,0,i,temp);   
40.                
41.             for(j=i;j>k;j--)   
42.             {   
43.                 array[j]=array[j-1];   
44.             }   
45.             array[k]=temp;   
46.             System.out.println(Arrays.toString(array));   
47.         }   
48.     }   
49. }  

 

运行结果如下：

  [38, 49, 65, 97, 76, 13, 27]

Java代码  

1. [38, 49, 65, 97, 76, 13, 27]   
2. [38, 49, 65, 97, 76, 13, 27]   
3. [38, 49, 65, 76, 97, 13, 27]   
4. [13, 38, 49, 65, 76, 97, 27]   
5. [13, 27, 38, 49, 65, 76, 97]   
6. ---------排序后的结果----------   
7. [13, 27, 38, 49, 65, 76, 97]  

 

第二种：

 

Java代码  

1. package sort;   
2.   
3. import java.util.Arrays;   
4.   
5. public class BinarySearch2 {   
6.     public static void main(String args[])   
7.     {   
8.         int array[]={49,38,65,97,76,13,27};   
9.         binaryInsertSort(array,array.length);   
10.         System.out.println("------------排序后的结果-------------");   
11.         System.out.println(Arrays.toString(array));   
12.     }   
13.        
14.     /**  
15.      *   
16.      * @param array 要排序的数组  
17.      * @param size 数组的大小  
18.      */  
19.     public static void binaryInsertSort(int []array,int size)   
20.     {   
21.         int i,j,temp;   
22.         int low,high,mid;   
23.         for(i=1;i<size;i )   
24.         {   
25.             //将待插入的元素赋给temp，这个元素前面是有序数组，用于插入到有序数组中   
26.             temp=array[i];   
27.             low=0;   
28.             high=i-1;   
29.             while(low<=high)   
30.             {   
31.                 //有序数组的中间坐标，此时用于二分查找，减少查找次数   
32.                 mid = (low high)/2;   
33.                 //如果有序序列中的中间元素大于待排序的元素，则有序序列的中间坐标向前搜索，否则向后搜索   
34.                 if(array[mid]>array[i])   
35.                     high=mid-1;   
36.                 else  
37.                     low = mid   1;   
38.             }   
39.             /**  
40.              * j首先赋值为要插入值的前一个元素的最后的坐标，也就是有序数组中最后一个元素的坐标  
41.              * 然后依次向前扫描有序数组，然后如果满足条件则向后移动数据  
42.              */  
43.                
44.             for(j=i-1;j>=low;j--)   
45.             {   
46.                 array[j 1]=array[j];   
47.             }   
48.             //将待排序的元素插入到array数组中   
49.             array[low]=temp;   
50.             System.out.println(Arrays.toString(array));   
51.         }   
52.     }   
53.        
54. }  

 运行结果：

 

Java代码  

1. [38, 49, 65, 97, 76, 13, 27]   
2. [38, 49, 65, 97, 76, 13, 27]   
3. [38, 49, 65, 97, 76, 13, 27]   
4. [38, 49, 65, 76, 97, 13, 27]   
5. [13, 38, 49, 65, 76, 97, 27]   
6. [13, 27, 38, 49, 65, 76, 97]   
7. ------------排序后的结果-------------   
8. [13, 27, 38, 49, 65, 76, 97]