插入排序——折半插入排序

悠悠 2021-12-13 14:45 259阅读 0赞

折半插入排序是基于直接插入排序的优化。  
[直接插入排序][Link 1]  
将第i个元素插入时，通过折半查找的方式，来查找第i个元素合适的位置。

## 推导过程 ##

当0~(i-1)位置上的元素都已经排序OK，现需要插入第i个元素，设其值为temp;  
令low=0, high=i, mid=(high+low)/2。那么temp可能插入的位置是：low~high。每一次循环对范围的缩小都要保持这个性质不变。分两种情况讨论：

1.  temp<array\[mid\]。虽然temp<array\[mid\]，但是temp还是有可能插入到mid位置上。所以：  
    low = low;  
    high = mid;
2.  temp>=array\[mid\]。既然temp>=array\[mid\]，则一定不可能插入到mid位置上。所以：  
    low = mid + 1;  
    high = high;

那么循环结束的条件是什么呢？  
结论：  
循环结束的条件是low==high，此时唯一确定temp的插入位置。

不管有多少个元素，都会最终分解成以下情况，然后得到low==high，确定插入位置。

1.  high == low + 2 ——> mid = low+1;  
    如果temp<array\[mid\]，则进入情况2）;  
    如果此时temp>=array\[mid\]，则插入位置被直接确定下来，为high。
2.  high==low+1——>mid=low;  
    如果temp<array\[mid\]，则插入位置确定，为low。  
    如果temp>=array\[mid\]，则插入位置确定，为high。

## 代码 ##

package dataStructureAndAlgorithms;
    
    public class InsertSort_binarySort {
        
    
    	public static void main(String args[]) {
        
    		int[] array = {
         4, 2, 8, 9, 5, 7, 1, 6, 3 };
    
    		System.out.println("折半插入排序(升序)：");
    		System.out.println("未排序数组顺序为：");
    		display(array);
    		System.out.println("-----------------------");
    		sort(array);
    		System.out.println("-----------------------");
    		System.out.println("经过排序后的数组顺序为：");
    		display(array);
    		System.out.println();
    	}
    	
    	//	折半插入排序
    	public static void sort(int[] array){
        
    		int length = array.length;
    		//将位置i上的元素插入前面已经排好序的队列
    		for(int i=1;i<=length-1;i++){
        
    			int temp = array[i];
    			int high = i;
    			int low = 0;
    			//寻找合适的插入位置
    			while(low<high){
        
    				int mid = (low+high)/2;
    				if(temp < array[mid]){
        
    					high = mid;
    				}else{
        
    					low = mid + 1;
    				}
    			}			
    			
    			//此时low==mid
    			if(low != high)
    			{
        
    				System.out.println("fatal error!.low != high");
    				System.exit(0);
    			}
    			for(int j=i;j>low;j--){
        
    				array[j] = array[j-1];
    			}
    			array[low] = temp;
    			
    			
    			System.out.println("经过第"+ i + "轮排序后：");
    			display(array);
    		}
    	}
    	
    	public static void display(int[] array) {
        
    		for (int i = 0; i < array.length; i++) {
        
    			System.out.print(array[i] + " ");
    		}
    		System.out.println();
    	}
    }

## 输出 ##

折半插入排序(升序)：
    未排序数组顺序为：
    4 2 8 9 5 7 1 6 3 
    -----------------------
    经过第1轮排序后：
    2 4 8 9 5 7 1 6 3 
    经过第2轮排序后：
    2 4 8 9 5 7 1 6 3 
    经过第3轮排序后：
    2 4 8 9 5 7 1 6 3 
    经过第4轮排序后：
    2 4 5 8 9 7 1 6 3 
    经过第5轮排序后：
    2 4 5 7 8 9 1 6 3 
    经过第6轮排序后：
    1 2 4 5 7 8 9 6 3 
    经过第7轮排序后：
    1 2 4 5 6 7 8 9 3 
    经过第8轮排序后：
    1 2 3 4 5 6 7 8 9 
    -----------------------
    经过排序后的数组顺序为：
    1 2 3 4 5 6 7 8 9

[Link 1]: https://blog.csdn.net/qq_31567335/article/details/94985064