1. Basic introduction

Insertion sort is an internal sort method, which is to find the appropriate position of the element to be sorted by insertion, so as to achieve the purpose of sorting.

2. Basic ideas

See n elements to be sorted as an ordered table and an unordered table, start with an element, take the first element from the unordered table during the sorting process, compare its sorting code with that of the ordered table elements, insert it into the appropriate position in the ordered table, make it a new ordered table.

3. Application examples

There was a group of calves with test scores of 101, 34, 119, 1

Please sort from smallest to largest

    // Insert sort
    public static void insertSort(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        // Use the for loop to simplify the code
        for(int i = 1; i < arr.length; i++) {
            // Define the number to be inserted
            insertVal = arr[i];
            insertIndex = i - 1; Arr [1] = arr[1]

            // find the position of the insertVal
            / / that
            // 1. InsertIndex >= 0
            // 2. InsertVal < arr[insertIndex
            // 3. Arr [insertIndex] is inserted later
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
                insertIndex--;
            }
            // When exiting the while loop, insertIndex + 1 is found
            // For example
            // Here we determine whether an assignment is required
            if(insertIndex + 1! = i) { arr[insertIndex +1] = insertVal;
            }

            //System.out.println("第"+i+"轮插入");
            //System.out.println(Arrays.toString(arr));}}Copy the code

Testing:

public static void main(String[] args) {
        int[] arr = {101.34.119.1, -1.89};


        System.out.println("Before insertion sort");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("The time before sorting is equal to" + date1Str);

        insertSort(arr); // Call the insertion sort algorithm

        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("The time before sorting is equal to" + date2Str);

        System.out.println(Arrays.toString(arr));

    }
Copy the code