public class BubbleSort {
    public static void bubbleSort(int[] arr) {
cheon       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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
            }
            }
            // 如果没有进行交换，说明已经排好序，提前退出循环
            if (!swapped) {
            break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

public class SelectionSort {
    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;
            }
            }
            // 交换找到的最小值与当前元素
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前要插入的元素
            int j = i - 1;
         
            // 向前查找比当前元素大的元素，依次向后移动
            while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
            }
            // 找到合适的位置插入
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

public class QuickSort {

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
        quickSort(array, 0, array.length - 1);
        System.out.println("排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }

    // 快速排序的主方法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);  // 排序左半部分
            quickSort(array, pivotIndex + 1, high); // 排序右半部分
        }
    }

    // 分区方法，选择一个基准点并进行分区
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high]; // 选择最右边的元素作为基准点
        int i = low - 1;         // i 是小于基准点的区域的索引

        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
            i++;
            swap(array, i, j); // 交换小于基准点的元素到左边
            }
        }

        swap(array, i + 1, high); // 将基准点放到正确的位置
        return i + 1;             // 返回基准点的位置
    }

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

public class ShellSort {

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
        shellSort(array);
        System.out.println("排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }

    // 希尔排序方法
    public static void shellSort(int[] array) {
        int n = array.length;
        
        // 初始增量设置为数组长度的一半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个增量值进行插入排序
            for (int i = gap; i < n; i++) {
            int temp = array[i];
            int j = i;

            // 对当前元素进行插入排序
            while (j >= gap && array[j - gap] > temp) {
                    array[j] = array[j - gap];
                    j -= gap;
            }
            array[j] = temp;
            }
        }
    }
}

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
            } else {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

public class HeapSort {

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 5, 62, 32, 7, 9};
        heapSort(array);
        System.out.println("排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }

    // 堆排序方法
    public static void heapSort(int[] array) {
        int n = array.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }

        // 从堆中提取元素
        for (int i = n - 1; i > 0; i--) {
            // 将根节点（最大值）交换到数组末尾
            swap(array, 0, i);
            // 重新调整堆
            heapify(array, i, 0);
        }
    }

    // 调整堆的方法，使以 i 为根的子树满足最大堆性质
    private static void heapify(int[] array, int n, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 如果左子节点更大
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }

        // 如果右子节点更大
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点
        if (largest != i) {
            swap(array, i, largest);
            // 递归调整子树
            heapify(array, n, largest);
        }
    }

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

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        // 找到数组中的最大值
        int max = Arrays.stream(array).max().orElse(Integer.MAX_VALUE);

        // 创建计数数组并初始化
        int[] count = new int[max + 1];

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

        // 将计数数组转换为累积计数数组
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // 根据累积计数数组生成排序后的结果
        int[] sortedArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            sortedArray[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // 将排序结果复制回原数组
        System.arraycopy(sortedArray, 0, array, 0, array.length);
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原数组: " + Arrays.toString(array));

        countingSort(array);

        System.out.println("排序后: " + Arrays.toString(array));
    }
}

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

public class BucketSort {

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

        // 创建桶
        int numberOfBuckets = array.length;
        List<Float>[] buckets = new ArrayList[numberOfBuckets];
        for (int i = 0; i < numberOfBuckets; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素分配到桶中
        for (float num : array) {
            int bucketIndex = (int) (num * numberOfBuckets); // 确定桶的位置
            buckets[bucketIndex].add(num);
        }

        // 对每个桶内的元素进行排序
        for (List<Float> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 合并所有桶的排序结果
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float num : bucket) {
            array[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        float[] array = {0.42f, 0.32f, 0.73f, 0.25f, 0.67f, 0.48f, 0.12f, 0.89f, 0.94f, 0.36f};
        System.out.println("原数组: ");
        for (float num : array) {
            System.out.print(num + " ");
        }
        System.out.println();

        bucketSort(array);

        System.out.println("排序后: ");
        for (float num : array) {
            System.out.print(num + " ");
        }
    }
}

import java.util.*;

public class RadixSortWithHashMap {

    // 获取数组中最大值，以确定排序的轮数
    private static int getMax(int[] array) {
        int max = array[0];
        for (int num : array) {
            if (num > max) {
            max = num;
            }
        }
        return max;
    }

    // 使用 HashMap 实现计数排序
    private static void countingSortWithHashMap(int[] array, int exp) {
        // HashMap 用于存储每个位的对应列表
        Map<Integer, List<Integer>> countMap = new HashMap<>();

        // 初始化 HashMap 的键值对（键为 0-9 的数字，值为对应的列表）
        for (int i = 0; i < 10; i++) {
            countMap.put(i, new ArrayList<>());
        }

        // 根据每一位的数字，将元素放入对应的 HashMap 列表中
        for (int num : array) {
            int digit = (num / exp) % 10;
            countMap.get(digit).add(num);
        }

        // 将 HashMap 中的元素按键的顺序（从 0 到 9）重新写回数组
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int num : countMap.get(i)) {
            array[index++] = num;
            }
        }
    }

    // 主基数排序函数
    public static void radixSort(int[] array) {
        // 找到最大数以确定轮数
        int max = getMax(array);

        // 从个位开始对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortWithHashMap(array, exp);
        }
    }

    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("原数组: " + Arrays.toString(array));

        radixSort(array);

        System.out.println("排序后: " + Arrays.toString(array));
    }
}