排序算法详解：常用排序原理与对比 ⭐⭐⭐

/**
 * 冒泡排序 - 基础版本
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        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]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }
            // 如果本轮没有发生交换，说明已经有序，提前结束
            if (!swapped) break;
        }
    }

    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

/**
 * 鸡尾酒排序（双向冒泡）
 * 适用于近乎有序的数组，对完全有序数组可以做到 O(n)
 */
public static void cocktailSort(int[] arr) {
    if (arr == null || arr.length < 2) return;

    int left = 0;
    int right = arr.length - 1;
    boolean swapped;

    while (left < right) {
        swapped = false;

        // 从左向右冒泡：将较大元素放到右边
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                swapped = true;
            }
        }
        right--;

        if (!swapped) break;

        swapped = false;

        // 从右向左冒泡：将较小元素放到左边
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                swap(arr, i, i - 1);
                swapped = true;
            }
        }
        left++;

        if (!swapped) break;
    }
}

/**
 * 选择排序
 * 时间复杂度：O(n²) —— 无论数据是否有序，都需要进行 n(n-1)/2 次比较
 * 空间复杂度：O(1)
 * 稳定性：不稳定 ⭐
 */
public class SelectionSort {

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;  // 假设当前 i 为最小值索引

            // 在未排序区间 [i+1, n-1] 中找最小元素
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将找到的最小元素与未排序区间的第一个元素交换
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

/**
 * 插入排序
 * 时间复杂度：最好 O(n)，平均/最坏 O(n²)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 */
public class InsertionSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i];  // 待插入的元素
            int j = i - 1;

            // 将比 current 大的元素向后移动，为 current 腾出位置
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];  // 元素后移
                j--;
            }

            // 插入 current 到正确位置
            arr[j + 1] = current;
        }
    }

    /**
     * 二分插入排序（折半插入）
     * 在已排序区间使用二分查找，减少比较次数
     * 但移动次数不变，所以整体时间复杂度仍是 O(n²)
     */
    public static void binaryInsertionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i];
            int left = 0, right = i - 1;

            // 二分查找插入位置
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] > current) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 将 [left, i-1] 区间的元素后移
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }

            arr[left] = current;
        }
    }
}

/**
 * 希尔排序（Shell Sort）
 * 时间复杂度：平均 O(n^1.3)，最坏 O(n²)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class ShellSort {

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;

        // 初始增量：n/2，逐步缩小
        for (int gap = n / 2; gap >= 1; gap /= 2) {

            // 对每个子序列进行插入排序
            for (int i = gap; i < n; i++) {
                int current = arr[i];
                int j = i - gap;

                // 在当前子序列中寻找插入位置
                while (j >= 0 && arr[j] > current) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = current;
            }
        }
    }

    /**
     * 使用 Knuth 序列的希尔排序
     * 增量公式：h = 3*h + 1 (h 初始为 1)
     * Knuth 序列在实践中通常比简单的 n/2 序列更快
     */
    public static void shellSortKnuth(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;

        // 使用 Knuth 序列计算初始增量
        // h = 1, 4, 13, 40, 121, ...
        int gap = 1;
        while (gap < n / 3) {
            gap = gap * 3 + 1;
        }

        while (gap >= 1) {
            for (int i = gap; i < n; i++) {
                int current = arr[i];
                int j = i - gap;

                while (j >= 0 && arr[j] > current) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = current;
            }
            gap /= 3;  // 缩小增量
        }
    }
}

/**
 * 归并排序
 * 时间复杂度：所有情况 O(n log n)
 * 空间复杂度：O(n) —— 需要额外的辅助数组
 * 稳定性：稳定 ⭐
 */
public class MergeSort {

