詳解七大排序

一.直接插入排序

（1）基本思想

（2）算法步驟

（3）代碼實現

（4）算法特性

（5）算法優化

（6）示例演示

二.希爾排序

（1）基本思想

（2）算法步驟

（3）代碼實現

（4）算法特性

?（5）算法優化

（6）實例演示

?三.選擇排序

（1）基本思想

（2）算法步驟

（3）代碼實現

1）每次交換一個元素（最小元素）：

2）每次交換兩個元素（一個最大元素，一個最小元素）：

（4）算法特性

（5）算法優化

（6）實例演示

?四.堆排序

（1）基本思想

（2）算法步驟

（3）代碼實現

?（4）算法特性

（5）算法優化

（6）實例演示

1）建堆過程：

?2）排序階段

五.冒泡排序

（1）基本思想

（2）算法步驟

（3）代碼實現

（4）算法特性

?（5）算法優化

1. 提前終止（已實現）

2. 雞尾酒排序（雙向冒泡）

3. 記錄最后交換位置

?（6）實例演示

六.快速排序

（1）基本思想

（2）算法步驟

（3）代碼實現

?（4）算法特性

1. 高效的平均性能

2. 內存效率高

3. 實現靈活

最壞情況性能差

2. 不穩定排序

3. 遞歸實現的風險

（5）算法優化

1. 三數取中法選擇基準值

2. 尾遞歸優化

3. 插入排序混合優化

?（6）實例演示

示例1：基礎快速排序流程

示例2：三數取中法優化

示例3：三路快排處理重復元素

七.歸并排序

（1）基本思想

（2）算法步驟

（3）代碼實現

（4）算法特性

（5）算法優化

1. 小規模數據使用插入排序

2. 減少不必要的數組復制

3. 提前終止合并過程

（6）實例演示

分解階段

合并階段

八.常見排序表

?在數據結構中，排序是組織和處理數據的核心操作之一。它不僅是數據組織的核心手段，更是提升計算效率、優化資源利用的基礎。其應用貫穿于數據庫、操作系統、機器學習、實時系統等領域，是算法設計與系統優化的基石。

選擇適合的排序算法需綜合考慮數據規模、內存限制、穩定性需求及硬件特性。

這篇文章詳細解析了七大排序的思想、步驟及其特點。

一.直接插入排序

（1）基本思想

直接插入排序是一種簡單的排序算法，其基本思想是：將待排序的元素逐個插入到已排序序列的適當位置，直到所有元素都插入完畢。

（2）算法步驟

將第一個元素視為已排序序列
取出下一個元素，在已排序序列中從后向前掃描
如果已排序元素大于新元素，將該元素移到下一位置
重復步驟3，直到找到已排序元素小于或等于新元素的位置
將新元素插入到該位置
重復步驟2~5，直到所有元素都排序完成

