目錄

十大排序算法分類?編輯

冒泡排序

算法步驟：

?動圖演示：

性能分析：

代碼實現（Java）：

快速排序（挖坑法）

算法步驟：

動圖演示：

性能分析：

代碼實現（Java）：

---

十大排序算法分類

本篇分享十大排序算法中的 需要進行交換操作的冒泡排序與快速排序?, 其余算法也有介紹噢（努力趕進度中，后續會添加上）
?

冒泡排序

冒泡排序是一種非常直觀的排序算法，遍歷數組，每次比較兩個元素，如果后者比前者小則交換位置?，重復的進行直至沒有再需要交換，說明該數組排序完成。冒泡排序的 名字由來是因為越小的元素會經過交換慢慢"浮"到數組的頂端。

算法步驟：

核心邏輯

• 外層循環控制輪數，共進行?n-1?輪遍歷，n?為數組長度。
• 每輪內層循環比較相鄰元素?arr[j]?和?arr[j+1]，若前者較大則交換。
• 每輪結束后，當前未排序部分的最大值會“冒泡”到正確位置（數組末尾）。

優化方法

• 提前終止：引入boolean變量，如果在某輪內循環未發生交換，說明數組有序，可直接結束排序
• ?減少遍歷范圍：每輪外層循環后，數組末尾已有序，內層循環無需再比較已排序部分。

終止條件

• ?外層循環完成n?- 1次遍歷，或boolean = false

?動圖演示：

性能分析：

時間復雜度：

• ?最好情況：數組已經有序，此時只需要遍歷一次，時間復雜度 O(n)
• ?最壞情況：數組完全倒序，此時需要遍歷n - 1次，每次遍歷都需要進行n - i 次 比較可能的交換（i為當前遍歷次數），因此時間復雜度為O(n^2)
• ? 平均情況：時間復雜度為O(n^2)? ? ?

空間復雜度：

• 僅需常數級額外空間 因此空間復雜度為O(1)

穩定性：

• 穩定排序（相等元素不會交換位置）

代碼實現（Java）：

/*** 冒泡排序算法實現（升序排序）* @param arr 待排序的整型數組*/
public void bubbleSort(int[] arr) {// 獲取數組長度int n = arr.length;// 布爾變量用于    boolean swapped;// 外層循環：控制排序輪數（最多需要 n-1 輪）for (int i = 0; i < n - 1; i++) {// 每輪開始前初始化交換標志為 falseswapped = false;// 內層循環：比較相鄰元素并交換// 每輪結束后，最大的元素會"冒泡"到數組末尾，所以比較范圍逐漸縮小for (int j = 0; j < n - i - 1; 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;}}
}

快速排序（挖坑法）

快速排序核心就是選擇一個基準值(就是一個作參照的數)，然后將數組分成左右兩部分，左邊是比基準值小的元素。右邊是比基準值大的元素。 然后遞歸地對左右兩部分繼續進行這個過程，最終整個數組有序

快速排序是通過一次分區就定位一個元素的最終位置，并遞歸處理兩側子數組

算法步驟：

? ?核心邏輯

1. 首先設定一個基準值 （通常是第一個數字/最后一個數字），通過該基準值將數組分成左右兩部分。

2. 分區(partition)：將所有小于基準值的元素移到基準值左邊，大于的移到右邊

3. 遞歸排序：對左右兩個子數組遞歸進行上述過程

4. 概括來說為 挖坑填數 + 分治法

?優化方法

• 采用三數取中法（取左、中、右三個位置的中間值作為基準值）
• 如果分區后子數組長度小于閾值（如 10）時，直接改用插入排序，減少了遞歸的開銷

? 終止條件

• 當left >= right (起始索引大于等于結束索引，子數據長度 <= 1)，終止當前遞歸（說明該子數組已有序）
• 所有子數組均完成分區和排序時，整個數組即有序

動圖演示：

（借用大佬的動圖）

性能分析：

時間復雜度：

• 時間性能你取決于遞歸的深度
• 最好情況：二叉樹幾乎平衡時，也就是數組劃分的比較均勻（基準值位于中間）。，遞歸次數最少，要log2N 次。遞歸過程中需要對i，j下標一起掃描數組，所以總體時間復雜度時O(N*log2N)
• 最壞情況：二叉樹極度不平衡 ，整體時間復雜度達到 (N2)

空間復雜度：

• 空間性能取決于遞歸消耗的棧空間
• 最好情況：已經分析過，需要遞歸logzN次，空間復雜度為O（logzN）
• 最壞情況：已經分析過，需要遞歸N-1次，空間復雜度為O(N)

穩定性：

• 不穩定?

代碼實現（Java）：

public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {// 取大于號，防止 start > endif (start >= end) {return;}int pivot = pirtiton1(array, start, end);quick(array, start, pivot - 1);quick(array, pivot + 1, end);}// 挖坑法private static int pirtiton1(int[] array, int left, int right) {int tmp = array[left];while (left < right) {// 為什么判斷條件加等號，// 用int[] arr = {5, 7, 3, 1, 4, 9, 6, 5}測試while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}// 將找到的大于基準值的元素填入右邊的"坑"array[right] = array[left];}// 將基準值放入最后的"坑"中（此時left == right）array[left] = tmp;return left;}