您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

經典八大排序算法深度解析：Java 與 Python 完整實現指南

編輯：Java 綜合教學

前言：為什麼排序算法是程式設計的基石

排序算法是電腦科學中最基礎、也是最經典的課題之一。無論是面試準備、競賽編程，還是日常開發中的效能優化，掌握這八大經典排序算法都是工程師的必修課。本文將系統整理直接插入排序、希爾排序、直接選擇排序、堆排序、冒泡排序、快速排序、歸並排序、基數排序的核心邏輯、時空複雜度、穩定性特點，並提供基於《算法導論》偽代碼的 Java 與 Python 雙語言完整實現，助你建立扎實的算法底蘊。

八大排序算法總覽：複雜度與特性一覽表

在深入代碼前，先建立整體認知框架。下表總結了八大排序的關鍵指標：

時間複雜度：最好 / 平均 / 最壞情況
空間複雜度：輔助空間需求
穩定性：相等元素相對位置是否保持
原址排序：是否佔用常數級額外空間

八大排序算法分類與複雜度總表

逐個擊破：算法邏輯與代碼實現

1. 直接插入排序 — 有序區間的動態維護

核心思想：將數組分為「已排序」與「未排序」兩部分，每次從未排序區取出首元素，在已排序區從後向前掃描，將比它大的元素依次後移，騰出位置插入。

最好 O(n)（已有序），最壞 O(n²)（逆序）
穩定、原址

Java 實現

public class InsertSort {
    public int[] sort(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;
        }
        return arr;
    }
}

Python 實現

def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

2. 希爾排序 — 縮小增量的插入排序進化版

核心思想：按增量（gap）將數組分組，對每組進行插入排序，逐步縮小增量至 1。利用了插入排序對「近乎有序」數組極快的特性。

平均 O(n^1.3)，最壞 O(n²)
不穩定、原址

Java 實現

public class ShellSort {
    public int[] sort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                if (arr[i] < arr[i - gap]) {
                    int key = arr[i];
                    int j = i - gap;
                    while (j >= 0 && arr[j] > key) {
                        arr[j + gap] = arr[j];
                        j -= gap;
                    }
                    arr[j + gap] = key;
                }
            }
        }
        return arr;
    }
}

Python 實現

def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            if arr[i] < arr[i - gap]:
                key = arr[i]
                j = i - gap
                while j >= 0 and arr[j] > key:
                    arr[j + gap] = arr[j]
                    j -= gap
                arr[j + gap] = key
        gap //= 2
    return arr

3. 直接選擇排序 — 每輪鎖定一個極值

核心思想：每輪在未排序區找到最小（大）元素，與未排序區首位交換。雖然簡單，但無論輸入如何，比較次數固定為 O(n²)。

最好/最壞均 O(n²)
不穩定、原址

Java 實現

public class SelectSort {
    public int[] sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) minIdx = j;
            }
            if (minIdx != i) {
                int tmp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = tmp;
            }
        }
        return arr;
    }
}

Python 實現

def select_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

4. 堆排序 — 利用完全二叉樹特性的高效選擇

核心思想：將數組視為完全二叉樹，構建最大堆，堆頂即為最大值。反覆「交換堆頂與末尾、縮小堆規模、下沉調整」即可完成排序。

時間 O(n log n)，空間 O(1)
不穩定、原址

Java 實現（關鍵輔助方法）

public class HeapSort {
    // 維護以 i 為根的最大堆
    private void maxHeapify(int[] arr, int i, int heapSize) {
        int l = 2 * i + 1, r = l + 1, largest = i;
        if (l < heapSize && arr[l] > arr[largest]) largest = l;
        if (r < heapSize && arr[r] > arr[largest]) largest = r;
        if (largest != i) {
            swap(arr, i, largest);
            maxHeapify(arr, largest, heapSize);
        }
    }
    // 構建初始最大堆
    private void buildMaxHeap(int[] arr) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--)
            maxHeapify(arr, i, arr.length);
    }
    public int[] sort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            maxHeapify(arr, 0, i);
        }
        return arr;
    }
    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Python 實現

def max_heapify(arr, i, heap_size):
    l, r, largest = 2 * i + 1, 2 * i + 2, i
    if l < heap_size and arr[l] > arr[largest]: largest = l
    if r < heap_size and arr[r] > arr[largest]: largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        max_heapify(arr, largest, heap_size)

