【Java数据结构】七大排序+计数排序+基数排序+桶排序 超详细讲解

这个问题涉及到很多内容，包括七大排序算法（插入排序、冒泡排序、选择排序、归并排序、快速排序、堆排序、基数排序），以及计数排序和桶排序。由于篇幅所限，我将提供每种排序算法的核心思想和Java代码实现。

1. 插入排序

插入排序的核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

Java代码实现：

public void insertionSort(int[] arr) {
    int i, j, key;
    for (i = 1; i < arr.length; i++) {
        key = arr[i];
        j = i - 1;
 
        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

2. 快速排序

快速排序使用分治策略，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。

Java代码实现：

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 获取分区后的枢纽位置
        int pivotIndex = partition(arr, low, high);
 
        // 分别对枢纽左右两边进行递归排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}
 
private int partition(int[] arr, int low, int high) {
    // 选择一个枢纽值，通常是数组的第一个元素
    int pivot = arr[low];
 
    while (low < high) {
        // 在右边找到第一个小于枢纽值的元素
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high]; // 将找到的元素放到左边
 
        // 在左边找到第一个大于枢纽值的元素
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low]; // 将找到的元素放到右边
    }
 
    // 最终将枢纽值放到低位（左边的高位）
    arr[low] = pivot;
 
    // 返回枢纽位置
    return low;
}

3. 计数排序

计数排序是一种稳定的线性时间排序算法，适用于一定范围内的整数排序。

Java代码实现：

public void countingSort(int[] arr) {
    // 找出数组中的最大值和最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
 
    // 初始化计数数组
    int[] countArray = new int[max - min + 1];
 
    // 计数
    for (int i = 0; i < arr.length; i++) {