（3）代碼實現

 for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > temp) {/*array[j+1]就是temp,但是1個i對應很多個j,所以i不是等于j+1;要用j+1來表示temp*/array[j + 1] = array[j];} else {//不用改變元素位置,把取出來的temp再放回去// array[j+1]=temp;break;}}/*出了j的循環,證明j這時已經小于0了,也就是-1把取出來的temp再放回去j+1的位置,也就是下標0*/array[j + 1] = temp;}

（4）算法特性

特性	說明
時間復雜度	最好O(n)，最壞和平均O(n2)
空間復雜度	O(1)（原地排序）
穩定性	穩定排序
適用場景	小規模數據或基本有序數據
優點	（1）實現簡單直觀；（2）穩定排序，不會改變相同元素的相對順序；（3）原地排序，不需要額外的存儲空間（空間復雜度O（1））；（4）對小規模或部分有序數據高效；
缺點	（1）時間復雜度高：平均O(n2); （2）對逆序數據表現最差；（3）數據移動頻繁；

（5）算法優化

二分查找優化：在已排序部分使用二分查找確定插入位置（減少比較次數）
希爾排序：是插入排序的改進版，通過分組插入提高效率

（6）示例演示

以數組?[5, 2, 4, 6, 1, 3]?為例：

初始:  [5, 2, 4, 6, 1, 3]
第1輪: [2, 5, 4, 6, 1, 3] (插入2)
第2輪: [2, 4, 5, 6, 1, 3] (插入4)
第3輪: [2, 4, 5, 6, 1, 3] (插入6)
第4輪: [1, 2, 4, 5, 6, 3] (插入1)
第5輪: [1, 2, 3, 4, 5, 6] (插入3)

直接插入排序雖然簡單，但在處理小規模或部分有序數據時效率較高，且實現簡單，常被用作其他高級排序算法的子過程。

二.希爾排序

（1）基本思想

希爾排序（Shell Sort）是插入排序的一種高效改進版本，由Donald Shell于1959年提出。其核心思想是通過分組插入排序逐步減少間隔（增量），最終實現整個數組的有序化。

希爾排序的思想是通過分組來減少增量，提前進行多次小范圍排序，使得數據有序化，最后當gap=1（最后一次排序）時，實現高效率的直接插入排序。

（2）算法步驟

選擇增量序列：確定一個遞減的增量序列（例如初始增量為數組長度的一半，后續逐步減半）。
分組插入排序：對每個增量間隔形成的子序列進行直接插入排序。
縮小增量：重復步驟2，直到增量為1，此時整個數組作為一整個序列進行最后一次插入排序（希爾排序的最后一次排序就是直接插入排序）。

（3）代碼實現

 public static void shellSort(int[] array) {int gap = array.length / 2;
/*隨著gap的遞減,分的組數也越來越少,直接組數為1,gap=1,這時進行直接插入排序*/while (gap > 0) {shell(array, gap);gap = gap / 2;}}//希爾排序內排序public static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int temp = array[i];int j = i - gap;for (; j >= 0; j = j - gap) {if (array[j] > temp) {array[j + gap] = array[j];} else {break;}}//此時j為負數,但不是-1array[j + gap] = temp;}}

希爾排序是優化版的直接插入排序，旨在提升直接插入排序的效率。

并且希爾排序的最后一次排序就是直接插入排序，希爾排序之所以效率高是因為希爾排序通過前面幾次小范圍排序使得數組逐漸有序化（直接插入排序在數據有序化的時候效率高）。

（4）算法特性

特性	說明
時間復雜度	最壞O(n2)，平均約?`O(n log n)（當希爾增量`（n/2遞減`）時）`
空間復雜度	O(1)
穩定性	不穩定排序（相同元素可能在排序時改變相對順序）
適用場景	中小規模數據排序（特別是內存受限環境）
優點	原地排序，不需要額外的存儲空間；比直接插入排序效率更高，更適合中等規模數據；靈活性強，可以通過選擇不同增量序列來優化性能。
缺點	不穩定排序，相同元素可能在排序時改變相對順序；增量依賴，性能受增量序列的選擇影響較大；理論復雜，最佳增量序列至今尚無統一結論。

希爾排序的時間復雜度分析是算法理論中的一個經典難題，其復雜度高度依賴增量序列的選擇，目前無法精確計算所有情況下的時間復雜度。?

?（5）算法優化

Sedgewick增量優化：

使用Robert Sedgewick提出的增量序列實現的希爾排序改進版本。這種增量序列通過數學優化顯著提升了希爾排序的性能，是目前已知綜合表現最優的增量序列之一。

public static void shellSortOptimized(int[] arr) {int n = arr.length;// Sedgewick增量序列（部分）int[] gaps = {1073, 281, 77, 23, 8, 1}; for (int gap : gaps) {if (gap >= n) continue;for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}
}

（6）實例演示

算法演示（以希爾增量為例）
初始數組：[12, 34, 54, 2, 3, 8, 15, 29]增量 = 4：分組：[12,3], [34,8], [54,15], [2,29]排序后：[3,8,15,2,12,34,54,29]增量 = 2：分組：[3,15,12,54], [8,2,34,29]排序后：[3,2,12,8,15,29,54,34]增量 = 1：對整個數組插入排序，最終有序。

希爾排序的時間復雜度并非固定值，而是由增量序列決定。早期資料中的?O(n log n)?是對特定場景的簡化描述，現代研究更傾向于具體分析增量序列的影響。實際開發中，選擇優化增量序列可顯著提升性能，使其在小規模數據排序中具備競爭力。

?三.選擇排序

（1）基本思想

選擇排序是一種簡單直觀的排序算法，其核心思想是每次從未排序序列中選出最小（或最大）元素，將其放到已排序序列的末尾，直到所有元素排序完成。

（2）算法步驟

初始化：整個數組視為未排序序列
尋找最小值：遍歷未排序序列，找到最小元素的位置
交換位置：將最小元素與未排序序列的第一個元素交換
縮小范圍：將已找到的最小元素歸入已排序序列
重復操作：重復步驟2~4，直到所有元素有序

（3）代碼實現

1）每次交換一個元素（最小元素）：

public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}//這時j已經遍歷完數組,交換存儲的最小值下標元素和array[i]swap(array, minIndex, i);}}//定義方法:交換數組中兩個下標對應的元素public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}