    /**
     * 递归版本
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int[] temp = new int[arr.length];  // 一次性分配，避免每次递归分配
        mergeSortHelper(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSortHelper(int[] arr, int left, int right, int[] temp) {
        if (left >= right) return;  // 递归终止条件

        int mid = left + (right - left) / 2;  // 防止溢出

        // 分解：左右两部分分别递归排序
        mergeSortHelper(arr, left, mid, temp);
        mergeSortHelper(arr, mid + 1, right, temp);

        // 合并：左右两部分合并（只有左 > 右 时才合并）
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 合并两个有序数组 arr[left..mid] 和 arr[mid+1..right]
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;      // 左半部分指针
        int j = mid + 1;  // 右半部分指针
        int k = left;      // 临时数组指针

        // 双指针合并
        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, left, arr, left, right - left + 1);
    }

    /**
     * 迭代版本（自底向上）
     * 不需要递归，空间上更节省（不需要递归栈）
     */
    public static void mergeSortIterative(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        int[] temp = new int[n];

        // 子数组大小从 1 开始，每次翻倍
        for (int size = 1; size < n; size *= 2) {

            // 对所有子数组进行两两合并
            for (int left = 0; left < n - size; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min(left + 2 * size - 1, n - 1);
                merge(arr, left, mid, right, temp);
            }
        }
    }

    /**
     * 求逆序对数量（LeetCode 困难题：数组中的逆序对）
     * 归并排序顺便可以解决的问题
     */
    private static long reversePairs = 0;

    public static int reversePairs(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int[] temp = new int[arr.length];
        reversePairs = 0;
        mergeSortHelperForReverse(arr, 0, arr.length - 1, temp);
        return (int) reversePairs;
    }

    private static void mergeSortHelperForReverse(int[] arr, int left, int right, int[] temp) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSortHelperForReverse(arr, left, mid, temp);
        mergeSortHelperForReverse(arr, mid + 1, right, temp);

        if (arr[mid] > arr[mid + 1]) {
            mergeForReverse(arr, left, mid, right, temp);
        }
    }

    private static void mergeForReverse(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // arr[i] > arr[j]，说明 arr[i..mid] 都大于 arr[j]
                // 构成 (mid - i + 1) 个逆序对
                reversePairs += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, left, arr, left, right - left + 1);
    }
}

/**
 * 快速排序
 * 时间复杂度：平均 O(n log n)，最坏 O(n²)
 * 空间复杂度：O(log n)（递归栈）
 * 稳定性：不稳定
 */
public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSortHelper(arr, 0, arr.length - 1);
    }

    private static void quickSortHelper(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSortHelper(arr, low, pivotIndex - 1);
            quickSortHelper(arr, pivotIndex + 1, high);
        }
    }

    /**
     * Lomuto 分区方案（以最后一个元素为基准）
     * 返回基准最终所在的位置
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选择最后一个元素作为基准
        int i = low - 1;        // i 是小于基准区域的边界

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        // 将基准放到正确位置
        swap(arr, i + 1, high);
        return i + 1;
    }

    /**
     * Hoare 分区方案（更快，减少交换次数）
     */
    private static int partitionHoare(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;

        while (true) {
            do { i++; } while (arr[i] < pivot);
            do { j--; } while (arr[j] > pivot);

            if (i >= j) return j;
            swap(arr, i, j);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // ============================================================
    // 快速排序的优化版本
    // ============================================================

    /**
     * 优化1：三数取中（Median-of-Three）
     * 避免基准选择不当导致最坏情况
     */
    public static void quickSortMedian(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSortHelperMedian(arr, 0, arr.length - 1);
    }

    private static void quickSortHelperMedian(int[] arr, int low, int high) {
        if (low < high) {
            // 三数取中：选取 left, mid, right 三个数的中位数作为基准
            int pivotIndex = medianOfThree(arr, low, high);
            // 将中位数交换到 high-1 的位置
            swap(arr, pivotIndex, high - 1);

            int pivot = arr[high - 1];
            int i = low;
            int j = high - 1;

            while (true) {
                while (arr[++i] < pivot) {}
                while (j > low && arr[--j] > pivot) {}

                if (i < j) {
                    swap(arr, i, j);
                } else {
                    break;
                }
            }

            swap(arr, i, high - 1);

            quickSortHelperMedian(arr, low, i - 1);
            quickSortHelperMedian(arr, i + 1, high);
        }
    }

    /**
     * 三数取中：返回中位数的索引
     */
    private static int medianOfThree(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;

        if (arr[low] > arr[high]) swap(arr, low, high);
        if (arr[mid] > arr[high]) swap(arr, mid, high);
        if (arr[low] > arr[mid]) swap(arr, low, mid);

        return mid;
    }

    /**
     * 优化2：随机基准（Random Pivot）
     * 避免特定输入导致的性能退化
     */
    public static void quickSortRandom(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSortHelperRandom(arr, 0, arr.length - 1);
    }

    private static void quickSortHelperRandom(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = randomPartition(arr, low, high);
            quickSortHelperRandom(arr, low, pivotIndex - 1);
            quickSortHelperRandom(arr, pivotIndex + 1, high);
        }
    }

    private static int randomPartition(int[] arr, int low, int high) {
        int randomIndex = low + (int) (Math.random() * (high - low + 1));
        swap(arr, randomIndex, high);
        return partition(arr, low, high);
    }

    /**
     * 优化3：小规模数据切换到插入排序
     * 当子数组规模小于阈值（通常 16-47）时，使用插入排序
     */
    private static final int INSERTION_THRESHOLD = 16;

    public static void quickSortOptimized(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSortHelperOptimized(arr, 0, arr.length - 1);
    }

    private static void quickSortHelperOptimized(int[] arr, int low, int high) {
        // 小规模数据用插入排序
        if (high - low < INSERTION_THRESHOLD) {
            insertionSort(arr, low, high);
            return;
        }

        int pivotIndex = partition(arr, low, high);
        quickSortHelperOptimized(arr, low, pivotIndex - 1);
        quickSortHelperOptimized(arr, pivotIndex + 1, high);
    }

    private static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }
}

