[数据结构与算法]Java排序算法（三）插入排序

插入排序

算法思想

插入排序就是通过构建有序数列，然后对于未排序的数据在已经有序的序列中从后往前扫描，找到合适的位置并插入。

算法描述

①从给定的序列中的第一个元素开始，默认该元素已经在有序序列。
②取出下一个元素并保存在一个临时变量temp中（防止数据移动时该元素丢失），在已经排序的有序序列中从后往前扫描。
③如果该元素大于temp，则继续往前扫描到下一个元素。
④重复步骤③，直到在已排序的序列中找到小于等于temp的元素。temp插入到该元素的后面；如果已排序的序列中的所有元素都大于temp，那么将temp元素插入到已排序的序列中的第一个位置。
⑤重复步骤②到④，直到所有的元素排序完毕。

动画演示

代码演示

import java.util.Arrays;

public class SortTest03 {
    public static void insertSort(int[] arr) {
        //安全检测
        if (arr == null || arr.length == 1) {
            return;
        }

        for (int i = 1;i < arr.length;i++) {
            int temp = arr[i];
            int j = i - 1;
            for (;j >= 0;j--) {
                if (temp < arr[j]) {
                    arr[j + 1] = arr[j];
                }else {//temp >= arr[j]
                    arr[j + 1] = temp;
                    break;
                }
            }
            //已排序的序列中没有一个元素小于temp
            //temp放在已经排序好的序列中的0号位置
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println("排序前:" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}

运行结果：

插入排序算法分析

🙈时间复杂度： 最优时间复杂度：O(n)，平均时间复杂度：O(n²)，最差时间复杂度：O(n²)
🙊空间复杂度： 平均空间复杂度：O(1)
🙉稳定性： 稳定