Java 实现常见排序算法

import java.util.Arrays;

public class SortDemo {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 9, 1, 7, 4};
        System.out.println("原始数组：" + Arrays.toString(arr));

        // 复制数组，避免共用同一个数组
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        bubbleSort(arr1);
        System.out.println("冒泡排序：" + Arrays.toString(arr1));

        int[] arr2 = Arrays.copyOf(arr, arr.length);
        selectSort(arr2);
        System.out.println("选择排序：" + Arrays.toString(arr2));

        int[] arr3 = Arrays.copyOf(arr, arr.length);
        insertSort(arr3);
        System.out.println("插入排序：" + Arrays.toString(arr3));

        int[] arr4 = Arrays.copyOf(arr, arr.length);
        shellSort(arr4);
        System.out.println("希尔排序：" + Arrays.toString(arr4));

        int[] arr5 = Arrays.copyOf(arr, arr.length);
        quickSort(arr5, 0, arr5.length - 1);
        System.out.println("快速排序：" + Arrays.toString(arr5));

        int[] arr6 = Arrays.copyOf(arr, arr.length);
        mergeSort(arr6, 0, arr6.length - 1);
        System.out.println("归并排序：" + Arrays.toString(arr6));

        int[] arr7 = Arrays.copyOf(arr, arr.length);
        heapSort(arr7);
        System.out.println("堆排序：" + Arrays.toString(arr7));
    }

    /**
     * 冒泡排序：相邻元素比较交换，大的往后冒泡
     * 时间：O(n²)，空间 O(1)，稳定排序
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapFlag = 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;
                    swapFlag = true;
                }
            }
            if (!swapFlag) break; // 本轮无交换，提前退出
        }
    }

    /**
     * 选择排序：每次选最小元素放到前面
     * 时间：O(n²)，空间 O(1)，不稳定
     */
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        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;
                }
            }
            // 交换
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }

    /**
     * 插入排序：像打牌，把元素插入前面有序区间
     * 时间 O(n²)，空间 O(1)，稳定；数据接近有序时效率很高
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int val = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > val) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = val;
        }
    }

    /**
     * 希尔排序：改进插入排序，按步长分组插入，逐步缩小步长到1
     * 时间 O(n^1.3) 左右，空间 O(1)，不稳定
     */
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int val = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > val) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = val;
            }
            gap /= 2;
        }
    }

    /**
     * 快速排序：选基准，分区，左小右大，递归
     * 平均 O(nlogn)，最坏 O(n²)；空间 O(logn)，不稳定
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    /**
     * 归并排序：分治，拆分数组，合并有序数组
     * O(nlogn)，空间 O(n)，稳定排序
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        // 拷贝回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    /**
     * 堆排序：构建大顶堆，堆顶和末尾交换，调整堆
     * O(nlogn)，空间 O(1)，不稳定
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, n);
        }
        // 堆顶交换到末尾，重新调整堆
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    private static void adjustHeap(int[] arr, int parent, int len) {
        int root = arr[parent];
        int leftChild = parent * 2 + 1;
        while (leftChild < len) {
            int rightChild = leftChild + 1;
            if (rightChild < len && arr[rightChild] > arr[leftChild]) {
                leftChild = rightChild;
            }
            if (arr[leftChild] <= root) break;
            arr[parent] = arr[leftChild];
            parent = leftChild;
            leftChild = parent * 2 + 1;
        }
        arr[parent] = root;
    }
}