插入排序&&直接插入

插入排序有哪些

包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。
属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置）

直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中
，直到所有的记录插入完为止，得到一个新的有序序列。

例如,已知待排序的一组记录是：
60,71,49,11,24,3,66
假设在排序过程中，前3个记录已按关键码值递增的次序重新排列，构成一个有序序列：
49,60,71
将待排序记录中的第4个记录（即11）插入上述有序序列，以得到一个新的含4个记录的有序序列。首先，应找到11的插入位置，
再进行插入。可以讲11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，
11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。
假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的记录依照同样的
方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序，才能完成。

直接插入排序的算法思路：

（1） 设置监视哨r[0]，将待插入记录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。

插入排序用代码的实现方式

package Binary.Tree;

public class InsertSort {
    int[]a;
    public InsertSort() {
        a=new int[]{8,19,2,3,100,99,1000,888,-1,0};
    }
    public InsertSort(int size) {
        a=new int[size];
    }
    //插入排序
    public void inset_Sort() {
        int insertNode;
        for(int i=1;i<a.length;i++) {
            insertNode=a[i]; //保存插入节点的变量
            int j=i-1;
            while(j>=0 && insertNode<a[j]) {
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=insertNode;
        }
    }
    //遍历
    public void disPlay() {
        for (int e : a) {
            System.out.print(e+"\t");
        }
    }
    public static void main(String[] args) {
        InsertSort sort = new InsertSort();
        System.out.println("排序前的内容");
        sort.disPlay();
        System.out.println("\n"+"排序后的果");
        sort.inset_Sort();
        sort.disPlay();
    }
}