2）每次交換兩個元素（一個最大元素，一個最小元素）：

 public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] > array[maxIndex]) {maxIndex = i;} else if (array[i] < array[minIndex]) {minIndex = i;}}//走完i循環,交換元素swap(array, minIndex, left);if (maxIndex == left) {swap(array, left, right);} else {swap(array, maxIndex, right);}left++;right--;}}

（4）算法特性

特性	說明
時間復雜度	固定 O(n2)（無論數據是否有序）
空間復雜度	O(1)（原地排序）
穩定性	通常不穩定（可特殊實現為穩定）
交換次數	最多 n-1 次交換
比較次數	固定?n(n?1)22n(n?1)??次
優點	簡單直觀：邏輯清晰，易于理解和實現交換次數少：每輪僅需一次交換（相比冒泡排序更高效）內存友好：原地排序，無需額外空間適用小數據：數據量較小時實際性能尚可
缺點	效率低下：時間復雜度始終為 O(n2)，不適合大規模數據無適應性：無論數據初始狀態如何，比較次數固定不穩定排序：默認實現會改變相同元素的相對順序

（5）算法優化

雙向選擇排序（雞尾酒選擇排序）
- 同時尋找最小值和最大值，減少循環次數
- 優化后比較次數減少約50%
堆排序優化
- 使用堆結構優化選擇過程，時間復雜度降為 O(n log n)
- 實際上堆排序就是選擇排序的高級變種

（6）實例演示

初始狀態： [5, 2, 4, 6, 1, 3]
第1輪：找到最小值1 → 交換位置 → [1, 2, 4, 6, 5, 3]
第2輪：找到次小值2 → 無需交換 → [1, 2, 4, 6, 5, 3]
第3輪：找到最小值3 → 交換位置 → [1, 2, 3, 6, 5, 4]
第4輪：找到最小值4 → 交換位置 → [1, 2, 3, 4, 5, 6]
第5輪：數組已有序，排序完成

?四.堆排序

（1）基本思想

堆排序是一種基于完全二叉樹結構的高效排序算法，利用堆的性質進行排序。其核心思想是：

構建最大堆（或最小堆），將無序數組轉換為堆結構
逐步取出堆頂元素（最大值或最小值），與堆末尾元素交換并調整堆
重復調整直到堆大小為1，完成排序

（2）算法步驟

構建最大堆
從最后一個非葉子節點開始，自底向上調整堆結構
堆排序階段
- 交換堆頂與末尾元素（最大值歸位）
- 縮小堆范圍并重新調整堆
- 重復直到堆大小為1

