直接插入排序

思想: 将待排序数组看成无序区, 排序开始时,取出无序区的元素放入到有序区的合适位置上 

自序列的插入方式为从后往前依次比较插入

7 1 8 2 3 9 6 

初始时, 7 元素视为一个已排好序的子序列 

遍历到1时,    比较 子序列中  7 大于1  插入到子序列的后面 

此时子序列   [1,7]

遍历到元素 8 时  与子序列中的元素进行比较  8大于7   插入到子序列的后面 

此时子序列 [1,7,8]

遍历到元素2 时, 与子序列中的元素进行比较 2 小于8  2 小于7 2 大于1 插入到1的后面 

此时子序列[1,2,7,8]

遍历到元素3时, 与子序列中的元素进行比较 3 小于8 ,3小于7, 3大于2 插入到2后面的位置

此时子序列 [1,2,3,7,8]

遍历到元素9时, 与子序列中的元素进行比较  9 大于8  插入到8后面的位置 

此时子序列 [1,2,3,7,8,9]

遍历到元素6时, 与子序列中的元素进行比较  6 小于9 6小于8 , 6 小于7 6 大于3 插入到3后面的位置

此时子序列[1,2,3,6,7,8,9]

完成排序

代码

public int[] InsertSort(int[] sourceArray){
    int[] arr=Array.copyOf(sourceArray, sourceArray.length)
    //从下标为1的元素开始选择合适的位置插入,因为下标0只有一个元素,默认在有序子序列
    for (int i=1; i < arr.length; i++){
        //记录要插入的数据
        int tmp=arr[i];
        
        // 从已经排序的子序列的右边开始比较, 找到比其小的数
        int j = i;
        while (j >0 && tmp < arr[j-1]){
            arr[j] = arr[j-1];
            j--;
        }
        //存入比其小的数, 插入
        if(j !=i){
            arr[j]=tmp;
        }
    }
    return arr;
}