import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortingAlgorithms {

    // 快速排序
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

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

    // 归并排序
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            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 n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // 选择排序
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    // 桶排序
    public static void bucketSort(float[] arr) {
        int n = arr.length;
        if (n <= 0) return;

        // 创建 n 个桶
        List<List> buckets = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n);
            buckets.get(bucketIndex).add(arr[i]);
        }

        // 对每个桶进行排序
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets.get(i));
        }

        // 将排序后的元素放回原数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (float num : buckets.get(i)) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        // 快速排序测试
        int[] quickArr = {10, 7, 8, 9, 1, 5};
        quickSort(quickArr, 0, quickArr.length - 1);
        System.out.println("快速排序结果: " + Arrays.toString(quickArr));

        // 归并排序测试
        int[] mergeArr = {12, 11, 13, 5, 6, 7};
        mergeSort(mergeArr, 0, mergeArr.length - 1);
        System.out.println("归并排序结果: " + Arrays.toString(mergeArr));

        // 选择排序测试
        int[] selectionArr = {64, 25, 12, 22, 11};
        selectionSort(selectionArr);
        System.out.println("选择排序结果: " + Arrays.toString(selectionArr));

        // 桶排序测试
        float[] bucketArr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f};
        bucketSort(bucketArr);
        System.out.println("桶排序结果: " + Arrays.toString(bucketArr));
    }
}

代码说明：

1. 快速排序（Quick Sort）：选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于基准元素，右边部分的元素都大于基准元素。递归地对左右两部分进行排序。
2. 归并排序（Merge Sort）：将数组分成两个子数组，分别对两个子数组进行排序。合并两个已排序的子数组。
3. 选择排序（Selection Sort）：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。重复步骤 1，直到所有元素均排序完毕。
4. 桶排序（Bucket Sort）：将数组元素分配到多个桶中。对每个桶中的元素进行排序。将排序后的元素依次放回原数组。

复杂度分析：

• 快速排序：平均时间复杂度为 ，最坏时间复杂度为 。
• 归并排序：时间复杂度为 。
• 选择排序：时间复杂度为 。
• 桶排序：平均时间复杂度为 ，其中 是桶的数量。