插入排序簡介

• 插入排序（insertion sort)是從第一個元素開始，該元素就認為已經被排序過了。
• 然后取出下一個元素，從該元素的前一個索引下標開始往前掃描，比該值大的元素往后移動。
• 直到遇到比它小的元素時候，比它小元素的下一個元素就是該元素的位置；當索引值為0的時候，那么索引為0的位置就是該元素的位置。

代碼實現

package com.xxliao.algorithms.sort.insertion_sort;/*** @author xxliao* @description: 插入排序* @date 2024/5/30 21:44*/
public class InsertionSort {public static void main(String[] args) {int[] array = {1,6,2,6,8,3,8,3,9,3,4,6,56,8};System.out.print("排序前：");printArray(array);sort(array);System.out.print("排序后：");printArray(array);}/*** @description  插入排序* @author  xxliao* @date  2024/5/30 21:46*/public static void sort(int[] array) {for (int i = 1; i <= array.length - 1; i++) {int temp = array[i]; //記錄當前值int j = i -1; //記錄值索引的前一個值，也就是當前值，需要和前面0 ~  i-1 范圍的值進行比較。while(j >= 0 && array[j] > temp) { //前面的值 比 后面的值大，進行交換array[j+1] = array[j]; // 將大的值往后移動一位，原值在temp中j--;}// 找到放置的位置，賦值array[j+1] = temp;printArray(array);}}/*** @description  打印數組* @author  xxliao* @date  2024/5/30 21:47*/public static void printArray(int[] array) {for (int i = 0; i <= array.length - 1; i++) {System.out.print(array[i]+" ");}System.out.println();}
}

演示結果：