1. 寫在前面：為什么要掌握這 3 種排序？
日常開發(fā)中，從 “給 100 條用戶考勤數(shù)據(jù)按時間排序” 到 “給 1 萬條訂單按金額排序”，排序是高頻需求。而冒泡排序、快速排序、歸并排序覆蓋了 “小規(guī)模數(shù)據(jù)”“大規(guī)模數(shù)據(jù)”“穩(wěn)定排序” 三大核心場景，學會它們，基本能解決 80% 的排序問題。
本文全程用 Java 實現(xiàn)，每個算法包含 “核心思想→完整代碼→關鍵細節(jié)解釋→測試驗證”，代碼注釋清晰，新手也能輕松理解。
2. 冒泡排序：“水泡上冒” 的簡單排序
核心思想
像水里的氣泡往上冒一樣，每次對比相鄰的兩個元素，把較大的元素 “往后推”。若有n個元素，需進行n-1輪對比（最后 1 個元素無需對比）；每輪結束后，最大的元素會 “浮” 到當前未排序部分的末尾，后續(xù)輪次無需再處理它。
Java 完整代碼實現(xiàn)
public class SortDemo {
// 冒泡排序方法
public static void bubbleSort(int\[] arr) {
// 1. 獲取數(shù)組長度（n個元素需n-1輪對比）
int n = arr.length;
// 2. 外層循環(huán)控制“輪次”
for (int i = 0; i < n - 1; i++) {
// 優(yōu)化點：標記本輪是否發(fā)生交換，無交換說明數(shù)組已有序，直接退出
boolean swapped = false;
// 3. 內層循環(huán)控制“每輪對比次數(shù)”：每輪后最大元素已排好，對比次數(shù)遞減
// 第1輪對比n-1次，第2輪n-2次...第i輪n-1-i次
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;
}
}
// 若本輪無交換，數(shù)組已有序，無需繼續(xù)循環(huán)
if (!swapped) {
break;
}
}
}
// 測試冒泡排序
public static void main(String\[] args) {
// 測試數(shù)組：對應“5個元素排序”場景
int\[] testArr = {5, 3, 8, 1, 2};
System.out.print("冒泡排序前：");
printArray(testArr);
bubbleSort(testArr);
System.out.print("冒泡排序后：");
printArray(testArr); // 輸出：\[1, 2, 3, 5, 8]
}
// 輔助方法：打印數(shù)組（方便查看結果）
private static void printArray(int\[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr\[i] + (i == arr.length - 1 ? "\n" : ", "));
}
}
}
關鍵細節(jié)解釋
輪次控制：外層循環(huán)
for (int i = 0; i < n - 1; i++)，對應 “n個元素需n-1輪”，比如 5 個元素只需 4 輪；對比次數(shù)遞減：內層循環(huán)
for (int j = 0; j < n - 1 - i; j++)，每輪后最大元素已排好，后續(xù)輪次無需再對比，避免無效操作；效率優(yōu)化：
swapped標志若為false，說明數(shù)組已完全有序（比如輸入數(shù)組本身就是有序的），直接退出循環(huán)，減少不必要的計算。
適用場景
數(shù)據(jù)量?。?00 個以內），比如幾十條員工信息排序。優(yōu)點是邏輯簡單、代碼易寫，適合新手入門；缺點是效率低，數(shù)據(jù)量大時會明顯變慢。
3. 快速排序：“分而治之” 的效率之王
核心思想
通過 “基準值劃分” 將數(shù)組拆成兩部分：比基準值小的元素放左邊，比基準值大的放右邊；然后對左右兩部分遞歸執(zhí)行同樣的操作，直到每個子數(shù)組只有 1 個元素（天然有序）。
數(shù)據(jù)量越大優(yōu)勢越明顯，比如 1000 個元素，每次拆成兩半，僅需 10 次左右就能排好（2^10 = 1024），是開發(fā)中最常用的排序算法。
關鍵步驟（Hoare 法：左右指針法）
選數(shù)組左邊界元素為基準值（也可選中間 / 右邊界，根據(jù)場景調整）；
左指針從左往右找 “比基準值大的元素”，右指針從右往左找 “比基準值小的元素”；
找到后交換左右指針指向的元素，重復步驟 2，直到左指針超過右指針；
交換基準值和右指針指向的元素，此時基準值左邊全是小數(shù)，右邊全是大數(shù)（完成 “劃分”）；
遞歸排序基準值左邊和右邊的子數(shù)組。
Java 完整代碼實現(xiàn)
public class SortDemo {
// 快速排序入口：對外提供統(tǒng)一調用方法，無需傳入左右邊界
public static void quickSort(int\[] arr) {
if (arr == null || arr.length <= 1) {
return; // 數(shù)組為空或只有1個元素，無需排序
}
// 調用重載方法，初始左邊界0，右邊界數(shù)組最后一個索引
quickSort(arr, 0, arr.length - 1);
}
// 快速排序重載方法：接收數(shù)組、左邊界、右邊界
private static void quickSort(int\[] arr, int left, int right) {
// 遞歸終止條件：左邊界 >= 右邊界，說明子數(shù)組只有1個元素（有序）
if (left >= right) {
return;
}
// 1. 劃分：找到基準值的最終位置，返回基準值索引
int pivotIndex = partition(arr, left, right);
// 2. 遞歸排序基準值左邊的子數(shù)組（左邊界到基準值左邊）
quickSort(arr, left, pivotIndex - 1);
// 3. 遞歸排序基準值右邊的子數(shù)組（基準值右邊到右邊界）
quickSort(arr, pivotIndex + 1, right);
}
// 輔助方法：劃分數(shù)組，返回基準值最終索引（核心步驟）
private static int partition(int\[] arr, int left, int right) {
// 1. 選左邊界元素為基準值
int pivot = arr\[left];
// 2. 初始化左右指針：左指針從左邊界+1開始（基準值已占左邊界）
int i = left + 1;
int j = right;
while (true) {
// 左指針：找比基準值大的元素（沒找到就繼續(xù)右移）
while (i <= j && arr\[i] <= pivot) {
i++;
}
// 右指針：找比基準值小的元素（沒找到就繼續(xù)左移）
while (i <= j && arr\[j] >= pivot) {
j--;
}
// 左指針超過右指針，說明所有元素已劃分完成，退出循環(huán)
if (i > j) {
break;
}
// 交換左右指針指向的元素：讓小數(shù)到左邊，大數(shù)到右邊
int temp = arr\[i];
arr\[i] = arr\[j];
arr\[j] = temp;
}
// 3. 交換基準值和右指針指向的元素：讓基準值到最終位置（左小右大）
int temp = arr\[left];
arr\[left] = arr\[j];
arr\[j] = temp;
// 返回基準值索引，用于后續(xù)遞歸劃分
return j;
}
// 測試快速排序
public static void main(String\[] args) {
// 測試數(shù)組：7個元素，模擬“分而治之”場景
int\[] testArr = {7, 3, 9, 2, 8, 1, 5};
System.out.print("快速排序前：");
printArray(testArr);
quickSort(testArr);
System.out.print("快速排序后：");
printArray(testArr); // 輸出：\[1, 2, 3, 5, 7, 8, 9]
}
// 輔助方法：打印數(shù)組
private static void printArray(int\[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr\[i] + (i == arr.length - 1 ? "\n" : ", "));
}
}
}
關鍵細節(jié)解釋
基準值劃分：
partition方法是核心，通過左右指針找到基準值的最終位置，確保 “左小右大”；遞歸邊界：
left >= right時終止遞歸，避免子數(shù)組越界；基準值選擇優(yōu)化：若輸入數(shù)組本身有序（比如
[1,2,3,4,5]），選左邊界為基準值會導致效率下降，此時可改為選 “中間值”（int pivot = arr[(left + right) / 2]），避免極端情況。
適用場景
數(shù)據(jù)量大（1000+），比如 1 萬條訂單按金額排序、10 萬條商品按銷量排序。優(yōu)點是效率極高，是開發(fā)中的 “首選排序”；缺點是 “不穩(wěn)定排序”（若兩個元素值相同，排序后可能打亂原始相對順序），若需保留原始順序（如 “金額相同按下單時間排序”），需謹慎使用。
4. 歸并排序：“先拆再合” 的穩(wěn)定之選
核心思想
采用 “分治法” 的 “先拆后合” 邏輯：
拆分：用 “二分法” 把數(shù)組拆成左右兩個子數(shù)組，直到每個子數(shù)組只有 1 個元素（天然有序）；
合并：寫一個
merge方法，將兩個有序子數(shù)組合并成一個有序數(shù)組；遞歸：遞歸拆分左、右子數(shù)組，再遞歸合并拆分后的子數(shù)組，直到合并成完整的有序數(shù)組。
歸并排序是 “穩(wěn)定排序”，能保留元素的原始相對順序，適合對排序穩(wěn)定性有要求的場景。
Java 完整代碼實現(xiàn)
import java.util.Arrays;
public class SortDemo {
// 歸并排序入口
public static void mergeSort(int\[] arr) {
// 數(shù)組為空或只有1個元素，無需排序
if (arr == null || arr.length <= 1) {
return;
}
// 調用重載方法，傳入原始數(shù)組和臨時數(shù)組（避免合并時頻繁創(chuàng)建數(shù)組，優(yōu)化內存）
mergeSort(arr, new int\[arr.length], 0, arr.length - 1);
}
// 歸并排序重載方法：接收數(shù)組、臨時數(shù)組、左邊界、右邊界
private static void mergeSort(int\[] arr, int\[] temp, int left, int right) {
// 遞歸終止條件：左邊界 >= 右邊界，子數(shù)組只有1個元素
if (left >= right) {
return;
}
// 1. 拆分：找數(shù)組中間索引，將數(shù)組拆成左右兩部分
int mid = left + (right - left) / 2; // 等價于(left+right)/2，避免整數(shù)溢出
// 遞歸拆分左子數(shù)組（左邊界到中間）
mergeSort(arr, temp, left, mid);
// 遞歸拆分右子數(shù)組（中間+1到右邊界）
mergeSort(arr, temp, mid + 1, right);
// 2. 合并：將左右兩個有序子數(shù)組合并成一個有序數(shù)組
merge(arr, temp, left, mid, right);
}
// 輔助方法：合并兩個有序子數(shù)組（核心步驟）
private static void merge(int\[] arr, int\[] temp, int left, int mid, int right) {
// 1. 將當前需合并的元素復制到臨時數(shù)組（避免合并時覆蓋原數(shù)組數(shù)據(jù)）
for (int i = left; i <= right; i++) {
temp\[i] = arr\[i];
}
// 2. 初始化指針：i指向左子數(shù)組起始（left），j指向右子數(shù)組起始（mid+1）
int i = left;
int j = mid + 1;
// k指向原數(shù)組的合并位置（從left開始）
int k = left;
// 3. 對比左右子數(shù)組元素，按從小到大放入原數(shù)組
while (i <= mid && j <= right) {
if (temp\[i] <= temp\[j]) {
// 左子數(shù)組元素小，放入原數(shù)組
arr\[k] = temp\[i];
i++;
} else {
// 右子數(shù)組元素小，放入原數(shù)組
arr\[k] = temp\[j];
j++;
}
k++;
}
// 4. 處理左子數(shù)組剩余元素（若右子數(shù)組已遍歷完）
while (i <= mid) {
arr\[k] = temp\[i];
i++;
k++;
}
// 右子數(shù)組剩余元素無需處理：因為temp\[j..right]已和arr\[j..right]一致
}
// 測試歸并排序
public static void main(String\[] args) {
// 測試數(shù)組：8個元素，模擬“先拆再合”場景
int\[] testArr = {6, 4, 9, 5, 7, 2, 8, 1};
System.out.print("歸并排序前：");
printArray(testArr);
mergeSort(testArr);
System.out.print("歸并排序后：");
printArray(testArr); // 輸出：\[1, 2, 4, 5, 6, 7, 8, 9]
}
// 輔助方法：打印數(shù)組
private static void printArray(int\[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr\[i] + (i == arr.length - 1 ? "\n" : ", "));
}
}
}
關鍵細節(jié)解釋
拆分邏輯：
int mid = left + (right - left) / 2，避免(left + right)導致的整數(shù)溢出（比如left=1e9、right=1e9時，left+right會超過int最大值）；臨時數(shù)組優(yōu)化：
temp數(shù)組在入口方法創(chuàng)建一次，避免合并時頻繁創(chuàng)建數(shù)組，減少內存開銷；合并步驟：先將元素復制到臨時數(shù)組，再對比合并，避免原數(shù)組數(shù)據(jù)被覆蓋；左子數(shù)組剩余元素需手動處理，右子數(shù)組無需處理（因臨時數(shù)組和原數(shù)組對應位置一致）。
適用場景
需 “穩(wěn)定排序” 的場景（如 “按成績排序，成績相同保留入學順序”），或數(shù)據(jù)量大且要求穩(wěn)定的情況。優(yōu)點是排序穩(wěn)定、效率高；缺點是需要額外的臨時數(shù)組存儲數(shù)據(jù)，內存開銷略大。
5. 完整代碼與運行結果
將三種排序算法整合到一個類中，可直接運行驗證：
import java.util.Arrays;
public class AllSortDemo {
// ---------------------- 冒泡排序 ----------------------
public static void bubbleSort(int\[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean 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 quickSort(int\[] arr) {
if (arr == null || arr.length <= 1) return;
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int\[] arr, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
private static int partition(int\[] arr, int left, int right) {
int pivot = arr\[left];
int i = left + 1, j = right;
while (true) {
while (i <= j && arr\[i] <= pivot) i++;
while (i <= j && arr\[j] >= pivot) j--;
if (i > j) break;
int temp = arr\[i];
arr\[i] = arr\[j];
arr\[j] = temp;
}
int temp = arr\[left];
arr\[left] = arr\[j];
arr\[j] = temp;
return j;
}
// ---------------------- 歸并排序 ----------------------
public static void mergeSort(int\[] arr) {
if (arr == null || arr.length <= 1) return;
mergeSort(arr, new int\[arr.length], 0, arr.length - 1);
}
private static void mergeSort(int\[] arr, int\[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
private static void merge(int\[] arr, int\[] temp, int left, int mid, int right) {
System.arraycopy(arr, left, temp, left, right - left + 1); // 替代手動循環(huán)復制
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
arr\[k++] = temp\[i] <= temp\[j] ? temp\[i++] : temp\[j++];
}
while (i <= mid) arr\[k++] = temp\[i++];
}
// ---------------------- 輔助與測試 ----------------------
private static void printArray(int\[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr\[i] + (i == arr.length - 1 ? "\n" : ", "));
}
}
public static void main(String\[] args) {
// 測試冒泡排序
int\[] bubbleArr = {5, 3, 8, 1, 2};
System.out.println("=== 冒泡排序 ===");
System.out.print("排序前：");
printArray(bubbleArr);
bubbleSort(bubbleArr);
System.out.print("排序后：");
printArray(bubbleArr);
// 測試快速排序
int\[] quickArr = {7, 3, 9, 2, 8, 1, 5};
System.out.println("\n=== 快速排序 ===");
System.out.print("排序前：");
printArray(quickArr);
quickSort(quickArr);
System.out.print("排序后：");
printArray(quickArr);
// 測試歸并排序
int\[] mergeArr = {6, 4, 9, 5, 7, 2, 8, 1};
System.out.println("\n=== 歸并排序 ===");
System.out.print("排序前：");
printArray(mergeArr);
mergeSort(mergeArr);
System.out.print("排序后：");
printArray(mergeArr);
}
}
運行結果
\=== 冒泡排序 ===
排序前：5, 3, 8, 1, 2
排序后：1, 2, 3, 5, 8
\=== 快速排序 ===
排序前：7, 3, 9, 2, 8, 1, 5
排序后：1, 2, 3, 5, 7, 8, 9
\=== 歸并排序 ===
排序前：6, 4, 9, 5, 7, 2, 8, 1
排序后：1, 2, 4, 5, 6, 7, 8, 9
6. 總結：如何選擇排序算法？
| 算法 | 核心優(yōu)勢 | 適用場景 | 注意事項 |
|---|---|---|---|
| 冒泡排序 | 邏輯簡單、代碼易寫 | 數(shù)據(jù)量小（100 個以內） | 效率低，不適合大數(shù)據(jù) |
| 快速排序 | 效率極高、性能最優(yōu) | 數(shù)據(jù)量大（1000+，無穩(wěn)定需求） | 不穩(wěn)定排序，需避免極端有序數(shù)組 |
| 歸并排序 | 穩(wěn)定排序、效率高 | 數(shù)據(jù)量大（需穩(wěn)定排序） | 需額外內存存儲臨時數(shù)組 |
記住這個選擇邏輯：小數(shù)據(jù)用冒泡，大數(shù)據(jù)無穩(wěn)定需求用快速，大數(shù)據(jù)有穩(wěn)定需求用歸并 —— 搞定開發(fā)中大部分排序場景，就這么簡單！
