目錄
1.?冒泡排序?(Bubble?Sort)
算法思路分析
代碼實現
復雜度分析
2. 選擇排序?(Selection Sort)
算法思路分析
代碼實現
復雜度分析
3. 插入排序?(Insertion Sort)
算法思路分析
代碼實現
復雜度分析
4. 快速排序 (Quick?Sort)
算法思路分析
代碼實現
復雜度分析
5. 歸并排序?(Merge?Sort)
算法思路分析
代碼實現
復雜度分析
6.?堆排序?(Heap?Sort)
算法思路分析
代碼實現
復雜度分析
算法性能對比總結
排序算法穩定性解釋:
- 穩定排序:相等的元素在排序后保持原有的相對順序
- 不穩定排序:相等的元素在排序后可能改變原有的相對順序
比如:
原始順序是?4?, 2,?4?,?1,?3,排序后變成了?1, 2,?3,?4?, 4?
- 原來:4??在?4??前面
- 現在:4??仍然在?4??前面
這就是穩定排序
1.?冒泡排序?(Bubble?Sort)
算法思路分析
冒泡排序是最簡單的排序算法之一,其核心思想是:
- 相鄰比較:比較相鄰的兩個元素,如果第一個比第二個大,則交換它們
- 逐步冒泡:每一輪比較后,最大的元素會"冒泡"到數組的末尾
- 重復執行:重復n-1輪,直到所有元素都排好序
代碼實現
/*** 冒泡排序算法* * 算法思路:* 1. 比較相鄰的兩個元素,如果第一個比第二個大,則交換它們* 2. 對每一對相鄰元素執行同樣的操作,從開始第一對到結尾的最后一對* 3. 重復以上步驟,每次都能將當前最大的元素"冒泡"到數組末尾* 4. 重復n-1輪,直到沒有任何一對數字需要比較*/
public static void bubbleSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數,總共需要n-1輪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;}}
}
復雜度分析
- 時間復雜度:O(n2) - 最壞和平均情況都是O(n2)
- 空間復雜度:O(1)?- 只需要一個臨時變量
- 穩定性:穩定排序
2. 選擇排序?(Selection Sort)
算法思路分析
選擇排序的核心思想是:
- 找最小值:在未排序序列中找到最小元素
- 交換位置:將找到的最小元素與未排序序列的第一個元素交換位置
- 重復執行:重復上述過程,直到所有元素都排好序
代碼實現
/*** 選擇排序算法* * 算法思路:* 1. 在未排序序列中找到最小元素,存放到排序序列的起始位置* 2. 然后,再從剩余未排序元素中繼續尋找最小元素* 3. 重復第二步,直到所有元素均排序完畢*/
public static void selectionSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {// 假設當前位置的元素是最小的int minIndex = i;// 在未排序序列中尋找最小元素for (int j = i + 1; j < n; j++) {// 如果找到更小的元素,更新最小元素的索引if (arr[j] < arr[minIndex]) {minIndex = j;}}// 將找到的最小元素與當前位置的元素交換if (minIndex != i) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}
}
復雜度分析
- 時間復雜度:O(n2)?- 無論最好、最壞、平均情況都是O(n2)
- 空間復雜度:O(1) - 只需要一個臨時變量
- 穩定性:不穩定排序
3. 插入排序?(Insertion Sort)
算法思路分析
插入排序的核心思想是:
- 構建有序序列:將第一個元素看作已排序序列
- 逐個插入:對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入
- 重復執行:重復上述過程,直到所有元素都插入到有序序列中
代碼實現
/*** 插入排序算法* * 算法思路:* 1. 從第一個元素開始,該元素可以認為已經被排序* 2. 取出下一個元素,在已經排序的元素序列中從后向前掃描* 3. 如果該元素(已排序)大于新元素,將該元素移到下一位置* 4. 重復步驟3,直到找到已排序的元素小于或者等于新元素的位置* 5. 將新元素插入到該位置后* 6. 重復步驟2~5*/
public static void insertionSort(int[] arr) {int n = arr.length;// 從第二個元素開始,逐個插入到已排序序列中for (int i = 1; i < n; i++) {// 保存當前要插入的元素int key = arr[i];// j指向已排序序列的最后一個元素int j = i - 1;// 從后向前掃描已排序序列,尋找插入位置// 如果已排序序列中的元素大于key,則將其向后移動while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 找到插入位置,將key插入arr[j + 1] = key;}
}
復雜度分析
- 時間復雜度:O(n2) - 最壞和平均情況,最好情況O(n)(已排序數組)
- 空間復雜度:O(1)?- 只需要一個臨時變量
- 穩定性:穩定排序
4. 快速排序 (Quick?Sort)
算法思路分析
快速排序是一種高效的排序算法,使用分治策略:
- 選擇基準:從數組中選擇一個基準元素(通常是最后一個元素)
- 分區操作:將數組分為兩部分,左邊都小于基準,右邊都大于基準
- 遞歸排序:對左右兩部分分別進行快速排序
- 合并結果:由于分區操作,合并時數組已經有序
代碼實現
/*** 快速排序算法* * 算法思路:* 1. 選擇一個基準元素(通常是最后一個元素)* 2. 將數組分為兩部分:左邊都小于基準,右邊都大于基準* 3. 對左右兩部分分別遞歸執行快速排序* 4. 由于分區操作,合并時數組已經有序*/
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}/*** 快速排序的遞歸實現* @param arr 待排序數組* @param low 起始索引* @param high 結束索引*/
private static void quickSort(int[] arr, int low, int high) {// 遞歸終止條件:當起始索引小于結束索引時if (low < high) {// 進行分區操作,返回基準元素的最終位置int pi = partition(arr, low, high);// 遞歸排序基準元素左邊的子數組quickSort(arr, low, pi - 1);// 遞歸排序基準元素右邊的子數組quickSort(arr, pi + 1, high);}
}/*** 分區操作:將數組分為兩部分* @param arr 待分區數組* @param low 起始索引* @param high 結束索引* @return 基準元素的最終位置*/
private static int partition(int[] arr, int low, int high) {// 選擇最后一個元素作為基準int pivot = arr[high];// i指向小于基準元素的最后一個位置int i = low - 1;// 遍歷數組,將小于基準的元素移到左邊for (int j = low; j < high; j++) {// 如果當前元素小于基準if (arr[j] < pivot) {i++;// 交換元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準元素放到正確的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;// 返回基準元素的最終位置return i + 1;
}
復雜度分析
- 時間復雜度:O(n log n) - 平均情況,最壞情況O(n2)
- 空間復雜度:O(log n)?- 遞歸調用棧的深度
- 穩定性:不穩定排序
5. 歸并排序?(Merge?Sort)
算法思路分析
歸并排序是一種穩定的排序算法,使用分治策略:
- 分解:將數組分成兩個子數組,遞歸地對子數組進行排序
- 合并:將兩個已排序的子數組合并成一個有序數組
- 遞歸執行:重復上述過程,直到所有元素都排好序
代碼實現
/*** 歸并排序算法* * 算法思路:* 1. 將數組分成兩個子數組,遞歸地對子數組進行排序* 2. 將兩個已排序的子數組合并成一個有序數組* 3. 重復上述過程,直到所有元素都排好序*/
public static void mergeSort(int[] arr) {mergeSort(arr, 0, arr.length - 1);
}/*** 歸并排序的遞歸實現* @param arr 待排序數組* @param left 左邊界* @param right 右邊界*/
private static void mergeSort(int[] arr, int left, int right) {// 遞歸終止條件:當左邊界小于右邊界時if (left < right) {// 計算中間位置int mid = left + (right - left) / 2;// 遞歸排序左半部分mergeSort(arr, left, mid);// 遞歸排序右半部分mergeSort(arr, mid + 1, right);// 合并兩個已排序的子數組merge(arr, left, mid, right);}
}/*** 合并兩個已排序的子數組* @param arr 原數組* @param left 左邊界* @param mid 中間位置* @param right 右邊界*/
private static void merge(int[] arr, int left, int mid, int right) {// 計算兩個子數組的長度int n1 = mid - left + 1;int n2 = right - mid;// 創建臨時數組來存儲兩個子數組int[] leftArray = new int[n1];int[] rightArray = new int[n2];// 復制數據到臨時數組for (int i = 0; i < n1; i++) {leftArray[i] = arr[left + i];}for (int j = 0; j < n2; j++) {rightArray[j] = arr[mid + 1 + j];}// 合并兩個子數組int i = 0, j = 0, k = left;// 比較兩個子數組的元素,將較小的元素放入原數組while (i < n1 && j < n2) {if (leftArray[i] <= rightArray[j]) {arr[k] = leftArray[i];i++;} else {arr[k] = rightArray[j];j++;}k++;}// 將剩余的元素復制到原數組while (i < n1) {arr[k] = leftArray[i];i++;k++;}while (j < n2) {arr[k] = rightArray[j];j++;k++;}
}
復雜度分析
- 時間復雜度:O(n?log?n) - 無論最好、最壞、平均情況都是O(n?log?n)
- 空間復雜度:O(n)?- 需要額外的數組來存儲合并結果
- 穩定性:穩定排序
6.?堆排序?(Heap?Sort)
算法思路分析
堆排序是一種基于堆數據結構的排序算法:
- 構建堆:將數組構建成最大堆(或最小堆)
- 提取根節點:將堆的根節點(最大值)與最后一個元素交換
- 調整堆:對剩余的n-1個元素重新構建堆
- 重復執行:重復上述過程,直到所有元素都排好序
代碼實現
/*** 堆排序算法* * 算法思路:* 1. 將數組構建成最大堆* 2. 將堆的根節點(最大值)與最后一個元素交換* 3. 對剩余的n-1個元素重新構建堆* 4. 重復上述過程,直到所有元素都排好序*/
public static void heapSort(int[] arr) {int n = arr.length;// 構建最大堆// 從最后一個非葉子節點開始,自底向上構建堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐個提取堆頂元素(最大值)for (int i = n - 1; i > 0; i--) {// 將堆頂元素(最大值)與最后一個元素交換int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 對剩余的i個元素重新構建最大堆heapify(arr, i, 0);}
}/*** 將以root為根的子樹調整為最大堆* @param arr 數組* @param n 堆的大小* @param root 根節點的索引*/
private static void heapify(int[] arr, int n, int root) {// 假設根節點是最大的int largest = root;// 計算左子節點的索引int left = 2 * root + 1;// 計算右子節點的索引int right = 2 * root + 2;// 如果左子節點存在且大于根節點if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子節點存在且大于當前最大值if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根節點if (largest != root) {// 交換根節點和最大值int temp = arr[root];arr[root] = arr[largest];arr[largest] = temp;// 遞歸調整被交換的子樹heapify(arr, n, largest);}
}
復雜度分析
- 時間復雜度:O(n?log n) - 無論最好、最壞、平均情況都是O(n?log n)
- 空間復雜度:O(1)?-?原地排序
- 穩定性:不穩定排序
堆排序原理參考:堆排序步驟推演-CSDN博客
算法性能對比總結
排序算法 | 時間復雜度 | 空間復雜度 | 穩定性 | 適用場景 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(1) | 穩定 | 小數據量 |
選擇排序 | O(n2) | O(1) | 不穩定 | 小數據量,交換次數少 |
插入排序 | O(n2) | O(1) | 穩定 | 小數據量,基本有序 |
快速排序 | O(n log n) | O(log n) | 不穩定 | 大數據量,實際應用 |
歸并排序 | O(n log n) | O(n) | 穩定 | 大數據量,要求穩定 |
堆排序 | O(n?log n) | O(1) | 不穩定 | 大數據量,原地排序 |
?使用建議:小數據量(n?< 50):使用插入排序,代碼簡單且效率較高;大數據量:優先使用快速排序,平均性能最好;要求穩定性:使用歸并排序;內存受限:使用堆排序,原地排序;
推薦:Java的Arrays.sort(),此方法已經為我們提供了高效的排序實現