java排序算法（七）：折半插入排序

2018-06-18 03:09:42来源：未知阅读 ()

java排序算法（七）：折半插入排序

　　折半插入排序法又称为二分插入排序法，是直接插入排序法的改良版本，也需要执行i-1趟插入。不同之处在于第i趟插入。先找出第i+1个元素应该插入的位置。假设前i个数据是已经处于有序状态

　　代码实现

package com.spring.test;

/**
 * 折半插入排序
 */
public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        print(data);
        binaryInsertSort(data);
        print(data);
    }

    /**
     * 折半插入
     * @param data
     */
    public static void binaryInsertSort(int[] data){
        for(int i=1;i<data.length;i++){
            if(data[i] < data[i-1]){
                //缓存i处的元素值
                int tmp = data[i];
                //记录搜索范围的左边界
                int low = 0;
                int high = i-1;
                while(low <= high){
                    //记录中间位置
                    int mid = (low+high)/2;
                    //比较中间位置数据和i处数据大小，以缩小搜索范围
                    if(data[mid] < tmp){
                        low = mid +1;
                    }else{
                        high = mid - 1;
                    }
                }
                //将low---i处的数据整体向后移动1位
                for(int j = i;j>low;j--){
                    data[j] = data[j-1];
                }
                data[low] = tmp;
                print(data);
            }
        }
    }


    /**
     * 对两个数据进行交换
     * @param data
     * @param i
     * @param j
     */
    public static void swap(int[] data,int i,int j){
        if(i==j){
            return ;
        }
        data[i] = data[i] + data[j];
        data[j] = data[i] - data[j];
        data[i] = data[i] - data[j];
    }

    /**
     * 对数组进行打印输出
     * @param data
     */
    public static void print(int[] data){
        for(int i=0;i<data.length;i++){
            System.out.print(data[i]+"\t");
        }
        System.out.println();
    }
}