插入排序

参考：插入排序，插入排序算法详解及实现

 

插入排序原理很简单，讲一组数据分成两组，我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。

 

为了排序方便，我们一般将数据第一个元素视为有序组，其他均为待插入组。

 

下面以升序为例进行一次图解：

 

 

 

public class InsertSort {

    public static void insertSort(int[] arrays){
        //临时变量
        int temp;

        //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
        for (int i = 1; i < arrays.length; i++) {

            temp = arrays[i];

            //如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
            while (i >= 1 && arrays[i - 1] > temp) {

                //往后退一个位置，让当前数据与之前前位进行比较
                arrays[i] = arrays[i - 1];

                //不断往前，直到退出循环
                i--;

            }

            //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
            arrays[i] = temp;

        }
    }

    public static void main(String[] args) {
        int[] arrays = {3, 2, 1, 3, 3};

        System.out.println("排序前："+ Arrays.toString(arrays));
        insertSort(arrays);
        System.out.println("排序后："+ Arrays.toString(arrays));
    }
}

 

参考：图解插入排序

       直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。   

 

    /**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arrays = {3, 2, 1, 3, 3};

        System.out.println("排序前："+ Arrays.toString(arrays));
        insertionSort(arrays);
        System.out.println("排序后："+ Arrays.toString(arrays));
    }