def build_max_heap(arr):
    for i in range((len(arr) - 1) // 2, -1, -1):
        max_heapify(arr, i, len(arr))

def heap_sort(arr):
    build_max_heap(arr)
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        max_heapify(arr, 0, i)
    return arr

5. 冒泡排序 — 相鄰交換，大元素「浮」到頂端

核心思想：雙重循環，內層相鄰比較交換，每輪將當前最大值移至未排序區末尾。可加旗標優化：若某輪無交換則提前結束。

最好 O(n)，最壞 O(n²)
穩定、原址

Java 實現

public class BubbleSort {
    public int[] sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = n - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
        return arr;
    }
    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Python 實現

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1, i, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                swapped = True
        if not swapped: break
    return arr

6. 快速排序 — 分治法的巔峰之作

核心思想：選取基準，一趟分區使左側≤基準≤右側，遞歸處理左右子區。隨機化基準可避免最壞 O(n²)。

平均 O(n log n)，最壞 O(n²)
不穩定、原址（遞歸棧 O(log n)）

Java 實現（隨機化分區）

public class QuickSort {
    private Random rand = new Random();
    public int[] sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quickSort(arr, low, mid - 1);
            quickSort(arr, mid + 1, high);
        }
    }
    private int partition(int[] arr, int low, int high) {
        // 隨機選基準，避免有序數組退化
        swap(arr, high, rand.nextInt(high - low + 1) + low);
        int pivot = arr[high], i = low - 1;
        for (int j = low; j < high; j++)
            if (arr[j] <= pivot) swap(arr, ++i, j);
        swap(arr, i + 1, high);
        return i + 1;
    }
    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Python 實現

import random
def quick_sort(arr, low, high):
    if low < high:
        mid = partition(arr, low, high)
        quick_sort(arr, low, mid - 1)
        quick_sort(arr, mid + 1, high)

def partition(arr, low, high):
    rand = random.randint(low, high)
    arr[high], arr[rand] = arr[rand], arr[high]
    pivot, i = arr[high], low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

7. 歸並排序 — 分治法的穩定標杆

核心思想：遞歸拆分至單元素，再合併兩個有序子陣列。需 O(n) 輔助空間，但保證 O(n log n) 最壞情況且穩定。

時間 O(n log n)，空間 O(n)
穩定、非原址

Java 實現

public class MergeSort {
    private int[] temp;
    public int[] sort(int[] arr) {
        temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
        return arr;
    }
    private void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) >>> 1;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }
    private void merge(int[] arr, int low, int mid, int high) {
        System.arraycopy(arr, low, temp, low, high - low + 1);
        int i = low, j = mid + 1, k = low;
        while (i <= mid && j <= high)
            arr[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
        while (i <= mid) arr[k++] = temp[i++];
        // 右半部剩餘元素已在原位，無需複製
    }
}

Python 實現

def merge_sort(arr, p, r):
    if p < r:
        q = (p + r) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)

def merge(arr, p, q, r):
    left = arr[p:q+1]
    right = arr[q+1:r+1]
    i = j = 0
    for k in range(p, r + 1):
        if j >= len(right) or (i < len(left) and left[i] <= right[j]):
            arr[k] = left[i]; i += 1
        else:
            arr[k] = right[j]; j += 1

8. 基數排序 — 非比較排序的線性奇蹟

核心思想：按位數（個位→十位→…）分配到 0-9 桶，再收集。利用「桶排序」思想，突破比較排序 O(n log n) 下界。

時間 O(d·(n+r))，d=位數，r=基數(10)
穩定、非原址、適用於非負整數

Python 實現（LSD 低位優先）

def count_digits(arr, radix=10):
    max_num = max(arr)
    cnt = 0
    while max_num:
        max_num //= radix
        cnt += 1
    return cnt

def radix_sort(arr, radix=10):
    k = count_digits(arr, radix)
    for i in range(1, k + 1):
        buckets = [[] for _ in range(radix)]
        for num in arr:
            digit = (num // (radix ** (i - 1))) % radix
            buckets[digit].append(num)
        arr.clear()
        for bucket in buckets:
            arr.extend(bucket)
    return arr

總結與選型建議

場景	推薦算法	理由
小規模 / 近乎有序	插入排序	最好 O(n)，實現簡單
通用高效 / 不要求穩定	快速排序	平均最快，原址，緩存友好
要求穩定 / 外部排序	歸並排序	穩定 O(n log n)，適合鏈表/磁盤
海量整數 / 固定位數	基數排序	線性時間，非比較
嵌入式 / 記憶體極限	堆排序	原址 O(n log n)，無遞歸棧溢出風險