Java 五大經典排序算法統一封裝工具類

概述

本文提供一個泛型工具類 Sort，封裝了插入排序、希爾排序、堆排序、歸併排序、快速排序五種常見算法，支援任意實現 Comparable 接口的類型，便於直接復用。

完整代碼

public class Sort {

    // ========== 插入排序 ==========
    public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a) {
        insertionSort(a, 0, a.length - 1);
    }
    private static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a, int left, int right) {
        for (int p = left; p <= right; p++) {
            AnyType tmp = a[p];
            int j = p;
            for (; j > left && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    // ========== 希爾排序 ==========
    public static <AnyType extends Comparable<? super AnyType>> void shellSort(AnyType[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                AnyType tmp = arr[i];
                int j = i;
                for (; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }

    // ========== 堆排序 ==========
    private static int leftChild(int i) { return i * 2 + 1; }
    private static <AnyType extends Comparable<? super AnyType>> void perculateDown(AnyType[] arr, int i, int size) {
        AnyType tmp = arr[i];
        for (int child; (child = leftChild(i)) < size; i = child) {
            if (child != size - 1 && arr[child].compareTo(arr[child + 1]) < 0) child++;
            if (tmp.compareTo(arr[child]) < 0) arr[i] = arr[child];
            else break;
        }
        arr[i] = tmp;
    }
    public static <AnyType extends Comparable<? super AnyType>> void heapSort(AnyType[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) perculateDown(arr, i, arr.length);
        for (int i = arr.length - 1; i >= 0; i--) {
            swapReferences(arr, 0, i);
            perculateDown(arr, 0, i);
        }
    }

    // ========== 歸併排序 ==========
    public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
        AnyType[] tmp = (AnyType[]) new Comparable[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
    }
    private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
        if (start < end) {
            int mid = (start + end) >> 1;
            mergeSort(arr, start, mid, tmp);
            mergeSort(arr, mid + 1, end, tmp);
            merge(arr, start, mid, end, tmp);
        }
    }
    private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
        int i = start, j = mid + 1, k = start;
        while (i <= mid && j <= end) {
            tmp[k++] = arr[i].compareTo(arr[j]) < 0 ? arr[i++] : arr[j++];
        }
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= end) tmp[k++] = arr[j++];
        for (int m = start; m <= end; m++) arr[m] = tmp[m];
    }

    // ========== 快速排序 ==========
    private static final int LENGTH_DIFF = 20;
    public static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    private static <AnyType extends Comparable<? super AnyType>> void quickSort(AnyType[] arr, int left, int right) {
        if (left + LENGTH_DIFF <= right) {
            AnyType pivot = median(arr, left, right);
            int i = left, j = right;
            while (true) {
                while (arr[++i].compareTo(pivot) < 0);
                while (arr[--j].compareTo(pivot) > 0);
                if (i < j) swapReferences(arr, i, j);
                else break;
            }
            swapReferences(arr, i, right);
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        } else {
            insertionSort(arr, left, right);
        }
    }
    private static <AnyType extends Comparable<? super AnyType>> AnyType median(AnyType[] arr, int left, int right) {
        int center = (left + right) / 2;
        if (arr[center].compareTo(arr[left]) < 0) swapReferences(arr, center, left);
        if (arr[left].compareTo(arr[right]) > 0) swapReferences(arr, left, right);
        if (arr[center].compareTo(arr[right]) < 0) swapReferences(arr, center, right);
        return arr[right];
    }

    private static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] arr, int i, int j) {
        AnyType tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

使用示例

Integer[] data = {5, 2, 9, 1, 5, 6};
Sort.quickSort(data);          // 快速排序
Sort.mergeSort(data);          // 歸併排序
Sort.heapSort(data);           // 堆排序
Sort.shellSort(data);          // 希爾排序
Sort.insertionSort(data);      // 插入排序

算法特性對比

總結

此工具類採用泛型與模板方法模式，代碼復用性強，適合作為項目通用排序組件或算法學習參考。