2 插入排序

快速理解插入排序（非降序排序，从前开始的排序）
插入排序类似于打牌，左侧是已经排好的序列，右侧是没有排好的序列
用y表示已经排好序的序列下标，用n表示没排序的下标，并且假设序列的下标 从0开始
先看一波伪代码：

int n,y
for n=1 to arr.length
    key = arr[n]
    for(y = n-1;y>=0 && key<arr[y];y--)
        arr[y+1] = arr[y]
    arr[y+1] = key
return arr

我们可以参考一下《算法导论》给出的插入排序
因为它给出的数组默认下标是1，所以j是从2开始，while循环是A[j]>key

/**
 * 插入排序
 * 类似于打牌是抽牌放位置
 */
public class InsertionSort {

    /**
     * 非降序排序
     * @param arr
     * @return
     */
    public static int []  InsertionSort(int arr[]){
        int n,y;  //n 指未排序的，y指以排好序的
        for(n = 1;n<arr.length;n++){
            int key = arr[n];    //取出一张未排序的牌
             //找出空位 实际按照理论y应该是空位，但是最后又执行了一次y--，所以最后的空位应该是y+1
            for(y = n-1;y>=0 && arr[y]>key;y--){  
                arr[y+1] = arr[y];
            }
            arr[y+1] = key;  //把牌放入到y+1的空位中
        }

        return arr;
    }

    public static void main (String [] args){
        int arr[]={5,4,3,2,1};
        arr = InsertionSort(arr);

        //输出
        for(int num : arr){
            System.out.print(num+" ");
        }
    }
}

插入排序分析

时间复杂度：
空间复杂度：
稳定性：