(十二）排序算法-插入排序

飞熊 • 2023年5月10日下午10:45 • 后端开发 • 阅读 290

1 基本介绍

1.1 概述

插入排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我
们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在
手中的每张牌进行比较，如下图所示：

它的算法思想则是将整个序列划分成两段,一段时已经排序完成的序列,另一端序列则是仍然无需的状态，下图所示。

分成这样两个序列之后，插入序列每次都是挑选待排序序列的队头元素插入到已有序的序列之中，从有序序列的队尾开始比较，如果比该元素大的话，将该元素后移，一旦出现小于该元素的元素，插入当前的位置。这个就是插入排序名字的由来。

1.2 算法详解

插入排序大思想：
插入排序（Insertion Sorting）的基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
插入排序思路图，如下所示。

动画展示：

2 代码实现

2.1 代码实现

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {45,2,6,265,2,5,74,52};
        System.out.println(Arrays.toString(arr));
        System.out.println("------------排序前------------");
        insertSort(arr);
        System.out.println("------------排序后------------");
        System.out.println(Arrays.toString(arr));
    }

    // 插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;

            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            arr[insertIndex+1] = insertVal;
            System.out.println("第" + i + "轮插入");
            System.out.println(Arrays.toString(arr));

        }
    }
}