/**
 * 堆排序
 * 时间复杂度：所有情况 O(n log n)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        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--) {
            swap(arr, 0, i);        // 将堆顶移到末尾
            heapify(arr, i, 0);      // 对剩余堆进行调整
        }
    }

    /**
     * Heapify：将以 i 为根节点的子树调整为大顶堆
     * @param arr 数组
     * @param n   当前堆的大小
     * @param i   待调整的节点索引
     */
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // ============================================================
    // 堆的常用操作（PriorityQueue 底层原理）
    // ============================================================

    /**
     * 插入操作：向堆中添加一个元素
     * 时间复杂度：O(log n)
     */
    public static void heapInsert(int[] arr, int index) {
        int value = arr[index];
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (arr[parent] >= value) {
                break;
            }
            arr[index] = arr[parent];
            index = parent;
        }
        arr[index] = value;
    }

    /**
     * 移除堆顶：弹出并返回堆顶元素
     * 时间复杂度：O(log n)
     */
    public static int heapPop(int[] arr, int heapSize) {
        int maxValue = arr[0];
        arr[0] = arr[heapSize - 1];
        heapify(arr, heapSize - 1, 0);
        return maxValue;
    }

    /**
     * 获取堆顶元素但不移除
     */
    public static int heapPeek(int[] arr) {
        return arr[0];
    }

    /**
     * 判断数组是否为堆
     */
    public static boolean isHeap(int[] arr, int n, int i) {
        if (i >= n / 2) return true;  // 叶子节点

        int left = 2 * i + 1;
        int right = 2 * i + 2;

        return (arr[i] >= arr[left]) &&
               (arr[i] >= arr[right]) &&
               isHeap(arr, n, left) &&
               isHeap(arr, n, right);
    }
}

import java.util.PriorityQueue;

/**
 * Top K 问题 - 使用小顶堆
 * 思路：维护一个大小为 K 的小顶堆，堆顶是 K 个数中的最小值
 * 遍历数组时，如果当前元素大于堆顶，则替换堆顶并调整堆
 *
 * 时间复杂度：O(n log k)
 * 空间复杂度：O(k)
 * 适用于：海量数据 Top K（只需要维护 K 个元素的堆）
 */
public class TopK {

    /**
     * 找出数组中最小的 K 个元素（Top K 小）
     */
    public static int[] topKSmallest(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            return new int[0];
        }

