[数据结构与算法]数据结构与算法

插入排序

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {25, 58, 65, 41, 32, 11, 22, 98, 74};
        //记录无序的索引位置
        int index = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                //找到无序数组的索引
                index = i + 1;
                break;
            }
        }
        arr = insertsort(arr, index);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //插入排序
    public static int[] insertsort(int[] arr, int index) {
        for (int i = index; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            //索引大于0，并且前一个数值大于后一个数值
            while (j > 0 && temp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            //退出循环，位置找到
            arr[j] = temp;
        }
        return arr;
    }
}