简介

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

思想

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

代码实现

package com.yuan.common.sort;

import java.util.Arrays;

/**
 * 插入排序
 * @author Yuan-9826
 */

public class InsertionSort {

    public static void insertAsc(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            //左边的数组序数是arr[0-i) 每次遍历完扩容为 [0-i]
            //遍历有序数组
            for (int j = 0; j < i; j++) {
                int left = arr[i];
                if (arr[i] <= arr[j]) {
                    //说明这个数小那就插在arr[j]前面
                    for (int k = i; k > j; k--) {
                        arr[k] = arr[k - 1];
                    }
                    //将要插入有序数组一边的数插进去
                    arr[j] = left;
                }
            }
        }
    }

    public static void selectDesc(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //左边的数组序数是arr[0-i) 每次遍历完扩容为 [0-i]
            //遍历有序数组
            for (int j = 0; j < i; j++) {
                int left = arr[i];
                if (arr[i] >= arr[j]) {
                    //说明这个数小那就插在arr[j]前面
                    for (int k = i; k > j; k--) {
                        arr[k] = arr[k - 1];
                    }
                    //将要插入有序数组一边的数插进去
                    arr[j] = left;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 5, 5, 6, 0, 1, 6, 1, 2, 3, 7, 8, 9};
        System.out.println(Arrays.toString(arr));
        insertAsc(arr);
        System.out.println("-----------------------");
        System.out.println(Arrays.toString(arr));
        System.out.println("-----------------------");
         selectDesc(arr);
        System.out.println(Arrays.toString(arr));
    }
}