排序算法圖解之Java插入排序

更新時間：2022年11月06日 09:01:00 作者：興趣使然黃小黃

插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。本文通過圖片合示例講解了插入排序的實現，需要的可以了解一下

1.插入排序簡介

插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。在其實現過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內層循環(huán)對當前元素前面有序表進行待插入位置查找，并進行移動

2.插入排序思想及圖解

插入排序的基本思想如下：

把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為一個新的有序表。

以序列：{55, 85, 21, 12, 5} 為例，圖解如下：

粉紅色部分為每輪認定的有序部分，其余顏色為認定的無序部分。綠色標識為每輪遍歷的無序序列的位置，將該位置的元素逐一與有序部分進行比較，找到合適的位置進行順序表的插入操作。

3.插入排序代碼實現

import java.util.Arrays;

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] array = {55, 85, 21, 12, 5};
        System.out.println("排序前: " + Arrays.toString(array));
        insertSort(array);
        System.out.println("排序后: " + Arrays.toString(array));
    }

    //插入排序
    public static void insertSort(int[] arr){
        //邊界條件
        if (arr.length < 1){
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            //定義待插入的位置和待插入的數
            int insertIndex = i-1; //arr[i]前面的位置,便于插入
            int insertVal = arr[i]; //先將待插入的值保存
            //給insertVal找到待插入的位置
            //1.insertIndex > 0防止越界
            //2.insertVal < arr[insertIndex] 說明還未找到待插入的位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex != i){
                arr[insertIndex+1] = insertVal; //插入
            }
            System.out.println("第" + i + "輪: " + Arrays.toString(arr));
        }
    }
}