目錄

1、插入排序

2、流程介紹

3、java實現

4、性能介紹

---

前言

????????在 Java 中，?冒泡排序（Bubble Sort）?和?選擇排序（Selection Sort）?之后，下一個性能更好的排序算法通常是?插入排序（Insertion Sort）。

????????雖然它們的時間復雜度都是?O(n2)，但在實際應用中，插入排序通常比選擇排序和冒泡排序更快，尤其是在處理部分有序數據時表現更優。

總結：Java 排序算法進階路線

1. O(n2) 算法（適合學習原理）

   • 冒泡排序（最慢）→ 選擇排序 →?插入排序（推薦先學）

2. O(n log n) 算法（實際應用）

   • 歸并排序（穩定）→ 快速排序（最快，但不穩定）→ 堆排序（空間省）

3. Java 內置排序

   • Arrays.sort()：對基本類型用?快速排序，對象類型用?歸并排序（保證穩定性）。

---

1、插入排序

Insertion Sort：插入排序是一種簡單直觀的排序算法，適合小規模數據或部分有序數據。

1、核心思想

????????將數組分為?已排序?和?未排序?兩部分，逐個將未排序部分的元素插入到已排序部分的正確位置。

2、適合場景

小規模數據或基本有序的數據（如日志按時間插入）。

3、時間復雜度：

最壞情況下為O(N*N)，此時待排序列為逆序，或者說接近逆序。
最好情況下為O(N)，此時待排序列為升序，或者說接近升序。

4、空間復雜度：O(1)。

---

2、流程介紹

如下圖所示：

步驟：

1.從第一個元素開始，該元素可以認為已經被排序.
2.取下一個元素tem，從已排序的元素序列從后往前掃描.
3.如果該元素大于tem，則將該元素移到下一位.
4.重復步驟3，直到找到已排序元素中小于等于tem的元素.
5.tem插入到該元素的后面，如果已排序所有元素都大于tem，則將tem插入到下標為0的位置.
6.重復步驟2~5.

---

3、java實現

代碼示例如下：

public class InsertionSort {/*** 插入排序（升序）* @param arr 待排序數組*/public static void insertionSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 邊界條件：數組為空或長度≤1時無需排序}// 從第二個元素開始（下標1），默認第一個元素已排序for (int i = 1; i < arr.length; i++) {int current = arr[i]; // 當前待插入的元素int j = i - 1;       // 已排序部分的最后一個元素下標// 從后往前遍歷已排序部分，尋找插入位置while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j]; // 比 current 大的元素向后移動j--;}// 插入 current 到正確位置arr[j + 1] = current;}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};System.out.println("排序前: " + Arrays.toString(arr));insertionSort(arr);System.out.println("排序后: " + Arrays.toString(arr));}
}

輸出：

排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]

關鍵步驟解析

1. 外層循環：

   • 從?i = 1?開始（默認?arr[0]?是已排序部分）。

   • 每次迭代處理一個未排序元素?current = arr[i]。

2. 內層循環：

   • 從?j = i - 1?開始，反向遍歷已排序部分。

   • 如果?arr[j] > current，則將?arr[j]?向后移動一位。

   • 直到找到?arr[j] ≤ current?的位置，此時?j + 1?就是?current?的插入位置。

3. 插入操作：

   • 將?current?放入?arr[j + 1]。

---

4、性能介紹

??為什么插入排序比選擇排序快？

1. 比較次數更少：選擇排序每一輪都要遍歷剩余全部元素找最小值，而插入排序在數據基本有序時只需少量比較。

2. 提前終止：如果數據已經有序，插入排序內層循環會立即終止（類似冒泡優化版）。

3. 數據局部性：插入排序是順序訪問數組，對 CPU 緩存更友好。

---

總結

1. 小數組排序：

   • Java 的?Arrays.sort()?在子數組長度 ≤ 47 時，會切換到插入排序。

2. 部分有序數據：

   • 如日志按時間插入、游戲排行榜實時更新。

3. 混合排序算法：

   • 快速排序的遞歸基改用插入排序（如?QuickSort + InsertionSort）。

---

參考文章：

1、六大排序算法：插入排序、希爾排序、選擇排序、冒泡排序、堆排序、快速排序-CSDN博客https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%25220faf03d22b2d125d5f49a4649ad59c85%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=0faf03d22b2d125d5f49a4649ad59c85&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v102^control&utm_term=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187