（3）代碼實現

    public static void heapSort(int[] array) {createHeap(array);for (int end = array.length - 1; end >= 0; end--) {//交換堆頂元素和最后一個元素swap(array, 0, end);//調整剩余元素為大根堆siftDown(array, 0, end);}}//定義方法:創建1個大根堆public static void createHeap(int[] array) {//確定最后1棵子樹的位置for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {//siftDown是將1棵子樹調整為大根堆,所以要使parent--,調整所有的子樹至大根堆siftDown(array, parent, array.length);}}/*定義方法:向下調整;將1個堆調整為大根堆在數組array中向下調整到length位置*/public static void siftDown(int[] array, int parent, int length) {int child = 2 * parent + 1;while (child < length) {//拿到左右孩子最大值if (child < array.length - 1 && array[child] >= array[child + 1]) {child++;}//如果孩子最大值大于父親節點,交換兩個節點的值if (array[child] > array[parent]) {swap(array, child, parent);//繼續向下調整parent = child;child = 2 * parent + 1;} else {break;}}}

?（4）算法特性

特性	說明
時間復雜度	O(n log n)
空間復雜度	O(1)（原地排序）
穩定性	不穩定
優點	時間復雜度穩定：始終保證O(n log n)的性能內存高效：原地排序，無需額外存儲空間適合大數據：處理海量數據時不會出現快速排序的最壞情況優先級隊列基礎：堆結構的重要應用場景
缺點	不穩定排序：相同值元素的相對位置可能改變緩存不友好：跳躍式訪問內存，可能影響實際性能常數項較大：實際運行速度通常略慢于快速排序

（5）算法優化

非遞歸實現
將調整方法改為迭代實現，避免遞歸調用開銷
多叉堆優化
使用三叉堆或四叉堆（適用于現代CPU緩存特性）
并行建堆
對大規模數據可采用多線程并行調整子樹

（6）實例演示

（以數組[12, 11, 13, 5, 6, 7]為例）

1）建堆過程：

初始數組： [12, 11, 13, 5, 6, 7]
轉換為完全二叉樹：12/  \11   13/ \   /5  6 7調整非葉子節點（索引2→1→0）：
最終最大堆： [13, 11, 12, 5, 6, 7]
對應二叉樹：13/  \11   12/ \   /5  6 7

?2）排序階段

第1次交換：13?7 → [7, 11, 12, 5, 6, 13]
調整堆：   [12, 11, 7, 5, 6, 13]第2次交換：12?6 → [6, 11, 7, 5, 12, 13]
調整堆：   [11, 6, 7, 5, 12, 13]...（重復過程）...
最終結果： [5, 6, 7, 11, 12, 13]

五.冒泡排序

（1）基本思想

冒泡排序是一種簡單的交換排序算法，其核心思想是通過相鄰元素的比較和交換，將較大的元素逐步“冒泡”到數組末尾。每一輪遍歷都會確定一個當前未排序部分的最大值。

（2）算法步驟

外層循環：控制排序輪數（共需?n-1?輪，n?為數組長度）
內層循環：遍歷未排序部分，比較相鄰元素
元素交換：若當前元素 > 后一個元素，則交換位置
優化判斷：若某輪無交換發生，提前終止排序

（3）代碼實現

public class BubbleSort {public static void bubbleSort(int[] arr) {if (arr == null || arr.length <= 1) return;int n = arr.length;boolean swapped; // 優化標志for (int i = 0; i < n - 1; i++) {swapped = false;// 每輪確定一個最大值，遍歷范圍逐漸縮小for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交換元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 若本輪無交換，說明已有序，提前結束if (!swapped) break;}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11};bubbleSort(arr);System.out.println(Arrays.toString(arr)); // 輸出 [11, 12, 22, 25, 34, 64]}
}

（4）算法特性

特性	說明
時間復雜度	最好O(n)，最壞和平均O(n2)
空間復雜度	O(1)（原地排序）
穩定性	穩定排序
交換次數	最多?n(n?1)22n(n?1)??次
優點	實現簡單：代碼邏輯直觀，適合教學和小規模數據穩定性：相等元素不會交換，保持原有順序空間效率：無需額外內存空間適應性：對部分有序數據效率較高（通過優化標志）
缺點	效率低下：大規模數據排序速度顯著下降冗余比較：即便數據已有序仍需多輪遍歷（未優化版本）

?（5）算法優化

1. 提前終止（已實現）

通過swapped標志檢測是否發生交換
最佳情況時間復雜度優化至O(n)（完全有序數組）

2. 雞尾酒排序（雙向冒泡）

交替進行正向和反向遍歷
對包含大量無序小元素的數組更高效

雞尾酒排序代碼實例：?

public static void cocktailSort(int[] arr) {int left = 0;int right = arr.length - 1;boolean swapped;while (left < right) {// 正向遍歷swapped = false;for (int i = left; i < right; i++) {if (arr[i] > arr[i+1]) {swap(arr, i, i+1);swapped = true;}}if (!swapped) break;right--;// 反向遍歷swapped = false;for (int i = right; i > left; i--) {if (arr[i] < arr[i-1]) {swap(arr, i, i-1);swapped = true;}}if (!swapped) break;left++;}
}

3. 記錄最后交換位置

記錄每輪最后一次交換的位置，減少無效比較

int lastSwapIndex = 0;
int sortBorder = arr.length - 1;for (int i = 0; i < arr.length - 1; i++) {boolean swapped = false;for (int j = 0; j < sortBorder; j++) {if (arr[j] > arr[j+1]) {swap(arr, j, j+1);swapped = true;lastSwapIndex = j;}}sortBorder = lastSwapIndex;if (!swapped) break;
}

?（6）實例演示

（以數組[5, 2, 4, 6, 1, 3]為例）

初始狀態： [5, 2, 4, 6, 1, 3]第1輪遍歷：
2 5 4 6 1 3 → 2 4 5 6 1 3 → 2 4 5 1 6 3 → 2 4 5 1 3 6
確定最大值6歸位第2輪遍歷：
2 4 5 1 3 → 2 4 1 5 3 → 2 4 1 3 5
確定次大值5歸位第3輪遍歷：
2 4 1 3 → 2 1 4 3 → 2 1 3 4
確定4歸位第4輪遍歷：
2 1 3 → 1 2 3
確定3歸位（優化：此時已有序，提前結束）

六.快速排序

（1）基本思想

快速排序是一種高效的分治算法，核心思想是通過基準值（pivot）劃分數組，將小于基準值的元素放在左側，大于基準值的元素放在右側，然后遞歸處理左右子數組，直到整個數組有序。

（2）算法步驟

選擇基準值（Pivot）：從數組中選取一個元素作為基準
分區操作（Partition）：重新排列數組，使小于基準值的元素在左，大于基準值的在右
遞歸排序：對左右兩個子數組遞歸執行上述步驟

（3）代碼實現

public class QuickSort {public static void quickSort(int[] arr) {if (arr == null || arr.length <= 1) return;sort(arr, 0, arr.length - 1);}private static void sort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);sort(arr, low, pivotIndex - 1);  // 遞歸處理左子數組sort(arr, pivotIndex + 1, high); // 遞歸處理右子數組}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];  // 選擇最后一個元素為基準值int i = low - 1;        // 指向比基準值小的最后一個元素for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high); // 將基準值放到正確位置return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr);System.out.println(Arrays.toString(arr)); // 輸出 [1, 5, 7, 8, 9, 10]}
}

?（4）算法特性

特性	說明
平均時間復雜度	O(n log n)
最壞時間復雜度	O(n2)（可通過優化避免）
空間復雜度	O(log n)（遞歸調用棧）
穩定性	不穩定
最佳適用場景	大規模隨機數據
優點	1. 高效的平均性能時間復雜度：平均情況O(n log n)，實際應用中效率通常高于其他O(n log n)算法（如歸并排序）比較次數少：相比歸并排序，快速排序的比較次數通常更少 2. 內存效率高原地排序：只需O(log n)的棧空間（遞歸調用），不需要額外存儲空間緩存友好：順序訪問內存，能有效利用CPU緩存 3. 實現靈活可通過多種方式選擇基準值（pivot）可優化為三路快排處理重復元素可與非遞歸實現結合
缺點	最壞情況性能差最壞時間復雜度：O(n2)（當輸入已排序且基準選擇不當時）解決方案：隨機化基準選擇或三數取中法 2. 不穩定排序相同元素的相對位置可能改變示例：排序`[3①, 2, 3②]`可能得到`[2, 3②, 3①]` 3. 遞歸實現的風險深度遞歸可能導致棧溢出解決方案：尾遞歸優化或改為迭代實現

（5）算法優化

1. 三數取中法選擇基準值

避免最壞情況（已排序數組導致O(n2)）

private static int selectPivot(int[] arr, int low, int high) {int mid = low + (high - low)/2;// 比較low/mid/high三個位置的元素if (arr[low] > arr[mid]) swap(arr, low, mid);if (arr[low] > arr[high]) swap(arr, low, high);if (arr[mid] > arr[high]) swap(arr, mid, high);return mid; // 返回中間值索引
}

2. 尾遞歸優化

減少遞歸調用棧深度

private static void sortOptimized(int[] arr, int low, int high) {while (low < high) {int pivotIndex = partition(arr, low, high);if (pivotIndex - low < high - pivotIndex) {sortOptimized(arr, low, pivotIndex - 1);low = pivotIndex + 1;} else {sortOptimized(arr, pivotIndex + 1, high);high = pivotIndex - 1;}}
}

3. 插入排序混合優化

對小規模子數組（如長度≤15）改用插入排序

private static final int INSERTION_THRESHOLD = 15;private static void sort(int[] arr, int low, int high) {if (high - low <= INSERTION_THRESHOLD) {insertionSort(arr, low, high);return;}// ...原快速排序邏輯
}

?（6）實例演示

示例1：基礎快速排序流程

輸入數組：[10, 80, 30, 90, 40, 50, 70]

步驟演示：

選擇基準值：70（末尾元素）
分區過程：
- 10 < 70 → 保留
- 80 > 70 → 跳過
- 30 < 70 → 與80交換 →?[10, 30, 80, 90, 40, 50, 70]
- 90 > 70 → 跳過
- 40 < 70 → 與80交換 →?[10, 30, 40, 90, 80, 50, 70]
- 50 < 70 → 與90交換 →?[10, 30, 40, 50, 80, 90, 70]
最終交換基準值 →?[10, 30, 40, 50, 70, 90, 80]
遞歸處理左右子數組

示例2：三數取中法優化

輸入數組：[1, 2, 3, 4, 5, 6, 7]（已排序數組）

優化步驟：

選擇low=1, mid=4, high=7
三數排序后取中值：4
分區后得到平衡劃分，避免O(n2)最壞情況

示例3：三路快排處理重復元素

輸入數組：[3, 1, 3, 2, 3, 3, 4]

分區過程：

初始：lt=0, gt=6, i=1, pivot=3
[3, 1, 3, 2, 3, 3, 4]步驟1：arr[1]=1 < 3 → 交換lt(0)和i(1)
[1, 3, 3, 2, 3, 3, 4] (lt=1, i=2)步驟2：arr[2]=3 == 3 → i++
(lt=1, i=3)步驟3：arr[3]=2 < 3 → 交換lt(1)和i(3)
[1, 2, 3, 3, 3, 3, 4] (lt=2, i=4)...最終得到：
<3的部分：[1, 2]
=3的部分：[3, 3, 3, 3]
>3的部分：[4]

七.歸并排序

（1）基本思想

歸并排序（Merge Sort）是一種經典的分治算法，由約翰?馮?諾伊曼在 1945 年提出。它的基本思想是將一個大問題分解為多個小問題，分別解決這些小問題，最后將小問題的解合并起來得到大問題的解。

歸并排序采用分治策略，具體分為兩個階段：

分解（Divide）：將待排序的數組從中間分成兩個子數組，然后遞歸地對這兩個子數組繼續進行分解，直到每個子數組只有一個元素（因為單個元素的數組本身就是有序的）。
合并（Merge）：將兩個有序的子數組合并成一個有序的數組。合并過程中，比較兩個子數組的元素，將較小的元素依次放入新的數組中，直到兩個子數組的所有元素都被放入新數組。

（2）算法步驟

分解階段：
- 找到數組的中間位置，將數組分成左右兩部分。
- 遞歸地對左右兩部分進行分解，直到每個子數組只有一個元素。
合并階段：
- 創建一個臨時數組，用于存放合并后的結果。
- 比較左右兩個子數組的元素，將較小的元素依次放入臨時數組中。
- 將臨時數組中的元素復制回原數組。

（3）代碼實現

 private static void mergechild(int[] array, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;mergechild(array, left, mid);mergechild(array, mid + 1, right);merge(array,left,mid,right);}
//定義方法:合并兩個子數組private static void merge(int[] array, int left, int mid, int right) {int[] tempArray = new int[right - left + 1];int k = 0;//臨時數組tempArray的下標int start1 = left;int start2 = mid + 1;int end1 = mid;int end2 = right;//兩個子數組中都有數據while (start1 <= end1 && start2 <= end2) {if (array[start1] > array[start2]) {tempArray[k] = array[start2];k++;start2++;} else if (array[start1] <= array[start2]) {tempArray[k] = array[start1];k++;start1++;}}//1個子數組中沒有數據了,跳出while循環while (start1 <= end1) {tempArray[k] = array[start1];k++;start1++;}while (start2 <= end2) {tempArray[k] = array[start2];k++;start2++;}//將tempArray中的元素復制回原數組for (int i = 0; i < tempArray.length; i++) {array[i+left]=tempArray[i];}}

（4）算法特性

特性	說明
平均時間復雜度	?O(nlogn)
空間復雜度	?O(n)
穩定性	穩定
最佳適用場景	處理大規模數據
優點	穩定性：歸并排序是一種穩定的排序算法，即相等元素的相對順序在排序前后不會改變。時間復雜度穩定：無論輸入數據的分布如何，歸并排序的時間復雜度都是?O(nlogn)。
缺點	空間復雜度較高：需要額外的?O(n)?空間來存儲臨時數組。常數因子較大：由于需要頻繁地進行數組的復制和合并操作，歸并排序的常數因子相對較大，在處理小規模數據時效率不如一些簡單的排序算法（如插入排序）。

（5）算法優化

1. 小規模數據使用插入排序

對于小規模的數據，插入排序的常數時間開銷相對較小，性能可能比歸并排序更好。因此當子數組規模較小時，可以采用插入排序來處理，減少遞歸調用帶來的開銷。

2. 減少不必要的數組復制

在歸并過程中，頻繁地創建和復制臨時數組會帶來一定的性能開銷。可以通過交替使用原數組和臨時數組來減少這種開銷。

3. 提前終止合并過程

在合并兩個有序子數組時，如果發現其中一個子數組的所有元素都已經小于另一個子數組的所有元素，就可以提前終止合并過程。

（6）實例演示

假設我們有一個待排序的數組?[38, 27, 43, 3, 9, 82, 10]

分解階段

首先將原數組從中間分成兩部分：[38, 27, 43, 3]?和?[9, 82, 10]。
對這兩個子數組繼續分解，[38, 27, 43, 3]?分成?[38, 27]?和?[43, 3]；[9, 82, 10]?分成?[9, 82]?和?[10]。
繼續分解，[38, 27]?分成?[38]?和?[27]；[43, 3]?分成?[43]?和?[3]；[9, 82]?分成?[9]?和?[82]。此時所有子數組都只有一個元素，分解結束。

合并階段

合并?[38]?和?[27]?得到?[27, 38]；合并?[43]?和?[3]?得到?[3, 43]；合并?[9]?和?[82]?得到?[9, 82]。
合并?[27, 38]?和?[3, 43]?得到?[3, 27, 38, 43]；[9, 82]?和?[10]?合并得到?[9, 10, 82]。
最后合并?[3, 27, 38, 43]?和?[9, 10, 82]?得到最終的有序數組?[3, 9, 10, 27, 38, 43, 82]。

八.常見排序表

排序算法	時間復雜度（最好）	時間復雜度（平均）	時間復雜度（最壞）	空間復雜度	穩定性	備注
冒泡排序	O(n)	O(n2)	O(n2)	O(1)	穩定	簡單但效率低
選擇排序	O(n2)	O(n2)	O(n2)	O(1)	不穩定	交換次數最少
插入排序	O(n)	O(n2)	O(n2)	O(1)	穩定	對小規模數據高效
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	不穩定	實際應用中最快（優化后）
歸并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	穩定	穩定且適合外部排序
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不穩定	適合大規模數據
希爾排序	O(n log n)	O(n log2 n)	O(n2)	O(1)	不穩定	插入排序的改進版