[数据结构与算法]java 直接插入排序

思路

将数组分为有序区间 和 无排序区间，默认第一个为有序区间，依次从左到右，左边第一个为有序区间，取无排序区间第一个数，与有序区间末尾数进行比较，如果小则互换位置，直到该树找到有序区间的合适位置为止，一直轮询此操作

java 示例

package com.example.demo.sort;

import cn.hutool.core.collection.CollectionUtil;
import cn.hutool.core.util.ArrayUtil;

import java.util.Collections;
import java.util.Random;


/**
 * @ Author     ：syc.
 * @ Date       ：Created in 上午10:04 2021/11/17
 * @ Description：
 * 直接插入排序
 * @ Modified By：
 * @ Version:
 */
public class DirectInsertionSort {
    public static void main(String[] args) {
        int num = 20;
        int[] nums = new int[num];
        Random r = new Random(1);
        for (int i = 0; i < num; i++) {
            nums[i] = r.nextInt(100);
        }
        DirectInsertionSort directInsertionSort = new DirectInsertionSort();
        directInsertionSort.sort(nums);
    }

    public void sort(int[] num) {
        for (int i = 0; i < num.length - 1; i++) {
            // end 为有序区间的末尾元素
            for (int end = i; end >= 0; end--) {
                // end + 1 为 未排序区间的第一个元素,需要将其放在有序区间合适位置
                // 如果未排序区间第一个元素小于有序区间元素 则将其两位置互换,直到找到合适的位置存放
                if (num[end + 1] < num[end]) {
                    int temp = num[end];
                    num[end] = num[end + 1];
                    num[end + 1] = temp;
                } else {
                    // 这里证明找到了合适的位置,此时有序区间排序完毕,结束寻找,进行下次轮询
                    break;
                }
            }
            System.out.println(String.format("有序,无序情况   [%s] - [%s]", CollectionUtil.join(Collections.singleton(ArrayUtil.sub(num, 0, i + 1)), ","), CollectionUtil.join(Collections.singleton(ArrayUtil.sub(num, i + 1, num.length)), ",")));
        }
    }
}

运行结果

有序,无序情况   [85] - [88,47,13,54,4,34,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [47,85] - [88,13,54,4,34,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [13,47,85] - [88,54,4,34,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [13,47,54,85] - [88,4,34,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,13,47,54,85] - [88,34,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,13,34,47,54,85] - [88,6,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,34,47,54,85] - [88,78,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,34,47,54,78,85] - [88,48,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,34,47,48,54,78,85] - [88,69,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,34,47,48,54,69,78,85] - [88,73,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,34,47,48,54,69,73,78,85] - [88,17,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,17,34,47,48,54,69,73,78,85] - [88,63,62,34,92,62,96,89]
有序,无序情况   [4,6,13,17,34,47,48,54,63,69,73,78,85] - [88,62,34,92,62,96,89]
有序,无序情况   [4,6,13,17,34,47,48,54,62,63,69,73,78,85] - [88,34,92,62,96,89]
有序,无序情况   [4,6,13,17,34,34,47,48,54,62,63,69,73,78,85] - [88,92,62,96,89]
有序,无序情况   [4,6,13,17,34,34,47,48,54,62,63,69,73,78,85,88] - [92,62,96,89]
有序,无序情况   [4,6,13,17,34,34,47,48,54,62,62,63,69,73,78,85,88] - [92,96,89]
有序,无序情况   [4,6,13,17,34,34,47,48,54,62,62,63,69,73,78,85,88,92] - [96,89]
有序,无序情况   [4,6,13,17,34,34,47,48,54,62,62,63,69,73,78,85,88,89,92] - [96]