直接插入排序

直接插入排序思想：

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

步骤：

L[ ]表示一个表，L()表示一个元素

1>查找出L(i)在L[1.....i-1]中的插入位置k

2>将L[k...i-1]中所有元素全部后移一个位置

3>将L(i)复制到L(k)

【图来自bilili,马士兵】

代码演示[以下使用的数组]：

package com;

public class Test {
    public static void directlySort(int[] l,int n) {
        int i, j;
        int k=0;
        for (i = 1; i < n; i++) {
            if(l[i]<l[i-1]){
                k=l[i];
                for(j=i-1;k<l[j];--j){
                    l[j+1]=l[j];
                    if(j==0){
                        j=-1;
                        break;
                    }
                }
                if(j==-1){
                    l[0]=k;
                }else{
                    l[j+1]=k;
                }
            }
            System.out.println("第"+i+"次排序结果");
            printArr(l);
        }
        System.out.println("最终直接插入排序结果");
        printArr(l);
    }
    public static void printArr(int[] l){
        for(int m=0;m<l.length;m++){
            System.out.print(l[m]+",");
        }
        System.out.print("\n");
    }

    public static void main(String[] args) {
        int[] a={9,6,1,3,5};
        directlySort(a,a.length);
    }
}

输出结果：