概要

排序算法是編程中最基礎也是最重要的算法之一。通過學習和理解不同的排序算法，我們可以在實際開發中選擇合適的算法來解決問題。本文將介紹八大常用排序算法，并分別用 Python、C++ 和 Java 三種語言實現。

---

時間復雜度

1. 冒泡排序（Bubble Sort）

算法描述: 冒泡排序是一種簡單的排序算法，通過不斷交換相鄰元素，使得較大的元素“浮”到數組的末尾。

時間復雜度

• 最佳情況：O(n)
• 平均情況：O(n2)
• 最壞情況：O(n2)

空間復雜度： O(1)
穩定性： 穩定

實現步驟

1. 比較相鄰元素，前大則交換

2. 對每一對相鄰元素重復操作

3. 每次遍歷后范圍縮小1

4. 重復直到無交換發生

代碼實現

python版本

def bubble_sort(arr):n = len(arr)for i in range(n-1):for j in range(n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr

C++版本

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}

Java版本

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}
}

2. 選擇排序（Selection Sort）

算法描述： 選擇排序通過分為有序區和無序區，逐步從無序區中找到最小元素，放到有序區的末尾。

時間復雜度：

• 最佳情況：O(n2)
• 平均情況：O(n2)
• 最壞情況：O(n2)

空間復雜度： O(1)

穩定性： 不穩定

代碼實現
python版本

# Python
def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(n-1-i):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr

C++版本

// C++
void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; ++i) {bool swapped = false;for (int j = 0; j < n-1-i; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);swapped = true;}}if (!swapped) break;}
}

Java版本

// Java
public static void bubbleSort(int[] arr) {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;}
}

3. 插入排序（Insertion Sort）

算法思想： 將未排序元素逐個插入已排序序列的合適位置

時間復雜度：

• 平均：O(n2)

• 最壞：O(n2)

• 最好：O(n)

穩定性： 穩定

python版本

# Python
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >=0 and key < arr[j] :arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr

C++版本

// C++
void insertionSort(int arr[], int n) {for (int i = 1; i < n; ++i) {int key = arr[i];int j = i-1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

Java版本

// Java
public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

4. 希爾排序（Shell Sort）

算法思想： 改進的插入排序，通過間隔分組進行預處理
時間復雜度： O(n log n) ~ O(n2)
穩定性： 不穩定

python版本

# Python
def shell_sort(arr):n = len(arr)gap = n//2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] > temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap //= 2return arr

C++版本

// C++
void shellSort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {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;}}
}

Java版本

// Java
public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n/2; gap > 0; gap /= 2) {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;}}
}

5. 歸并排序（Merge Sort）

算法思想： 分治法，遞歸拆分后合并有序子序列
時間復雜度： O(n log n)
穩定性： 穩定

python版本

# Python
def merge_sort(arr):if len(arr) > 1:mid = len(arr)//2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

C++版本：

// C++
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}
}

Java版本

// Java
public static void mergeSort(int[] arr, int l, int r) {if (l < r) {int m = (l + r) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);int[] L = Arrays.copyOfRange(arr, l, m + 1);int[] R = Arrays.copyOfRange(arr, m + 1, r + 1);int i = 0, j = 0, k = l;while (i < L.length && j < R.length) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < L.length) arr[k++] = L[i++];while (j < R.length) arr[k++] = R[j++];}
}

6. 快速排序（Quick Sort）

算法思想： 分治法，選取基準元素進行分區排序
時間復雜度：

• 平均：O(n log n)

• 最壞：O(n2)

穩定性： 不穩定

python版本

在這里插入代碼片# Python
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr)//2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

C++版本：

// C++
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], arr[j]);}}swap(arr[i+1], arr[high]);return i+1;
}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);}
}

Java版本

// Java
public 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);}
}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++;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;
}

7. 堆排序（Heap Sort）

算法思想： 利用堆數據結構進行選擇排序
時間復雜度： O(n log n)
穩定性： 不穩定

python版本

# Python
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n//2-1, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr

C++版本：

// C++
void heapify(int arr[], int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest])largest = l;if (r < n && arr[r] > arr[largest])largest = r;if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {for (int i = n/2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

Java版本

// Java
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;heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}

8. 計數排序（Counting Sort）

適用場景： 整數排序且值范圍不大
時間復雜度： O(n + k)
穩定性： 穩定

python版本

# Python
def counting_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] += 1idx = 0for i in range(len(count)):while count[i] > 0:arr[idx] = iidx += 1count[i] -= 1return arr

C++版本：

// C++
void countingSort(int arr[], int n) {int maxVal = *max_element(arr, arr + n);int count[maxVal + 1] = {0};for (int i = 0; i < n; i++)count[arr[i]]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

Java版本

// Java
public static void countingSort(int[] arr) {int maxVal = Arrays.stream(arr).max().getAsInt();int[] count = new int[maxVal + 1];for (int num : arr) count[num]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

小結

排序算法	平均時間復雜度	最壞時間復雜度	空間復雜度	穩定性
冒泡排序	O(n2)	O(n2)	O(1)	穩定
選擇排序	O(n2)	O(n2)	O(1)	不穩定
插入排序	O(n2)	O(n2)	O(1)	穩定
希爾排序	O(n log n)	O(n2)	O(1)	不穩定
歸并排序	O(n log n)	O(n log n)	O(n)	穩定
快速排序	O(n log n)	O(n2)	O(log n)	不穩定
堆排序	O(n log n)	O(n log n)	O(1)	不穩定
計數排序	O(n + k)	O(n + k)	O(k)	穩定

注：k為計數排序的值域范圍

應用場景建議：

• 小規模數據：插入排序

• 通用高效：快速排序

• 內存敏感：堆排序

• 穩定需求：歸并排序

• 整數排序：計數排序