排序算法——插入排序

题目：将该数组int[] data = {8,5,7,4,1,3,2}进行排序，要求手写插入排序进行实现。

插入排序整体思想：
将一个数组分成已排序和未排序两个部分，每次都从未排序的部分中取出一个数(b)，和已排序部分中的每个元素(arr[i])去
做比较，如果在已排序部分中找到一个数小于从未排序中拿出来的那个数(arr[i]<b)，就停止比较，将未排序部分取出来的
数插入到已排序部分比较小的元素后面(arr[i+1] = b)；每次从未排序部分取一个数都重复上面步骤，直到排序完成。
注意：未排序数字和已排序部分在作比较的时候，最好是从已排序部分的尾部开始比较，依次往头部进行。这样做的好处就是可以保证
元素之间的相对位置不会改变，同时在比较的时候同步可以向后移动数组元素，为即将插入的数字预留空间。降低时间复杂度

代码实现：

package com.lhb.test;

import java.util.Arrays;

/**
 * @Program: netty-chat
 * @Description:
 * @Author: LHB
 * @Version: v0.0.1
 * @Time: 2021-11-03 12:15
 **/
public class SortTest {
    /**
     * 插入排序整体思想：
     *   将一个数组分成已排序和未排序两个部分，每次都从未排序的部分中取出一个数(b)，和已排序部分中的每个元素(arr[i])去
     *   做比较，如果在已排序部分中找到一个数小于从未排序中拿出来的那个数(arr[i]<b)，就停止比较，将未排序部分取出来的
     *   数插入到已排序部分比较小的元素后面(arr[i+1] = b)；每次从未排序部分取一个数都重复上面步骤，直到排序完成。
     * 注意：未排序数字和已排序部分在作比较的时候，最好是从已排序部分的尾部开始比较，依次往头部进行。这样做的好处就是可以保证
     * 元素之间的相对位置不会改变，同时在比较的时候同步可以向后移动数组元素，为即将插入的数字预留空间。降低时间复杂度
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        if (arr.length > 0) {
            // 这里有两层循环
            // 时间复杂度最坏是: O(n²)-----每次都会执行第二次循环中的if语句
            // 时间复杂度最好是: O(n)------即每次都执行第二次循环的break
            for (int i = 1; i < arr.length; i++) {
                int data = arr[i];
                int j = i - 1;
                for (; j >= 0 ; j--) {
                    if (data < arr[j]) {
                        arr[j+1] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j+1] = data;
            }
        }
        return arr;
    }

    // 插入排序第二种写法
    public static void insertSort(int[] data) {
        int length = data.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >0 && data[j] < data[j-1]; j--) {
                int tmp = data[j];
                data[j] = data[j-1];
                data[j-1] = tmp;
            }

        }
    }
  

    public static void main(String[] args) {
        int[] data = {8,5,7,4,1,3,2};
        int[] result = insertSort(data);
        System.out.println(Arrays.toString(result));
    }
}

运行结果如下：