排序：插入排序法（Java,Kotlin）

定义

插入排序法定义

无聊的解释（百度百科）：
假设我们输入的是 5，1，4，2，3 我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了 1，5，4，2，3
接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 1，4，5，2，3我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了，以此类推。。。

插入排序的日常应用

简单示例

工具类SortUtils

Java示例代码

两种：1.交换；2.赋值

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = SortUtils.getRandomIntArray(10000, 1, 1000);
        insertSort2(arr);
        SortUtils.printArray(arr);
    }

    private static void insertSort(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            //寻找元素arr[i]的合适插入位置
            //1.如果j-1位置值比j位置值大，交换
            for(int j=i;j>0;j--){
                if(arr[j]<arr[j-1]){
                    SortUtils.swap(arr,j,j-1);
                }else{
                    break;
                }
            }
        }
    }

    private static void insertSort2(int[] arr) {
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            //寻找元素arr[i]的合适插入位置;
            // 1.提取出arr[i];
            // 2.如果j-1位置的数比j位置值大，j位置值等于j-1位置;
            // 3.把提取出来的值赋值给及位置
            int temp = arr[i];
            int j = i;
            for(;j>0;j--){
                if(arr[j-1]>temp){
                    arr[j] = arr[j - 1];
                }else{
                    break;
                }
            }
            arr[j] = temp;
        }
    }
}

Kotlin

fun main(args: Array<String>) {
    val arr = SortUtils.getRandomIntArray(10000,1,1000)
    insertSortKt2(arr)
    SortUtils.printArray(arr)
}

//交换
fun insertSortKt(arr:IntArray){
    val length =arr.size
    for ((key,value) in arr.withIndex()){
        var j = key
        while (j>0&&(arr[j-1]-arr[j])>0){
            SortUtils.swap(arr,j-1,j)
            j--
        }
    }
}

//赋值
fun insertSortKt2(arr:IntArray){
    val length =arr.size
    for ((key,value) in arr.withIndex()){
        var j = key
        var temp =arr[j]
        while (j>0&&(arr[j-1]-temp)>0){
            arr[j]=arr[j-1]
            j--
        }
        arr[j]=temp
    }
}

后记

• 赋值的排序方法要比交换的运行速度快。尤其是一些数据基本已经有序，只有几个无序时，尤其适用。
• Kotlin不能直接使用工具类中的反射，这个还没太研究明白=。=