        // 使用小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : arr) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num < minHeap.peek()) {
                // 当前数比堆顶（K 个数中的最小值）更小，替换
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        int[] result = new int[k];
        int index = 0;
        for (int num : minHeap) {
            result[index++] = num;
        }
        return result;
    }

    /**
     * 找出数组中最大的 K 个元素（Top K 大）
     */
    public static int[] topKLargest(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            return new int[0];
        }

        // 使用小顶堆，堆顶是 K 个大数中的最小值
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : arr) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        int[] result = new int[k];
        int index = 0;
        for (int num : minHeap) {
            result[index++] = num;
        }
        return result;
    }

    /**
     * 使用大顶堆（适用于需要完全有序的 Top K）
     * 先用小顶堆筛选出 Top K，再用大顶堆排序
     */
    public static int[] topKSorted(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            return new int[0];
        }

        // 第一步：找出 Top K（用小顶堆）
        int[] topK = topKLargest(arr, k);

        // 第二步：对 Top K 进行排序（用大顶堆）
        int n = topK.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(topK, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(topK, 0, i);
            heapify(topK, i, 0);
        }

        return topK;
    }

    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

/**
 * 快速选择算法（QuickSelect）
 * 用于在无序数组中找出第 K 大（或第 K 小）的元素
 * 平均时间复杂度 O(n)，空间复杂度 O(1)（不计递归栈）
 */
public class QuickSelect {

    /**
     * 找出第 K 大的元素（K 从 1 开始）
     */
    public static int findKthLargest(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            throw new IllegalArgumentException("Invalid k");
        }

        return quickSelect(arr, 0, arr.length - 1, arr.length - k);  // 第 K 大 = 第 (n-k) 小
    }

    /**
     * 找出第 K 小的元素（K 从 1 开始）
     */
    public static int findKthSmallest(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            throw new IllegalArgumentException("Invalid k");
        }

        return quickSelect(arr, 0, arr.length - 1, k - 1);
    }

    private static int quickSelect(int[] arr, int low, int high, int targetIndex) {
        if (low == high) {
            return arr[low];
        }

        int pivotIndex = partition(arr, low, high);

        if (targetIndex == pivotIndex) {
            return arr[pivotIndex];
        } else if (targetIndex < pivotIndex) {
            return quickSelect(arr, low, pivotIndex - 1, targetIndex);
        } else {
            return quickSelect(arr, pivotIndex + 1, high, targetIndex);
        }
    }

    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++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 使用 BFPRT 算法（Median of Medians）
     * 最坏情况也能保证 O(n) 时间复杂度
     */
    public static int findKthLargestBFPRT(int[] arr, int k) {
        if (arr == null || k <= 0 || k > arr.length) {
            throw new IllegalArgumentException("Invalid k");
        }

        return bfprtSelect(arr, 0, arr.length - 1, arr.length - k);
    }

    private static int bfprtSelect(int[] arr, int low, int high, int targetIndex) {
        if (low == high) {
            return arr[low];
        }

        // 1. 将数组分成每组 5 个，找出每组中位数
        int pivot = getMedianOfMedians(arr, low, high);

        // 2. 使用 pivot 进行划分
        int pivotIndex = partitionAroundPivot(arr, low, high, pivot);

        if (targetIndex == pivotIndex) {
            return arr[pivotIndex];
        } else if (targetIndex < pivotIndex) {
            return bfprtSelect(arr, low, pivotIndex - 1, targetIndex);
        } else {
            return bfprtSelect(arr, pivotIndex + 1, high, targetIndex);
        }
    }

    /**
     * 获取中位数的中位数（作为划分基准）
     */
    private static int getMedianOfMedians(int[] arr, int low, int high) {
        int n = high - low + 1;
        int numOfGroups = (n + 4) / 5;  // 向上取整

        int[] medians = new int[numOfGroups];
        int index = 0;

        for (int i = 0; i < numOfGroups; i++) {
            int groupStart = low + i * 5;
            int groupEnd = Math.min(groupStart + 4, high);
            int groupSize = groupEnd - groupStart + 1;

            // 对每组进行简单排序（5 个元素，直接插入排序）
            for (int j = groupStart + 1; j <= groupEnd; j++) {
                int key = arr[j];
                int k = j - 1;
                while (k >= groupStart && arr[k] > key) {
                    arr[k + 1] = arr[k];
                    k--;
                }
                arr[k + 1] = key;
            }

            // 取出中位数（每组第 (groupSize+1)/2 个）
            medians[index++] = arr[groupStart + groupSize / 2];
        }

        // 递归求中位数数组的中位数
        if (numOfGroups == 1) {
            return medians[0];
        }
        return bfprtSelect(medians, 0, numOfGroups - 1, numOfGroups / 2);
    }

    private static int partitionAroundPivot(int[] arr, int low, int high, int pivot) {
        // 将所有等于 pivot 的元素集中到中间区域
        int left = low, right = high;
        int i = low;

        while (i <= right) {
            if (arr[i] == pivot) {
                i++;
            } else if (arr[i] < pivot) {
                swap(arr, left++, i++);
            } else {
                swap(arr, i, right--);
            }
        }

        // 返回中位数区域的位置（取中间的某个等于 pivot 的位置）
        return (left + right) / 2;
    }
}

