在計算機科學與數學中，一個排序算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式排列的算法，排序後的資料即可放在有序數組。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜索算法與合併算法）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則：
- 輸出結果為遞增序列（遞增是針對所需的排序順序而言）
- 輸出結果是原輸入的一種排列、或是重組
雖然排序算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。舉例而言，冒泡排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新算法仍在不斷的被髮明。
冒泡排序 (Bubble Sort)
冒泡排序是一種簡單的排序算法。它重複地遍歷要排序的序列，依次比較兩個元素，如果它們的順序錯誤就把它們交換過來。遍歷序列的工作是重複地進行直到沒有再需要交換為止，此時説明該序列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢 “浮” 到數列的頂端。
算法步驟
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
- 針對所有的元素重複以上的步驟，除了最後一個；
- 重複步驟 1~3，直到排序完成。
圖解算法：
public class BubbleSortTest {
/**
* 冒泡排序
*/
public static int[] bubbleSort(int[] arr){
for (int i=1;i< arr.length;i++){
boolean flag = true;
for (int j = 0; j< arr.length-i;j++){
if (arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag){
break;
}
}
return arr;
}
public static void main(String[] args) {
int[] a = {12,23,45,67,89,21,22,11,10};
int[] a1 = bubbleSort(a);
System.out.println("a1:"+ Arrays.toString(a1));
System.out.println(Arrays.stream(a1).max());
}
}選擇排序 (Selection Sort)
選擇排序是一種簡單直觀的排序算法，無論什麼數據進去都是O(n²)的時間複雜度。所以用到它的時候，數據規模越小越好。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
算法步驟:
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
- 重複第2步，直到所有元素均排序完畢。
public class SelectionSort {
/**
* 選擇排序
*/
public static int[] selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("選擇排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = selectionSort(arr);
System.out.print("\n選擇排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}插入排序(Insertion Sort)
插入排序是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
插入排序也有一種優化算法，叫做拆半插入。
直接插入排序：在已排序序列中使用線性查找（從後往前一個一個比）來尋找插入位置。
折半插入排序：在已排序序列中使用二分查找來快速定位插入位置。
算法步驟
- 從第一個元素開始，該元素可以認為已經被排序；
- 取出下一個元素，在已經排序的元素序列中從後向前掃描；
- 如果該元素（已排序）大於新元素，將該元素移到下一位置；
- 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；
- 將新元素插入到該位置後；
- 重複步驟2~5。
public class InsertionSortTest {
/**
* 直接插入排序
*/
public static int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;
int current = arr[i];
// 從後往前比較，如果前一個元素大於當前元素，則將前一個元素向後移動一位，直到找到當前元素該插入的位置
while (preIndex >= 0 && arr[preIndex] > current) {
// 將 preIndex 的元素向後移動一位
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
/**
* 折半插入排序（二分插入排序）
* 時間複雜度：O(n²) 但比較次數只有 O(n log n)，比直接插入少很多比較
* 空間複雜度：O(1)
* 穩定排序
*/
public static void binaryInsertionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 從第2個元素開始處理
for (int i = 1; i < arr.length; i++) {
int temp = arr[i]; // 要插入的元素（先保存，防止被覆蓋）
int low = 0; // 已排序區的左邊界
int high = i - 1; // 已排序區的右邊界
// 二分查找插入位置（找第一個 >= temp 的位置，或者説最後一個 < temp 的位置的後面）
while (low <= high) {
int mid = low + (high - low) / 2; // 防止溢出寫法（推薦）
if (arr[mid] > temp) {
high = mid - 1; // temp 應該插在 mid 左邊
} else {
low = mid + 1; // temp 應該插在 mid 右邊（包括等於的情況，也往右找，保持穩定性）
}
}
// 循環結束時，low 就是插入位置（high 會變成 low-1）
// 將 [low, i-1] 的元素整體右移一位，給 temp 騰位置
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
// 把 temp 放到正確位置
arr[low] = temp;
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 2, 1, 4, 6, 10, 3, 1};
System.out.print("插入排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = insertionSort(arr);
System.out.print("\n插入排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
int[] arr1 = {5, 3, 2, 1, 4, 6, 10, 3, 1};
System.out.print("\n折半插入排序前:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
binaryInsertionSort(arr1);
System.out.print("\n折半插入排序結果:");
for (int i = 0; i < arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
}
}希爾排序(Shell Sort)
希爾排序是希爾(Donald Shell)於1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為遞減增量排序算法，同時該算法是衝破O(n²)的第一批算法之一。
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
算法步驟
我們來看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2, (n/2)/2, ..., 1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述：
- 選擇一個增量序列{t1, t2, …, tk}，其中(ti>tj, i<j, tk=1)；
- 按增量序列個數k，對序列進行k趟排序；
- 每趟排序，根據對應的增量t，將待排序列分割成若干長度為m的子序列，分別對各子表進行直接插入排序。僅增量因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。
public class ShellSortTest {
/**
* 希爾排序算法實現
*
* @param arr 待排序的整數數組
* @return 排序後的整數數組
*/
public static int[] shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2;
// 希爾排序主循環，逐步縮小間隔
while (gap > 0) {
// 對每個間隔組進行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i - gap;
// 在當前間隔組內進行插入排序
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
// 縮小間隔，繼續下一輪排序
gap /= 2;
}
return arr;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("希爾排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = shellSort(arr);
System.out.print("\n希爾排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}歸併排序(Merge Sort)
歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。
和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是O(nlogn)的時間複雜度。代價是需要額外的內存空間。
算法步驟
歸併排序算法是一個遞歸過程，邊界條件為當輸入序列僅有一個元素時，直接返回，具體過程如下：
- 如果輸入內只有一個元素，則直接返回，否則將長度為n的輸入序列分成兩個長度為n/2的子序列；
- 分別對這兩個子序列進行歸併排序，使子序列變為有序狀態；
- 設定兩個指針，分別指向兩個已經排序子序列的起始位置；
- 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間（用於存放排序結果），並移動指針到下一位置；
- 重複步驟3 ~4直到某一指針達到序列尾；
- 將另一序列剩下的所有元素直接複製到合併序列尾。
public class MergeSortTest {
/**
* 歸併排序主函數，將數組遞歸分解並排序
*
* @param arr 待排序的整數數組
* @return 排序後的整數數組
*/
public static int[] MergeSort(int[] arr) {
// 遞歸終止條件：數組長度小於等於1時直接返回
if (arr.length <= 1) {
return arr;
}
// 將數組從中間分割成兩部分
int middle = arr.length / 2;
int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
// 遞歸排序兩個子數組併合並
return Merge(MergeSort(arr_1), MergeSort(arr_2));
}
/**
* 合併兩個已排序的數組
*
* @param arr_1 第一個已排序的數組
* @param arr_2 第二個已排序的數組
* @return sorted_arr 合併後的已排序數組
*/
public static int[] Merge(int[] arr_1, int[] arr_2) {
// 創建結果數組，長度為兩個輸入數組長度之和
int[] sorted_arr = new int[arr_1.length + arr_2.length];
int idx = 0, idx_1 = 0, idx_2 = 0;
// 比較兩個數組元素，按順序合併到結果數組中
while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
if (arr_1[idx_1] < arr_2[idx_2]) {
sorted_arr[idx] = arr_1[idx_1];
idx_1 += 1;
} else {
sorted_arr[idx] = arr_2[idx_2];
idx_2 += 1;
}
idx += 1;
}
// 將剩餘元素複製到結果數組中
if (idx_1 < arr_1.length) {
while (idx_1 < arr_1.length) {
sorted_arr[idx] = arr_1[idx_1];
idx_1 += 1;
idx += 1;
}
} else {
while (idx_2 < arr_2.length) {
sorted_arr[idx] = arr_2[idx_2];
idx_2 += 1;
idx += 1;
}
}
return sorted_arr;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("歸併排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = MergeSort(arr);
System.out.print("\n歸併排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}快速排序(Quick Sort)
快速排序用到了分治思想，同樣的還有歸併排序。乍看起來快速排序和歸併排序非常相似，都是將問題變小，先排序子串，最後合併。不同的是快速排序在劃分子問題的時候經過多一步處理，將劃分的兩組數據劃分為一大一小，這樣在最後合併的時候就不必像歸併排序那樣再進行比較。但也正因為如此，劃分的不定性使得快速排序的時間複雜度並不穩定。
快速排序的基本思想：通過一趟排序將待排序列分隔成獨立的兩部分，其中一部分記錄的元素均比另一部分的元素小，則可分別對這兩部分子序列繼續進行排序，以達到整個序列有序。
算法步驟
快速排序使用分治法（Divide and conquer）策略來把一個序列分為較小和較大的2個子序列，然後遞迴地排序兩個子序列。具體算法描述如下：
- 從序列中隨機挑出一個元素，做為 “基準”(pivot)；
- 重新排列序列，將所有比基準值小的元素擺放在基準前面，所有比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個操作結束之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；
- 遞歸地把小於基準值元素的子序列和大於基準值元素的子序列進行快速排序。
public class QuickSortTest {
/**
* 交換數組中兩個位置的元素
*
* @param arr 要操作的數組
* @param i 第一個元素的下標
* @param j 第二個元素的下標
*/
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; // 臨時保存 arr[i] 的值
arr[i] = arr[j]; // 將 arr[j] 的值賦給 arr[i]
arr[j] = tmp; // 將保存的原 arr[i] 值賦給 arr[j]
}
/**
* 劃分函數（Partition）：將數組 arr[left...right] 劃分為兩部分
* 使得左邊部分都小於等於 pivot，右邊部分都大於等於 pivot
*
* @param arr 待排序數組
* @param left 當前區間的左邊界（包含）
* @param right 當前區間的右邊界（包含）
* @return 劃分完成後 pivot（基準值）最終所在的位置下標
*/
private static int Partition(int[] arr, int left, int right) {
// 如果區間只有一個元素，直接返回（防止後續隨機時出錯）
if (left == right) {
return left;
}
// 隨機選擇一個基準值（pivot），並將其交換到數組最右端
// 隨機化可以有效避免最壞情況（已排序或逆序時退化為 O(n²)）
int pivot = left + (int) (Math.random() * (right - left + 1));
swap(arr, pivot, right); // 把隨機選中的元素放到最右端作為基準
int small_idx = left; // small_idx 指向「小於區」的下一個位置（即大於等於區的起始）
// 從 left 開始遍歷到 right-1（right 位置是基準，不參與比較）
for (int i = left; i < right; i++) {
if (arr[i] < arr[right]) { // 如果當前元素小於基準值
swap(arr, i, small_idx); // 將它交換到「小於區」的末尾
small_idx++; // 小於區向右擴張一位
}
// 如果 arr[i] >= arr[right]，什麼都不做，留在原地（屬於大於等於區）
}
// 最後把基準值放到「小於區」和「大於等於區」的分界線上
swap(arr, small_idx, right);
return small_idx; // 返回基準值最終的位置
}
/**
* 快速排序主函數（遞歸實現）
*
* @param arr 待排序的整數數組
* @param left 待排序區間的左邊界（包含）
* @param right 待排序區間的右邊界（包含）
* @return 返回排好序的原數組（就地排序）
*/
public static int[] QuickSort(int[] arr, int left, int right) {
// 當 left >= right 時，區間中只有 0 或 1 個元素，無需排序（遞歸終止條件）
if (left < right) {
int pivotIndex = Partition(arr, left, right); // 進行一次劃分，得到基準位置
// 遞歸處理基準左邊的子區間
QuickSort(arr, left, pivotIndex - 1);
// 遞歸處理基準右邊的子區間
QuickSort(arr, pivotIndex + 1, right);
}
return arr; // 排序完成後返回原數組
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("快速排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = QuickSort(arr, 0, arr.length - 1);
System.out.print("\n快速排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}堆排序(Heap Sort)
堆排序是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆的性質：即子結點的值總是小於（或者大於）它的父節點。
算法步驟
- 將初始待排序列(R1, R2, ……, Rn)構建成大頂堆，此堆為初始的無序區；
- 將堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1, R2, ……, Rn-1)和新的有序區(Rn),且滿足R[1, 2, ……, n-1]<=R[n]；
- 由於交換後新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1, R2, ……, Rn-1)調整為新堆，然後再次將R[1]與無序區最後一個元素交換，得到新的無序區(R1, R2, ……, Rn-2)和新的有序區(Rn-1, Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。
public class HeapSortTest {
// 全局變量：記錄當前「堆」的有效長度（已排序的部分不屬於堆）
// 在排序過程中，堆的範圍會從 arr[0...heapLen-1] 逐漸縮小
static int heapLen;
/**
* 交換數組中兩個位置的元素
*
* @param arr 待操作的數組
* @param i 下標 i
* @ @param j 下標 j
*/
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* 構建最大堆（大頂堆）
* 從最後一個非葉子結點開始，依次向前進行下沉調整
*
* @param arr 待構建的數組
*/
private static void buildMaxHeap(int[] arr) {
heapLen = arr.length; // 初始時整個數組都屬於堆
// arr.length/2 - 1 是完全二叉樹中最後一個非葉子結點的下標
// 從這個結點開始向前遍歷，所有非葉子結點都要執行 heapify
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i);
}
}
/**
* 堆調整（下沉）：讓以 i 為根的子樹重新滿足大頂堆性質
*
* @param arr 數組
* @param i 需要下沉的結點下標（根結點）
*/
private static void heapify(int[] arr, int i) {
int left = 2 * i + 1; // 左孩子下標
int right = 2 * i + 2; // 右孩子下標
int largest = i; // 記錄當前子樹中值最大的結點下標，初始為根
// 如果右孩子在堆的有效範圍內，且右孩子的值更大，則更新 largest
if (right < heapLen && arr[right] > arr[largest]) {
largest = right;
}
// 如果左孩子在堆的有效範圍內，且左孩子的值更大，則更新 largest
if (left < heapLen && arr[left] > arr[largest]) {
largest = left;
}
// 如果子結點中有更大的值，則需要交換並繼續向下調整
if (largest != i) {
swap(arr, i, largest); // 根結點與更大的孩子交換
heapify(arr, largest); // 遞歸地對受影響的子樹繼續下沉
}
// 如果 largest == i，説明當前子樹已經滿足大頂堆性質，直接返回
}
/**
* 堆排序主函數（升序，使用大頂堆實現）
* 核心思想：
* 1. 先把整個數組建成一個大頂堆
* 2. 每次把堆頂（當前最大值）放到已排序區間的末尾
* 3. 縮小堆的大小，重新調整堆頂
*
* @param arr 待排序的整數數組
* @return 排好序的原數組（就地排序）
*/
public static int[] HeapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return arr;
}
heapLen = arr.length; // 初始化堆的長度為整個數組
buildMaxHeap(arr); // 第一步：構建初始大頂堆
// 從數組最後一個元素開始，逐步將最大值放到對應位置
for (int i = arr.length - 1; i > 0; i--) {
// 將當前堆頂（最大值）與當前未排序部分的最後一個元素交換
// 交換後，最大值就放到了正確位置（已排序區）
swap(arr, 0, i);
heapLen -= 1; // 已排序區域增大，堆的有效長度減1
// 由於交換後堆頂可能不再是最大值，需要重新調整堆（從根開始下沉）
heapify(arr, 0);
}
return arr; // 返回排好序的數組
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("堆排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = HeapSort(arr);
System.out.print("\n堆排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}計數排序(Counting Sort)
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。
計數排序(Counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。
算法步驟
- 找出數組中的最大值max、最小值min；
- 創建一個新數組C，其長度是max-min+1，其元素默認值都為0；
- 遍歷原數組A中的元素A[i]，以A[i]-min作為C數組的索引，以A[i]的值在A中元素出現次數作為C[A[i]-min]的值；
- 對C數組變形，新元素的值是該元素與前一個元素值的和，即當i>1時C[i] = C[i] + C[i-1]；
- 創建結果數組R，長度和原始數組一樣。
- 從後向前遍歷原始數組A中的元素A[i]，使用A[i]減去最小值min作為索引，在計數數組C中找到對應的值C[A[i]-min]，C[A[i]-min]-1就是A[i]在結果數組R中的位置，做完上述這些操作，將count[A[i]-min]減小1。
public class CountingSortTest {
/**
* 找出數組中的最大值和最小值
*
* @param arr 輸入數組（假設非空）
* @return 返回一個長度為 2 的數組：{最小值, 最大值}
*/
private static int[] getMinAndMax(int[] arr) {
int maxValue = arr[0]; // 初始假設第一個元素是最大值
int minValue = arr[0]; // 初始假設第一個元素是最小值
// 遍歷整個數組，更新最大值和最小值
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxValue) { // 如果當前元素更大，更新最大值
maxValue = arr[i];
} else if (arr[i] < minValue) { // 如果當前元素更小，更新最小值
minValue = arr[i];
}
}
// 返回 {min, max}，方便後面計算計數數組的大小
return new int[]{minValue, maxValue};
}
/**
* 計數排序（穩定版，支持負數）
* 適用於：數值範圍不大、包含負數的整數數組排序
* <p>
* 時間複雜度：O(n + k) 其中 k = max - min + 1
* 空間複雜度：O(n + k)
* 穩定性：穩定（相同元素相對順序不變）
*
* @param arr 待排序的整數數組
* @return 排好序的新數組（原數組不變）
*/
public static int[] CountingSort(int[] arr) {
// 長度小於 2 的數組已經有序，直接返回
if (arr == null || arr.length < 2) {
return arr;
}
// 第一步：找出數組的最大值和最小值
int[] extremum = getMinAndMax(arr);
int minValue = extremum[0];
int maxValue = extremum[1];
// 第二步：創建計數數組
// 大小為 (max - min + 1)，能把所有數值映射到非負下標
// 例如：[-5, -3, 0, 2] → min=-5 → countArr[0] 表示 -5，countArr[7] 表示 2
int[] countArr = new int[maxValue - minValue + 1];
// 第三步：統計每個數字出現的次數
for (int i = 0; i < arr.length; i++) {
// 將原值 arr[i] 映射為 countArr 的下標：arr[i] - minValue
countArr[arr[i] - minValue] += 1;
}
// 第四步：將計數數組變形為“累加數組”
// 變形後：countArr[i] 表示“小於等於當前值的元素總個數”
for (int i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i - 1];
}
// 第五步：從後向前遍歷原數組，確定每個元素應該放在結果數組的哪個位置
// 必須從後向前遍歷，才能保證排序的穩定性！
int[] result = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
// 計算當前元素應該放在結果數組的哪個下標
int mappedIndex = arr[i] - minValue; // 映射到 countArr 的下標
int position = countArr[mappedIndex] - 1; // 應該放的位置（從0開始）
result[position] = arr[i]; // 放到正確位置
countArr[mappedIndex] -= 1; // 該位置已用，下次同值元素放在前一個位置
}
// 返回排序好的新數組
return result;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1, 6, 10, 3, 1};
System.out.print("計數排序前:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int[] result = CountingSort(arr);
System.out.print("\n計數排序結果:");
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}
}桶排序(Bucket Sort)
桶排序是計數排序的升級版。它利用了函數的映射關係，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：
- 在額外空間充足的情況下，儘量增大桶的數量
- 使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中
桶排序的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裏，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行。
算法步驟
- 設置一個BucketSize，作為每個桶所能放置多少個不同數值；
- 遍歷輸入數據，並且把數據依次映射到對應的桶裏去；
- 對每個非空的桶進行排序，可以使用其它排序方法，也可以遞歸使用桶排序；
- 從非空桶裏把排好序的數據拼接起來。
public class BucketSortTest {
/**
* 找出 List<Integer> 中的最小值和最大值
*
* @param arr 非空整數列表
* @return int[] {最小值, 最大值}
*/
private static int[] getMinAndMax(List<Integer> arr) {
int maxValue = arr.get(0); // 假設第一個元素是最大值
int minValue = arr.get(0); // 假設第一個元素是最小值
// 遍歷所有元素，實時更新極值
for (int value : arr) {
if (value > maxValue) {
maxValue = value; // 發現更大的值，更新最大值
} else if (value < minValue) {
minValue = value; // 發現更小的值，更新最小值
}
}
return new int[] { minValue, maxValue };
}
/**
* 插入排序（專門用於小規模數據或單個桶內排序）
* 簡單、穩定、對於少量元素性能極佳（優於遞歸開銷）
*
* @param arr 待排序的列表
* @return 排好序的新列表
*/
private static List<Integer> insertionSort(List<Integer> arr) {
List<Integer> result = new ArrayList<>(arr); // 複製一份，避免修改原列表
// 從第二個元素開始，向前插入
for (int i = 1; i < result.size(); i++) {
int key = result.get(i); // 當前要插入的元素
int j = i - 1;
// 將比 key 大的元素全部後移一位
while (j >= 0 && result.get(j) > key) {
result.set(j + 1, result.get(j));
j--;
}
// 找到正確位置，插入 key
result.set(j + 1, key);
}
return result;
}
/**
* 桶排序（生產級優化版）
*
* 特性亮點：
* 1. 支持負數（通過 minValue 偏移）
* 2. 自動降級為插入排序（小數據量更快）
* 3. 自適應桶大小（遞歸時減半，防止最壞情況）
* 4. 邊界安全處理（越界、相等元素、桶大小為0）
* 5. 穩定性保持（桶內使用穩定排序）
*
* 時間複雜度：平均 O(n)，最壞 O(n²)，最佳 O(n)
* 空間複雜度：O(n)
*
* @param arr 待排序的整數列表
* @param bucket_size 每個桶預期容納的元素個數（建議 5~20）
* @return 排好序的新列表（原列表不變）
*/
public static List<Integer> BucketSort(List<Integer> arr, int bucket_size) {
// 邊界檢查：空列表或只有一個元素，直接返回
if (arr == null || arr.size() < 2) {
return arr == null ? new ArrayList<>() : new ArrayList<>(arr);
}
// 如果桶大小非法，設置為默認值 5（經驗最優）
if (bucket_size <= 0) {
bucket_size = 5;
}
// 小數據量直接用插入排序更快（避免遞歸和分配桶的開銷）
if (arr.size() <= 10 || bucket_size == 1) {
return insertionSort(arr);
}
// 獲取數值範圍
int[] extremum = getMinAndMax(arr);
int minValue = extremum[0];
int maxValue = extremum[1];
// 特判：所有元素都相等，無需排序
if (minValue == maxValue) {
return new ArrayList<>(arr);
}
// 計算桶的數量：(max - min) / bucket_size + 1
int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
// 創建 bucket_cnt 個空桶，每個桶是一個 ArrayList
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucket_cnt; i++) {
buckets.add(new ArrayList<Integer>());
}
// 將每個元素分配到對應的桶中
for (int element : arr) {
int bucketIndex = (element - minValue) / bucket_size;
// 防止數值恰好等於 maxValue 時越界（數學上可能 bucketIndex == bucket_cnt）
if (bucketIndex >= bucket_cnt) {
bucketIndex = bucket_cnt - 1;
}
buckets.get(bucketIndex).add(element);
}
// 對每個非空桶進行排序
for (int i = 0; i < buckets.size(); i++) {
List<Integer> bucket = buckets.get(i);
if (bucket.size() > 1) {
// 遞歸排序當前桶，桶大小減半（關鍵優化！防止退化成 O(n²)）
int newBucketSize = Math.max(1, bucket_size / 2);
buckets.set(i, BucketSort(bucket, newBucketSize));
}
// 如果桶內只有 0 或 1 個元素，無需排序
}
// 按順序合併所有桶，得到最終有序結果
ArrayList<Integer> result = new ArrayList<>();
for (List<Integer> bucket : buckets) {
result.addAll(bucket);
}
return result;
}
public static void main(String[] args) {
Integer[] arr = { 5, 4, 3, 2, 1, 6, 10, 3, 1 };
List<Integer> list = Arrays.asList(arr);
System.out.println("排序前的數組：" + list);
List<Integer> sortedList = BucketSort(list, 5);
System.out.println("排序後的數組：" + sortedList);
// 測試邊界情況
System.out.println("空列表測試：" + BucketSort(new ArrayList<>(), 5));
System.out.println("單元素測試：" + BucketSort(Arrays.asList(1), 5));
}
}基數排序(Radix Sort)
基數排序也是非比較的排序算法，對元素中的每一位數字進行排序，從最低位開始排序，複雜度為O(n×k)，n為數組長度，k為數組中元素的最大的位數；
基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基於分別排序，分別收集，所以是穩定的。
算法步驟
- 取得數組中的最大數，並取得位數，即為迭代次數N（例如：數組中最大數值為1000，則N=4）；
- A為原始數組，從最低位開始取每個位組成radix數組；
- 對radix進行計數排序（利用計數排序適用於小範圍數的特點）；
- 將radix依次賦值給原數組；
- 重複2~4步驟N次
public class RadixSortTest {
/**
* 基數排序（LSD）—— 完整支持負數版（推薦！）
* 核心思想：
* 1. 把負數和非負數分開處理
* 2. 對絕對值使用標準的正數基數排序
* 3. 最後：倒序放回負數 + 正序放回正數
*
* 時間複雜度：O(d × n)
* 空間複雜度：O(n)
* 穩定性：穩定
*/
public static void RadixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 第一步：分離正數和負數
List<Integer> negatives = new ArrayList<>();
List<Integer> nonNegatives = new ArrayList<>();
for (int num : arr) {
if (num < 0) {
negatives.add(-num); // 存絕對值，方便排序
} else {
nonNegatives.add(num);
}
}
// 第二步：分別對絕對值進行基數排序
int[] negArr = negatives.stream().mapToInt(i -> i).toArray();
int[] posArr = nonNegatives.stream().mapToInt(i -> i).toArray();
radixSortPositive(negArr); // 負數的絕對值排序
radixSortPositive(posArr); // 正數排序
// 第三步：合併結果（負數倒序 + 正數正序）
int index = 0;
// 先放負數（倒序，因為我們排的是絕對值，越大的絕對值應該越靠前）
for (int i = negArr.length - 1; i >= 0; i--) {
arr[index++] = -negArr[i];
}
// 再放正數（正序）
for (int num : posArr) {
arr[index++] = num;
}
}
// 標準的正數基數排序（只處理 >=0 的數）
private static void radixSortPositive(int[] arr) {
if (arr.length == 0) {
return;
}
// 找最大值，確定位數
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// 從個位開始，一位一位排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
// 按某一位進行計數排序（穩定）
private static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
// 統計當前位的數字出現次數
for (int i = 0; i < n; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 轉化為“小於等於該數字的總數”
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 從右向左填充（保證穩定性）
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[--count[digit]] = arr[i];
}
// 寫回原數組
System.arraycopy(output, 0, arr, 0, n);
}
// ==================== 測試主函數 ====================
public static void main(String[] args) {
int[] arr = { 5, 4, 3, 2, 1, 6, 10, 3, 1, -1, -6, -10, -3, -1 };
System.out.print("排序前: ");
printArray(arr);
RadixSort(arr);
System.out.print("排序後: ");
printArray(arr);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}穩定的排序算法
冒泡排序 (Bubble Sort)
時間複雜度：平均 O(n²)，最壞 O(n²)，最好 O(n)
空間複雜度：O(1)
特點：簡單實現，適合小數據集
插入排序 (Insertion Sort)
時間複雜度：平均 O(n²)，最壞 O(n²)，最好 O(n)
空間複雜度：O(1)
特點：對幾乎有序的數據效率高
雞尾酒排序 (Cocktail Sort)
時間複雜度：平均 O(n²)，最壞 O(n²)，最好 O(n)
空間複雜度：O(1)
特點：雙向冒泡排序
桶排序 (Bucket Sort)
時間複雜度：平均 O(n)，最壞 O(n²)，最好 O(n)
空間複雜度：O(k)
特點：需要 O(k) 額外空間
計數排序 (Counting Sort)
時間複雜度：平均 O(n+k)，最壞 O(n+k)，最好 O(n+k)
空間複雜度：O(n+k)
特點：需要 O(n+k) 額外空間
歸併排序 (Merge Sort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)，最好 O(n log n)
空間複雜度：O(n)
特點：需要 O(n) 額外空間
原地歸併排序
時間複雜度：平均 O(n log² n)
特點：如果使用最佳版本
二叉排序樹排序 (Binary Tree Sort)
時間複雜度：平均 O(n log n)，最壞 O(n²)
空間複雜度：O(n)
特點：期望時間 O(n log n)，最壞時間 O(n²)
鴿巢排序 (Pigeonhole Sort)
時間複雜度：平均 O(n+k)，最壞 O(n+k)
空間複雜度：O(k)
特點：需要 O(k) 額外空間
基數排序 (Radix Sort)
時間複雜度：平均 O(nk)，最壞 O(nk)
空間複雜度：O(n)
特點：需要 O(n) 額外空間
侏儒排序 (Gnome Sort)
時間複雜度：平均 O(n²)，最壞 O(n²)
空間複雜度：O(1)
圖書館排序 (Library Sort)
時間複雜度：平均 O(n log n)，最壞 O(n²)
空間複雜度：O((1+ε)n)
特點：期望時間 O(n log n)，需要 (1+ε)n 額外空間
塊排序 (Block Sort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)
空間複雜度：O(1)
Tim排序 (Timsort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)，最好 O(n)
空間複雜度：O(n)
特點：目前已知最快的排序算法，Python、Swift、Rust等語言的默認算法
不穩定的排序算法
選擇排序 (Selection Sort)
時間複雜度：平均 O(n²)，最壞 O(n²)，最好 O(n²)
空間複雜度：O(1)
希爾排序 (Shell Sort)
時間複雜度：平均 O(n log² n)
空間複雜度：O(1)
特點：如果使用最佳版本
克洛弗排序 (Clover Sort)
時間複雜度：平均 O(n)，最壞 O(n²)
空間複雜度：O(1)
梳排序 (Comb Sort)
時間複雜度：平均 O(n log n)
空間複雜度：O(1)
堆排序 (Heap Sort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)，最好 O(n log n)
空間複雜度：O(1)
平滑排序 (Smooth Sort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)
空間複雜度：O(1)
快速排序 (Quick Sort)
時間複雜度：平均 O(n log n)，最壞 O(n²)，最好 O(n log n)
空間複雜度：O(log n)
內省排序 (Introsort)
時間複雜度：平均 O(n log n)，最壞 O(n log n)
空間複雜度：O(log n)
耐心排序 (Patience Sort)
時間複雜度：平均 O(n log n + k)，最壞 O(n log n + k)
空間複雜度：O(n + k)
特點：需要找到最長遞增子序列
不實用的排序算法
Bogo排序
時間複雜度：平均 O(n × n!)，最壞期望時間為無窮
Stupid排序
時間複雜度：O(n³)
空間複雜度：遞歸版本需要 O(n²) 額外存儲器
珠排序 (Bead Sort)
時間複雜度：O(n) 或 O(√n)
特點：需要特別的硬件
煎餅排序 (Pancake Sort)
時間複雜度：O(n)
特點：需要特別的硬件
臭皮匠排序 (Stooge Sort)
時間複雜度：約 O(n²·⁷)
特點：算法簡單但效率極低
