基础算法练习04--折半插入排序

悠悠 2024-02-19 14:02 46阅读 0赞

**折半插入排序相比直接插入排序，时间复杂度并没有改变。但是，折半插入排序减少了元素比较的次数。基本的操作就是：通过折半查找，找到有序序列中要插入的位置。从这个位置开始往后，有序序列的所有元素向后移动一位，将需要插入的元素放入这个位置。**

**代码：**

package cn.drc.sort.insertsort;
    
    import java.util.Arrays;
    
    /**
     * 折半插入排序
     * @author drc
     *
     */
    public class HalfInsertSortDemo {
        public static void main(String[] args) {
    	int[] arr = {4,8,6,45,3,68,64,5,34,36,0,42,48,9,
    	    41,1,2,89,34,10,63,7,48,96,51,20,74};
    	halfInsertSort(arr);
    	System.out.println(Arrays.toString(arr));
        }
    	
        static int[] halfInsertSort(int[] arr) {
    	// 有序序列的初始长度为1
    	int orderLength = 1;
            // 既然要进行折半的操作，那么就需要有序序列头和尾
            int start, end, mid;
    	while (orderLength < arr.length) {
    	    // 纪录需要插入的元素
    	    int toInsert = arr[orderLength];
    	    start = 0;
    	    end = orderLength - 1;
    		
    	    mid = 0;
    	    while (start<=end) {
    		// 每次要加入一个元素的时候，都需要将有序序列进行折半，和要插入的元素进行比较
    		mid = (start+end)/2;
    		
    		if (arr[(start+end)/2] > toInsert) { // 要插入的位置在低半区
    		    end = mid-1;
    		} else { // 要插入的位置在高半区
    		    start = mid+1;
    		}
                }
    			
    	    for (int x=orderLength; x>start; x--) {
    	        // 从插入位置开始所有元素后移
    	        arr[x] = arr[x-1];
    	    }
    	    // 插入
    	    arr[start] = toInsert;
    	    // 有序序列长度自增1
    	    orderLength++;
            }
        return arr;
        }
    }