16、数据结构和算法 - 实战：插入排序算法

1.1 什么是插入排序

假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置。

1.2 算法基本思想

插入排序的基本思想是：将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组，把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。这样的话，n个元素需要进行n-1趟排序。

1.3 插入排序复杂度分析

插入排序的时间复杂度是 ：插入排序的时间复杂度是由两个循环构成，所以他的时间复杂度肯定是 。

1.3 插入排序代码实现

package com.yuanxw.datastructure.chapter16;

import java.util.Arrays;

/**
 * 插入排序
 * 插入排序类似于打扑克，取出未排序的一张牌插入到已排序的牌中，取出的一张牌是在已排序好的牌中从后向前查找，直到查找到比当前牌小的那个位置，然后插入进去
 * <p>
 * 每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止。
 * 当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移。
 */
public class InsertionSort {
   
     
    public static void main(String[] args) {
   
     
        int[] array = new int[]{
   
     10, -7, 8, -2, 5, -4};
        System.out.println("【插入排序】前的结果：" + Arrays.toString(array));
        insertionSort(array);
        System.out.println("【插入排序】后的结果：" + Arrays.toString(array));
    }

    public static void insertionSort(int[] array) {
   
     
        // 从第二个元素开始对比插入的位置
        for (int i = 1; i < array.length; i++) {
   
     
            // 需要插入排序的value
            int insertValue = array[i];
            // 排好序的结束位置
            int inserIndex = i - 1;
            // 条件：1.inserIndex >= 0  2.当前值比前一个比较大小。
            while (inserIndex >= 0 && insertValue < array[inserIndex]) {
   
     
                // 赋值动做操作
                array[inserIndex + 1] = array[inserIndex];
                // 每次赋值动做操作完后需要进行前移比较已经排好的元素。
                inserIndex--;
            }
            // 找到位置后，插入
            array[inserIndex + 1] = insertValue;
        }
    }
}

执行结果：

【插入排序】前的结果：[10, -7, 8, -2, 5, -4]
【插入排序】后的结果：[-7, -4, -2, 5, 8, 10]