Java 經典排序算法全集：冒泡、選擇、插入、快速、歸並、二分查找完整實現與性能對比

排序算法分類與選型指南

選型口訣：

• n ≤ 50 → 直接插入/選擇
• 基本有序 → 插入/冒泡/隨機快排
• n 大、追求穩定 → 歸並/堆/快排（三向切分優化）

統一測試框架 SortDemo

package com.test;

import java.util.Random;

public class SortDemo {
    // ---------- 工具方法 ----------
    public int[] createArray() {
        Random r = new Random();
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) a[i] = r.nextInt(100) - r.nextInt(100); // 含負數
        printArray(a, "原始序列");
        return a;
    }

    public void printArray(int[] a, String tag) {
        System.out.print(tag + "：");
        for (int v : a) System.out.print(v + " ");
        System.out.println();
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    // ---------- 1. 冒泡排序 ----------
    public void bubbleSort(int[] a, boolean asc) {
        for (int i = 1; i < a.length; i++) {
            boolean swapped = false;
            for (int j = 0; j < a.length - i; j++) {
                if (asc ? a[j] > a[j+1] : a[j] < a[j+1]) {
                    swap(a, j, j+1);
                    swapped = true;
                }
            }
            if (!swapped) break; // 優化：提前終止
        }
        printArray(a, asc ? "冒泡↑" : "冒泡↓");
    }

    // ---------- 2. 直接選擇排序 ----------
    public void selectSort(int[] a, boolean asc) {
        for (int i = 0; i < a.length - 1; i++) {
            int extIdx = i;
            for (int j = i + 1; j < a.length; j++) {
                if (asc ? a[j] < a[extIdx] : a[j] > a[extIdx]) extIdx = j;
            }
            if (extIdx != i) swap(a, i, extIdx);
        }
        printArray(a, asc ? "選擇↑" : "選擇↓");
    }

    // ---------- 3. 直接插入排序 ----------
    public void insertSort(int[] a, boolean asc) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && (asc ? a[j] > key : a[j] < key)) {
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = key;
        }
        printArray(a, asc ? "插入↑" : "插入↓");
    }

    // ---------- 4. 快速排序 ----------
    public void quickSort(int[] a, boolean asc) {
        qsort(a, 0, a.length - 1, asc);
        printArray(a, asc ? "快速↑" : "快速↓");
    }

    private void qsort(int[] a, int lo, int hi, boolean asc) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi, asc);
        qsort(a, lo, p - 1, asc);
        qsort(a, p + 1, hi, asc);
    }

    private int partition(int[] a, int lo, int hi, boolean asc) {
        int pivot = a[lo];
        int i = lo, j = hi;
        while (i < j) {
            while (i < j && (asc ? a[j] >= pivot : a[j] <= pivot)) j--;
            if (i < j) a[i++] = a[j];
            while (i < j && (asc ? a[i] <= pivot : a[i] >= pivot)) i++;
            if (i < j) a[j--] = a[i];
        }
        a[i] = pivot;
        return i;
    }

    // ---------- 5. 歸並排序 ----------
    public void mergeSort(int[] a) {
        int[] tmp = new int[a.length];
        mergeSort(a, 0, a.length - 1, tmp);
        printArray(a, "歸並↑");
    }

    private void mergeSort(int[] a, int l, int r, int[] tmp) {
        if (l >= r) return;
        int m = (l + r) >>> 1;
        mergeSort(a, l, m, tmp);
        mergeSort(a, m + 1, r, tmp);
        merge(a, l, m, r, tmp);
    }

    private void merge(int[] a, int l, int m, int r, int[] tmp) {
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
        while (i <= m) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        System.arraycopy(tmp, 0, a, l, k);
    }

    // ---------- 6. 數組反轉 ----------
    public void reverse(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) swap(a, i, j);
        printArray(a, "反轉");
    }

    // ---------- 7. 二分查找（遞歸 + 迭代） ----------
    public int binarySearchRec(int[] a, int key) {
        return bsRec(a, key, 0, a.length - 1);
    }
    private int bsRec(int[] a, int key, int l, int r) {
        if (l > r) return -1;
        int m = (l + r) >>> 1;
        if (key < a[m]) return bsRec(a, key, l, m - 1);
        if (key > a[m]) return bsRec(a, key, m + 1, r);
        return m;
    }

    public int binarySearchIter(int[] a, int key) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int m = (l + r) >>> 1;
            if (key < a[m]) r = m - 1;
            else if (key > a[m]) l = m + 1;
            else return m;
        }
        return -1;
    }

    // ---------- 主測試入口 ----------
    public static void main(String[] args) {
        SortDemo demo = new SortDemo();
        int[] arr;

        arr = demo.createArray(); demo.bubbleSort(arr.clone(), true);
        arr = demo.createArray(); demo.bubbleSort(arr.clone(), false);

        arr = demo.createArray(); demo.selectSort(arr.clone(), true);
        arr = demo.createArray(); demo.selectSort(arr.clone(), false);

        arr = demo.createArray(); demo.insertSort(arr.clone(), true);
        arr = demo.createArray(); demo.insertSort(arr.clone(), false);

        arr = demo.createArray(); demo.quickSort(arr.clone(), true);
        arr = demo.createArray(); demo.quickSort(arr.clone(), false);

        arr = demo.createArray(); demo.mergeSort(arr.clone());

        arr = demo.createArray(); demo.reverse(arr.clone());

        // 二分查找演示（需先排序）
        arr = demo.createArray(); demo.quickSort(arr, true);
        int idx = demo.binarySearchIter(arr, 74);
        System.out.println("二分查找 74 → 索引：" + idx + (idx >= 0 ? " (值=" + arr[idx] + ")" : " 未找到"));
    }
}

關鍵優化點說明

1. 冒泡加旗標：無交換即有序，提前退出，最好 O(n)。
2. 插入排序移位代替交換：減少賦值操作，實測比冒泡快 2 倍+。
3. 快排原地分區：雙指針法，空間 O(log n) 棧深度；可進一步引入三向切分應對大量重複鍵。
4. 歸並輔助數組外部分配：避免遞歸層層 new 數組，空間固定 O(n)。
5. 二分查找無符號右移：(l+r)>>>1 防溢出，比除法快。

實戰建議

• 生產代碼直接用 Arrays.sort() / Collections.sort()：JDK 使用雙軸快排（基本類型）與 TimSort（對象），經過極致優化。
• 面試手寫重點：快排分區、歸並合併、堆調整、希爾增量序列。
• 自定義比較器場景：實現 Comparator<T> 配合 Arrays.sort(T[], Comparator)。