/**
 * 计数排序
 * 适用于：整数排序，数据范围不大（最大值 - 最小值不能太大）
 * 时间复杂度：O(n + k)，k 为数据范围
 * 空间复杂度：O(k)
 * 稳定性：稳定 ⭐
 */
public class CountingSort {

    /**
     * 标准计数排序（稳定版本）
     */
    public static int[] countingSort(int[] arr) {
        if (arr == null || arr.length == 0) return arr;

        // 找出数据范围
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        int range = max - min + 1;
        int[] count = new int[range];
        int[] output = new int[arr.length];

        // 1. 统计每个元素出现的次数
        for (int num : arr) {
            count[num - min]++;
        }

        // 2. 累加计数（计算元素在输出数组中的位置）
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 3. 从后向前遍历，保证稳定性（相等元素的相对顺序不变）
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // 拷贝回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
        return arr;
    }

    /**
     * 计数排序扩展：处理负数
     */
    public static int[] countingSortWithNegative(int[] arr) {
        if (arr == null || arr.length == 0) return arr;

        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        int range = max - min + 1;
        int[] count = new int[range];
        int[] output = new int[arr.length];

        for (int num : arr) {
            count[num - min]++;
        }

        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        System.arraycopy(output, 0, arr, 0, arr.length);
        return arr;
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

/**
 * 桶排序
 * 适用于：数据分布均匀，范围可控
 * 时间复杂度：平均 O(n + k)，最坏 O(n²)（所有元素都在一个桶中）
 * 空间复杂度：O(n + k)
 * 稳定性：取决于桶内排序使用的算法
 */
public class BucketSort {

    public static void bucketSort(float[] arr) {
        if (arr == null || arr.length == 0) return;

        // 1. 创建 n 个桶
        int n = arr.length;
        LinkedList<Float>[] buckets = new LinkedList[n];

        // 2. 将元素分配到各个桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n);  // 假设数据在 [0, 1) 范围内
            if (buckets[bucketIndex] == null) {
                buckets[bucketIndex] = new LinkedList<>();
            }
            buckets[bucketIndex].add(arr[i]);
        }

        // 3. 对每个桶内部进行排序（使用插入排序或 Collections.sort）
        for (LinkedList<Float> bucket : buckets) {
            if (bucket != null) {
                Collections.sort(bucket);
            }
        }

        // 4. 合并所有桶
        int index = 0;
        for (LinkedList<Float> bucket : buckets) {
            if (bucket != null) {
                for (float num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }

    /**
     * 整数桶排序（使用计数排序作为桶内排序）
     */
    public static int[] bucketSortInt(int[] arr, int bucketSize) {
        if (arr == null || arr.length == 0) return arr;

        // 找出数据范围
        int max = arr[0], min = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        // 创建桶
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 分配元素到桶
        for (int num : arr) {
            int bucketIndex = (num - min) / bucketSize;
            buckets[bucketIndex].add(num);
        }

        // 对每个桶排序并合并
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            if (bucket.size() > 0) {
                Collections.sort(bucket);
                for (int num : bucket) {
                    arr[index++] = num;
                }
            }
        }

        return arr;
    }
}

/**
 * 基数排序
 * 适用于：非负整数或可以映射为非负整数的数据
 * 时间复杂度：O(d * (n + k))，d 为位数，k 为进制
 * 空间复杂度：O(n + k)
 * 稳定性：稳定
 */
public class RadixSort {

    /**
     * LSD（Least Significant Digit）基数排序：从低位开始
     */
    public static void radixSortLSD(int[] arr) {
        if (arr == null || arr.length == 0) return;

        // 找出最大值，确定位数
        int max = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
        }

        // 从低位到高位，依次进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];  // 0-9 十个桶

        // 统计每个桶的元素个数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 累加计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 从后向前遍历，保证稳定性
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        System.arraycopy(output, 0, arr, 0, n);
    }

    /**
     * MSD（Most Significant Digit）基数排序：从高位开始
     * 可以用递归实现，适合字符串排序
     */
    public static void radixSortMSD(String[] arr) {
        if (arr == null || arr.length == 0) return;
        radixSortMSDHelper(arr, 0, arr.length - 1, 0);
    }

    private static void radixSortMSDHelper(String[] arr, int low, int high, int digitIndex) {
        if (low >= high || digitIndex >= arr[low].length()) {
            return;
        }

        int[] count = new int[256 + 1];  // ASCII 字符 + 1 表示字符串结束
        String[] temp = new String[high - low + 1];

        // 统计每个桶的元素个数
        for (int i = low; i <= high; i++) {
            int d = charAt(arr[i], digitIndex) + 1;  // +1 区分字符串结束
            count[d]++;
        }

        // 累加计数
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 分配到临时数组
        for (int i = high; i >= low; i--) {
            int d = charAt(arr[i], digitIndex) + 1;
            temp[--count[d]] = arr[i];
        }

        // 拷贝回原数组
        for (int i = low; i <= high; i++) {
            arr[i] = temp[i - low];
        }

        // 递归处理每个桶
        for (int i = 0; i < count.length - 1; i++) {
            if (count[i + 1] > count[i]) {
                radixSortMSDHelper(arr, low + count[i], low + count[i + 1] - 1, digitIndex + 1);
            }
        }
    }

    /**
     * 获取字符串指定位置的字符（字符串长度不够时返回 -1）
     */
    private static int charAt(String s, int index) {
        if (index >= s.length()) {
            return -1;
        }
        return s.charAt(index);
    }

    /**
     * 处理负数的基数排序
     */
    public static void radixSortWithNegative(int[] arr) {
        if (arr == null || arr.length == 0) return;

        // 将数组分为负数和非负数两部分
        int max = Math.abs(arr[0]);
        for (int num : arr) {
            max = Math.max(max, Math.abs(num));
        }

        int[] negative = new int[arr.length];
        int[] positive = new int[arr.length];
        int negCount = 0, posCount = 0;

        for (int num : arr) {
            if (num < 0) {
                negative[negCount++] = -num;  // 取绝对值
            } else {
                positive[posCount++] = num;
            }
        }

        // 分别对负数和非负数进行基数排序
        int[] negSorted = new int[negCount];
        int[] posSorted = new int[posCount];

        System.arraycopy(negative, 0, negSorted, 0, negCount);
        System.arraycopy(positive, 0, posSorted, 0, posCount);

        if (negCount > 0) {
            radixSortLSD(negSorted);
            // 负数结果取反并反转顺序
            for (int i = 0; i < negCount; i++) {
                arr[i] = -negSorted[negCount - 1 - i];
            }
        }

        if (posCount > 0) {
            radixSortLSD(posSorted);
            System.arraycopy(posSorted, 0, arr, negCount, posCount);
        }
    }
}

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

/**
 * 方法1：简单遍历 O(n)
 * 检查是否严格递增
 */
public boolean isSortedAscending(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

/**
 * 方法2：判断是升序还是降序
 * 返回值：1=升序，-1=降序，0=无序
 */
public int checkSortOrder(int[] arr) {
    if (arr == null || arr.length < 2) return 1;

    boolean ascending = true, descending = true;

    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] < arr[i + 1]) descending = false;
        if (arr[i] > arr[i + 1]) ascending = false;
    }

    if (ascending) return 1;
    if (descending) return -1;
    return 0;
}

/**
 * 方法3：近乎有序的判断
 * 如果逆序对数量很少（如 < n * k），可以认为是近乎有序
 */
public boolean isNearlySorted(int[] arr, int k) {
    // 逆序对数量 <= k 时，可以通过 k 次相邻交换完成排序
    int inversions = 0;
    for (int i = 0; i < arr.length - 1 && inversions <= k; i++) {
        if (arr[i] > arr[i + 1]) {
            inversions++;
            swap(arr, i, i + 1);
        }
    }
    return inversions <= k;
}