直接插入排序 - JAVA学习网

基本思想

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

排序过程

1.初始化无序区、有序区，待排序数组的第一个元素为有序区，剩余元素为无序区；

2.遍历无序区，将无序区每一个元素插入到有序区的正确位置上；

Java算法实现

/**
 * 排序接口类
 * Created by zhouyh on 2018/5/25.
 */
public abstract class ISort {
    public abstract int[] sort(int[] array);
}

/**
 * 直接插入排序
 * Created by zhouyh on 2018/5/25.
 */
public class DirectInsertSort extends ISort {
    @Override
    public int[] sort(int[] array) {
        int tmp;
        for (int i=1; i<array.length; i++){
            tmp = array[i]; //array[i]的拷贝
            //如果右侧无序区第一个元素array[i] < array[i-1]小于左侧有序区最后一个元素
            //需要将左侧有序区比array[i]大的元素后移
            if (array[i] < array[i-1]){
                int j = i-1;
                while (j>=0 && tmp<array[j]){
                    array[j+1] = array[j];
                    j--;
                }
                array[j+1] = tmp;
            }
        }
        return array;
    }
}

View Code

JAVA学习网

分类