十大经典排序算法

交换类：通过元素之间的两两交换来实现排序 插入类：将数分为2部分，依次将无序的数插入到有序的数列中 选择类：从待排序数列中找到最小值或者最大值元素，放到已拍好序的序列后面

计数排序和基数排序可以认为是桶排序的一种特殊实现，都不是通过元素之间的比较来实现排序的

1. 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

排序原理：

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大
3. 每次比较得到的最大值下次就不用再比较了

实现代码:

• 时间复杂度分析：O(n^2)
• 空间复杂度分析：O(1)
• 稳定性：稳定

public class Test3 {
    /**
     * 实现冒泡排序的方法。
     * @param array 要排序的整数数组。
     */
    public static void bubbleSort(int[] array) {
        // 遍历整个数组。
        for (int i = 0; i < array.length - 1; i++) {
            // 优化冒泡排序。
            // 这里使用一个标志变量来判断如果数组已经有序，则直接退出循环。
            boolean flg = false;
            // 内层循环用于比较和交换相邻的元素。
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 如果一个元素大于它相邻的下一个元素，则交换它们。
                if(array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    // 如果发生了交换，则将标志变量设置为true。
                    flg = true;
                }
            }
            // 如果某一轮的比较中没有发生任何交换，说明数组已经有序，直接跳出循环。
            if(!flg) {
                break;
            }
        }
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param j 第一个元素的索引。
     * @param i 第二个元素的索引。
     */
    private static void swap(int[] array, int j, int i) {
        // 临时变量用于存储要交换的元素。
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array ={9,8,7,6,5,4,3,2,1};
        // 调用冒泡排序方法对数组进行排序。
        bubbleSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

2. 直接插入排序

直接插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

排序原理：

1.把所有的元素分为两组，已经排序的和未排序的；

2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；

3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

步骤:

1. 从数组的第一个元素开始，可以认为它自身已经被排序。

2. 选择下一个元素（记为tem），并从已排序的序列的末尾开始向前扫描。

3. 如果遇到的已排序元素大于tem，则将该元素向后移动一位。

4. 重复上述过程，直到找到一个已排序的元素小于等于tem。

5. 将tem插入到这个位置之后。如果所有已排序元素都大于tem，则将tem插入在数组的开头。

6. 对未排序的每个元素重复上述步骤

• 时间复杂度分析：
  • 最坏情况下为O(N*2)，此时待排序列为逆序或接近逆序，这意味着每次插入操作都需要将已排序部分的所有元素向后移动。
  • 最好情况下为O(N)，此时待排序列为升序或接近升序，这意味着每次插入都不需要移动已排序部分的任何元素，仅需比较一次即可找到插入位置。
• 空间复杂度分析：只是开辟了一个 tmp 的变量 i，j，常数，即空间复杂度：O(1)
• 稳定性：直接插入排序是稳定的。在排序过程中，相等的元素不会改变彼此的顺序。
• 该排序再数据越接近有序的情况，时间效率越高。

public class Test5 {
    /**
     * 实现直接插入排序的方法。
     * @param arr 要排序的整数数组。
     */
    public static void insertSort(int[] arr) {
        // 从第二个元素开始遍历数组，因为第一个元素自身就认为是已排序的。
        for (int i = 1; i < arr.length; i++) {
            // 将当前要插入的元素存储在tmp中。
            int tmp = arr[i];
            int j;
            // 从当前元素的前一个元素开始向前遍历，寻找插入位置。
            for (j = i - 1; j >= 0 ; j--) {
                // 如果当前元素（arr[j]）大于要插入的元素（tmp），
                // 则将当前元素向后移动一个位置。
                if(arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    // 找到了一个比tmp小的元素，跳出循环。
                    break;
                }
            }
            // 将tmp放到找到的位置的后面（j+1的位置）。
            arr[j + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array ={9,8,7,6,5,4,3,2,1};
        // 调用直接插入排序方法对数组进行排序。
        insertSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

3. 希尔排序

希儿排序是插入排序的优化，在排序过程中待排序数组根据gap增量进行插入排序，使子区间有序从而使整个待排序数组越来越有序。

● 具体思路

​ ① 设置gap增量，这里gap的初始值为待排序数组的元素个数 / 2，每次以2倍的数量减少。

​ ② 原本的插入排序间隔是1，这里每一组数据的排序间隔是gap，用gap进行分组排序。

​ ③ gap越大，每组的元素个数就越少，反之，每组的元素个数越多。直到gap减少到1，整个数组变为一个序列，此时进行一次普通的插入排序，因为数组已经部分有序，所以效率较高。

注：希尔排序避免了当待排序数组为逆序时，直接插入排序达到最坏时间复杂度O(N^2)的情况，希尔排序是先根据gap增量对 待排序数组 进行预排序，最基本排序思路还是依次取出[gap,arr.length - 1]位置的元素在对应组内的有序区间中找到插入位置插入，所以说希尔排序是插入排序的优化。

静图分析:

动图如下：

实现代码:

• 时间复杂度分析：希尔排序的时间复杂度不好分析， 这里我们就大概记一下，约为 O(n^1.3)，感兴趣的话，可以查阅一下相关书籍。
• 空间复杂度分析：仍然开辟的是常数个变量，空间复杂度为 O(1)
• 稳定性：不稳定

public class Test4 {
    /**
     * 实现希尔排序的方法。
     * @param array 要排序的整数数组。
     */
    public static void shellSort(int[] array) {
        // 初始化间隔gap为数组长度的一半。
        int gap = array.length >> 1; // 等价于 gap = array.length / 2;
        // 当gap大于1时，进行分组插入排序。
        while (gap > 1) {
            // 对每个分组进行插入排序。
            shell(array, gap);
            // 更新gap的值，每次减半。
            gap >>= 1; // 等价于 gap /= 2;
        }
        // 当gap为1时，进行最终的插入排序，此时整个数组被视为一个分组。
        shell(array, 1);
    }

    /**
     * 希尔排序的内部方法，用于对指定gap的分组进行插入排序。
     * @param array 数组。
     * @param gap 当前排序的间隔。
     */
    private static void shell(int[] array, int gap) {
        // 从第gap个元素开始，逐个对每个分组进行插入排序。
        for (int i = gap; i < array.length; i++) {
            // 保存当前要插入的元素。
            int tmp = array[i];
            int j = i - gap;
            // 遍历当前分组中的所有元素。
            for (; j >= 0; j -= gap) {
                // 如果当前元素大于tmp，将其向后移动gap个位置。
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    // 找到了插入的位置，跳出循环。
                    break;
                }
            }
            // 将tmp插入到找到的位置。
            array[j + gap] = tmp;
        }
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array ={9,8,7,6,5,4,3,2,1};
        // 调用希尔排序方法对数组进行排序。
        shellSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

4. 选择排序

选择排序是一种简单直观的排序方法。

排序原理：

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处 的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
2. 交换第一个索引处和最小值所在的索引处的值

4.1 选择排序优化前：

• 时间复杂度分析： O(n^2)
• 空间复杂度分析：O(1)
• 稳定性：不稳定 实际开发中用的不多

public class Test6 {
    /**
     * 实现选择排序的方法。
     * @param arr 要排序的整数数组。
     */
    public static void selectSort(int[] arr) {
        // 边界检查：如果数组为空或只有一个元素，则无需排序。
        if (arr == null || arr.length < 2) {
            return;
        }

        // 外层循环：遍历数组，每次选出一个最小元素的位置。
        for (int i = 0; i < arr.length - 1; i++) {
            // min变量保存该趟比较过程中，最小元素所对应的索引，
            // 先假设前面的元素为最小元素
            int minIndex = i;
            // 内层循环：从i+1位置开始，找出剩余元素中的最小值。
            for (int j = i + 1; j < arr.length; j++) {
                //如果后面的元素小，将后面元素的索引更新为最小值的索引
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //然后交换此次查找到的最小值和原始的最小值
            swap(arr, i, minIndex);
        }
    }

    /**
     * 交换数组中的两个元素。
     * @param arr 数组。
     * @param i 第一个元素的索引。
     * @param j 第二个元素的索引。
     */
    public static void swap(int[] arr, int i, int j) {
        // 临时变量用于交换两个元素。
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array ={9,8,7,6,5,4,3,2,1};
        // 调用选择排序方法对数组进行排序。
        selectSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

4.2 选择排序优化后：

选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。第一次选择最大值与最小值，过程如下

实现代码:时间复杂度:O(N^2) 面试两种写法都差不多

public class Test7 {
    /**
     * 实现优化后的选择排序方法。
     * @param array 要排序的整数数组。
     */
    public void selectSort(int[] array) {
        // 初始化左右指针，分别指向数组的起始和结束位置。
        int left = 0;
        int right = array.length - 1;

        // 当左指针小于右指针时，进行排序操作。
        while (left < right) {
            // 初始化最大值和最小值的索引为当前左指针位置。
            int maxIndex = left;
            int minIndex = left;

            // 遍历当前未排序的数组部分。
            for (int i = left + 1; i <= right; i++) {
                // 更新最大值的索引。
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
                // 更新最小值的索引。
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
            }

            // 将找到的最小值交换到当前未排序部分的最左边。
            swap(array, minIndex, left);

            // 如果最大值的索引是left，由于最小值已经与left交换，因此更新最大值的索引。
            if (maxIndex == left) {
                maxIndex = minIndex;
            }

            // 将找到的最大值交换到当前未排序部分的最右边。
            swap(array, maxIndex, right);

            // 缩小未排序数组的范围。
            left++;
            right--;
        }
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param i 第一个元素的索引。
     * @param j 第二个元素的索引。
     */
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

5. 堆排序

排序思想：

1. 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2. 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3. 将剩余的n-1个数再调整为大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

实现代码:

• 时间复杂度分析：建堆的时间复杂度优先级队列那期有说过为 O(n)，排序调整堆的时候，一共要调整 n-1 次，每次向下调整的时间复杂度是 logn，所以即 logn(n - 1)，即 O(nlogn)，加上面建堆的时间复杂度：O(n) + O(nlogn)，最终时间复杂度也就是：O(n*logn)。
• 空间复杂度分析：O(1)
• 稳定性：不稳定

public class Test2 {
    /**
     * 实现堆排序的方法。
     * @param array 要排序的整数数组。
     */
    public static void heapSort(int[] array) {
        // 第一步：建立大根堆。
        createHeap(array); // 时间复杂度O(N)

        int end = array.length - 1;
        // 第二步：进行堆排序。
        // 通过不断将堆顶元素（最大值）与数组末尾元素交换，并减小堆的大小。
        // 时间复杂度O(N*log(N))
        while(end > 0) {
            // 将堆顶元素（最大值）与数组末尾元素交换。
            swap(array, 0, end);
            // 对堆顶元素进行向下调整，重新形成大根堆。
            // 此时数组末尾的元素是最大值，不参与堆的调整。
            shiftDown(array, 0, end);
            end--;
        }
    }

    /**
     * 创建大根堆。
     * @param array 数组。
     */
    private static void createHeap(int[] array) {
        // 从最后一个非叶子节点开始，向前进行向下调整。
        for (int p = (array.length - 1 - 1) / 2; p >= 0 ; p--) {
            shiftDown(array, p, array.length);
        }
    }    
    
    /**
     * 向下调整方法，用于维护大根堆的性质。
     * @param array 数组。
     * @param root 要调整的根节点下标。
     * @param len 堆的大小。
     */
    private static void shiftDown(int[] array, int root, int len) {
        // child指向root的左子节点。
        int child = 2 * root + 1;
        while(child < len) {
            // 选择root的左右子节点中较大者。
            if(child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            // 如果子节点大于根节点，则交换，并继续向下调整。
            if(array[child] > array[root]) {
                swap(array, child, root);
                root = child;
                child = 2 * root + 1;
            } else {
                // 如果根节点大于子节点，停止调整。
                break;
            }
        }
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param child 第一个元素的下标。
     * @param root 第二个元素的下标。
     */
    private static void swap(int[] array, int child, int root) {
        int tmp = array[child];
        array[child] = array[root];
        array[root] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array = {9,8,7,6,5,4,3,2,1};
        // 调用堆排序方法对数组进行排序。
        heapSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

6. 快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；
2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

6.1 hoare版本(左右指针法)

hoare法划分思路：

1. 选择基准值（Pivot）:
   • hoare法首先从数组中选择一个元素作为基准值。通常选择第一个元素或最后一个元素，但也可以是任意元素。
2. 左右指针的移动:
   • 如果基准值取自左端，则应先移动右指针；如果基准值取自右端，则应先移动左指针。这是为了确保交换操作能保持排序的正确性。
3. 指针移动和交换:
   • 右指针向左移动，直到找到小于基准值的元素；左指针向右移动，直到找到大于基准值的元素。然后交换这两个元素。这个过程一直持续，直到左右指针相遇。
4. 分区（Partitioning）:
   • 当左右指针相遇时，将相遇点的元素与基准值交换。这样，基准值左侧的所有元素都小于基准值，右侧的所有元素都大于基准值。
5. 递归排序:
   • 接下来对基准值左右两侧的子序列递归地应用同样的过程。递归继续，直到每个子序列只包含一个元素或为空（左右序列不存在时），便停止操作，此时数组变得有序。

单趟动图如下： ​

实现代码:

public class Test8 {
    /**
     * 快速排序的主方法。
     * @param array 要排序的整数数组。
     */
    public static void quickSort(int[] array) {
        // 对整个数组进行快速排序。
        quick(array, 0, array.length - 1);
    }

    /**
     * 快速排序的递归函数。
     * @param array 数组。
     * @param start 排序的起始位置。
     * @param end 排序的结束位置。
     */
    public static void quick(int[] array, int start, int end) {
        // 递归终止条件，当起始位置大于等于结束位置时。
        if (start >= end) {
            return;
        }
        // 对数组进行划分，返回划分元素的位置。
        int pivot = partition(array, start, end);
        // 对划分元素左边的部分进行快速排序。
        quick(array, start, pivot - 1);
        // 对划分元素右边的部分进行快速排序。
        quick(array, pivot + 1, end);
    }

    /**
     * Hoare划分方法，用于快速排序中的划分。
     * @param array 数组。
     * @param left 划分的起始位置。
     * @param right 划分的结束位置。
     * @return 划分元素的最终位置。
     */
    private static int partition(int[] array, int left, int right) {
        // 选取左边界作为基准值。
        int tmp = array[left];
        int i = left;
        // 进行一次划分。
        while (left < right) {
            // 从右边开始，寻找比基准值小的元素。
            while (left < right && array[right] >= tmp) {
                right--;
            }
            // 从左边开始，寻找比基准值大的元素。
            while (left < right && array[left] <= tmp) {
                left++;
            }
            // 交换这两个元素。
            swap(array, left, right);
        }
        // 最后将基准值交换到中间位置。
        swap(array, left, i);
        // 返回划分元素的位置。
        return left;
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param i 第一个元素的索引。
     * @param j 第二个元素的索引。
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        // 调用快速排序方法对数组进行排序。
        quickSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

6.2 挖坑法

思路： 挖坑法思路与hoare版本(左右指针法)思路类似

1. 选择基准值并挖坑:
   • 首先选择一个元素作为基准值（pivot），通常是数组的第一个或最后一个元素。该位置的元素被取出，留下一个“坑”。
2. 左右指针移动:
   • 定义两个指针left和right，分别从数组的两端开始向中间移动。
   • 若基准值选在最左边，right指针先移动；若基准值选在最右边，则left指针先移动。
3. 移动过程和填坑:
   • right指针向左移动，直到找到一个小于基准值的元素，然后将该元素填入左边的“坑”中，这时right指针所指位置形成新的“坑”。
   • 接着left指针向右移动，直到找到一个大于基准值的元素，然后将该元素填入右边的“坑”中，这时left指针所指位置形成新的“坑”。
   • 这个过程交替进行，直到left和right指针相遇。
4. 填入基准值并递归:
   • 当left和right相遇时，将基准值填入最后的“坑”中。此时，基准值左边的所有元素都小于它，右边的所有元素都大于它。
   • 然后对基准值左右两侧的子数组递归地重复上述过程。
5. 完成排序:
   • 重复上述过程，直到所有的子数组都被排序，最终整个数组变得有序。

单趟动图如下： ​

实现代码:

public class Test7 {
    /**
     * 快速排序的主方法。
     * @param array 要排序的整数数组。
     */
    public static void quickSort(int[] array) {
        // 对整个数组进行快速排序。
        quick(array, 0, array.length - 1);
    }

    /**
     * 快速排序的递归方法。
     * @param array 数组。
     * @param start 排序的起始位置。
     * @param end 排序的结束位置。
     */
    private static void quick(int[] array, int start, int end) {
        // 递归结束条件：起始位置不小于结束位置。
        if (start >= end) {
            return;
        }
        // 对数组进行划分，返回划分元素的位置。
        int pivot = partition(array, start, end);
        // 对划分元素左边的部分进行快速排序。
        quick(array, start, pivot - 1);
        // 对划分元素右边的部分进行快速排序。
        quick(array, pivot + 1, end);
    }

    /**
     * 挖坑法进行划分的方法。
     * @param array 数组。
     * @param left 划分的起始位置。
     * @param right 划分的结束位置。
     * @return 划分元素的最终位置。
     */
    private static int partition(int[] array, int left, int right) {
        // 选取左边界的元素作为基准值，并挖一个坑。
        int tmp = array[left];
        while (left < right) {
            // 从右向左找小于基准值的元素填坑。
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            // 从左向右找大于或等于基准值的元素填坑。
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        // 将基准值填回最后一个坑。
        array[left] = tmp;
        return left;
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param i 第一个元素的索引。
     * @param j 第二个元素的索引。
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        // 调用快速排序方法对数组进行排序。
        quickSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

6.3 前后指针法

思路：

1. 选择基准值（Pivot）:
   • 选择数组中的一个元素作为基准值（key），通常是第一个或最后一个元素。这个值用于划分数组。
2. 初始化指针:
   • prev指针初始化为序列的起始位置（left），cur指针初始化为prev + 1。
3. 指针移动和交换:
   • 遍历数组时，cur指针不断向后移动。
   • 当cur指向的元素小于基准值时，prev指针先向后移动一位，然后交换prev和cur指向的元素，之后cur指针继续移动。
   • 当cur指向的元素大于或等于基准值时，cur指针直接向后移动。
4. 划分完成:
   • 当cur指针到达数组的末端时，交换prev+1位置上的元素和基准值。此时，基准值左侧的所有元素都小于它，右侧的所有元素都大于它。
5. 递归排序:
   • 对基准值左右两侧的子数组重复上述过程，直到每个子序列只包含一个元素或为空。
6. 完成排序:
   • 这个过程重复进行，直到整个数组变得有序。

实现代码:

public class Test9 {
    /**
     * 快速排序的主方法。
     * @param array 要排序的整数数组。
     */
    public static void quickSort(int[] array) {
        // 对整个数组进行快速排序。
        quick(array, 0, array.length - 1);
    }

    /**
     * 快速排序的递归函数。
     * @param array 数组。
     * @param start 排序的起始位置。
     * @param end 排序的结束位置。
     */
    public static void quick(int[] array, int start, int end) {
        // 递归终止条件，当起始位置大于等于结束位置时。
        if (start >= end) {
            return;
        }
        // 对数组进行划分，返回划分元素的位置。
        int pivot = partition(array, start, end);
        // 对划分元素左边的部分进行快速排序。
        quick(array, 0, pivot - 1);
        // 对划分元素右边的部分进行快速排序。
        quick(array, pivot + 1, end);
    }

    /**
     * 前后指针法进行划分的方法。
     * @param array 数组。
     * @param left 划分的起始位置。
     * @param right 划分的结束位置。
     * @return 划分元素的最终位置。
     */
    private static int partition(int[] array, int left, int right) {
        // prev作为前指针，初始化为left。
        int prev = left;
        // cur作为后指针，初始化为left+1。
        int cur = left + 1;
        // 遍历直到cur到达数组的末端。
        while (cur <= right) {
            // 如果cur指向的元素小于基准值，并且prev和cur不指向同一个元素，
            // 则交换prev和cur指向的元素，并移动prev指针。
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            // 移动cur指针。
            cur++;
        }
        // 将基准值与prev指针指向的元素交换。
        swap(array, prev, left);
        return prev;
    }

    /**
     * 交换数组中的两个元素。
     * @param array 数组。
     * @param i 第一个元素的索引。
     * @param j 第二个元素的索引。
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        // 初始化一个待排序的数组。
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        // 调用快速排序方法对数组进行排序。
        quickSort(array);
        // 打印排序后的数组。
        System.out.println(Arrays.toString(array));
    }
}

6.4 快速排序的优化

通过上面的测试我们发现，当给一组有序且很大的数据时，如果用快速排序就会造成栈溢出，溢出的原因就是因为快速排序在递归的时候要开辟内存空间，而递归的次数受树高度的影响。给定一组有序序列，在快排时就等同于只有左树或者只有右树，这样递归的次数就是这个序列的长度，因此给定的序列越大，递归次数越多就会越容易栈溢出。

6.4.1 三数取中法(优化一)（对排序本身分割数据的一种优化）

1. 三数取中法:

   • 该方法选择左端、中间和右端三个位置的元素，然后取这三个元素的中值作为快速排序的基准值。这样做可以减少在极端情况下（如数组已经有序）快速排序性能下降的风险。

     传统快速排序对于基准值的选择，通常是第一个元素或最后一个元素，但是在极端情况下，如完全有序的数组，如果总是选择最左边或最右边的元素作为基准值，每次划分只能排除一个元素，导致递归次数极多，效率极低。

2. 改善递归深度:

   • 通过更好地选择基准值，三数取中法能够使得划分更加均衡，从而减少递归的深度，避免栈溢出。

3. 性能提升:

   • 在最坏的情况下（比如当数组已经有序时），传统快速排序的性能会退化到 O(n^2)。而使用三数取中法，可以使得快速排序在这类情况下仍然保持较高的效率，接近于平均情况的时间复杂度 O(n log n)。

实现代码:

public class Test9 {
    /**
     * 快速排序的优化版本。
     * @param array 要排序的整数数组。
     */
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    /**
     * 三数取中法找基准值。
     * @param array 数组。
     * @param left 划分的起始位置。
     * @param right 划分的结束位置。
     * @return 三数中值的下标。
     */
    private int medianOfThreeIndex(int[] array, int left, int right) {
    // 计算中间元素的下标
    int mid = left + (right - left) >>> 1;

    // 以下逻辑旨在从 left, mid, right 三个位置中找到中间值的下标
    if(array[left] < array[right]) {
        // 如果左端小于右端
        if(array[mid] < array[left]) {
            // 如果中间值小于左端，则左端是中间值
            return left;
        } else if(array[mid] > array[right]) {
            // 如果中间值大于右端，则右端是中间值
            return right;
        } else {
            // 否则中间值即为中间值
            return mid;
        }
    } else {
        // 如果左端大于右端
        if(array[mid] > array[left]) {
            // 如果中间值大于左端，则左端是中间值
            return left;
        } else if(array[mid] < array[right]) {
            // 如果中间值小于右端，则右端是中间值
            return right;
        } else {
            // 否则中间值即为中间值
            return mid;
        }
    }
}

    /**
     * 快速排序的递归函数。
     * @param array 数组。
     * @param left 排序的起始位置。
     * @param right 排序的结束位置。
     */
    public void quick(int[] array, int left, int right) {
        if(left >= right) return;

        // 通过三数取中法选择基准值，并将基准值与左边界交换。
        int index = medianOfThreeIndex(array, left, right);
        swap(array, left, index);

        // 对数组进行划分。
        int pivot = partitionHole(array, left, right);

        // 对划分元素左边的部分进行快速排序。
        quick(array, left, pivot - 1);
        // 对划分元素右边的部分进行快速排序。
        quick(array, pivot + 1, right);
    }

    // 这里省略swap和partitionHole方法的实现

    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

6.4.2 小区间优化(优化二)

数据量大的时候，分割到区间越小，则表示数据越接近有序了，前面我们认识了一个数据越接近有序效率越快的排序，那就是直接插入排序，所以我们可以进行小区间优化，那么简单来说，就是当区间的数据个数小于某个值的时候，采用直接插入排序算法。

1. 小区间优化:
   • 当递归处理的子数组长度小于一个阈值（如15）时，使用直接插入排序替代快速排序。
   • 直接插入排序在小数据集上非常高效，因为小数组近似有序的概率较高，直接插入排序在这种情况下的性能接近于 O(n)。
2. 减少不必要的递归调用:
   • 在快速排序过程中，当分割得到的子数组足够小，继续使用快速排序将会导致过多不必要的递归调用。
   • 通过切换到直接插入排序，可以减少递归深度，提高整体性能。
3. 综合两种排序算法的优势:
   • 快速排序在处理大型数据集时非常高效，而直接插入排序在处理小型或部分有序的数据集时效率更高。
   • 结合这两种排序算法可以使得整个排序过程更加高效和稳定。

• 时间复杂度分析：在我们有了三数取中优化的情况下，可以达到 O(n*logn)，如果没有三数取中，极端最坏的情况下，能达到 O(n^2)，但是我们通常说的快排都是优化过的，也就是 O(n*logn)。
• 空间复杂度分析：每次递归都会压栈，随之开辟空间，那么快排类似于二叉树的前序遍历，左子树遍历完了，再有右子树，也就是会压栈，也会出栈，那么最大压栈多少呢？显然是树的高度，即 O(logn)。
• 稳定性：快速排序是不稳定的排序算法。在排序过程中，相等的元素可能会因为划分操作而改变它们的相对位置。

public class Test9 {
    /**
     * 快速排序的优化版本，包括小区间优化。
     * @param array 要排序的整数数组。
     * @param left 排序的起始位置。
     * @param right 排序的结束位置。
     */
    private void quick(int[] array, int left, int right) {
        if (left >= right) {
            // 递归结束条件
            return;
        }

        // 小区间优化
        // 如果待排序的区间数据个数小于15个，使用直接插入排序
        if ((right - left + 1) < 15) {
            insertSort(array, left, right); // 注意这里需要传入left和right
            return;
        }

        // 三数取中，选择基准值
        int mid = findMidValOfIndex(array, left, right);
        swap(array, left, mid);

        // 进行一次快速排序的划分
        int pivot = partitionHoare(array, left, right);

        // 递归对左右两个子区间进行排序
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    // 这里省略了swap、partitionHoare、insertSort和findMidValOfIndex方法的实现

    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

---

6.5 非递归实现快速排序

我们需要用到栈

我们之前是在已经确定基准点之后，对剩余的区间递归进行同样的操作

我们现在创建一个栈，把剩余区间的左、右位置的下标分别放入栈中，如图是已经找到一个基准6的情况

然后弹出下标9给H，再弹出一个下标6给L，根据新的L和H的区间找到新的基准，再重复上面的操作

实现代码:

public class Test10 {
    /**
     * 非递归实现的快速排序。
     * @param array 要排序的整数数组。
     */
    public static void quickSort(int[] array){
        int left = 0;
        int right = array.length - 1;
        // 使用栈来存储每一层递归需要的左右边界。
        Deque<Integer> stack = new LinkedList<>();

        // 初始调用partition方法进行一次划分。
        int pivot = partition(array, left, right);

        // 对左侧子数组进行处理，如果存在两个以上的元素，则入栈。
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 对右侧子数组进行处理，如果存在两个以上的元素，则入栈。
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        // 不断地从栈中取出元素进行快速排序的划分操作。
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();

            pivot = partition(array, left, right);

            // 对左侧子数组进行处理。
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            // 对右侧子数组进行处理。
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    /**
     * 挖坑法进行划分的方法。
     * @param array 数组。
     * @param left 划分的起始位置。
     * @param right 划分的结束位置。
     * @return 划分元素的最终位置。
     */
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            // 从右向左找小于基准值的元素填坑。
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            // 从左向右找大于或等于基准值的元素填坑。
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        // 将基准值填回最后一个坑。
        array[left] = tmp;
        return left;
    }

    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

7. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

排序原理：

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止。
2. 将相邻的两个子组进行合并成一个有序的大组；
3. 不断的重复步骤2，直到最终只有一个组为止

详细步骤：

1. 递归分解:
   • 归并排序的核心思想是“分而治之”。首先，算法将数组递归地分解成更小的子序列，直到每个子序列只包含一个元素或没有元素。
   • 在mergeSort方法中，通过递归调用自身，数组被分为两部分，左半部分由left到mid，右半部分由mid+1到right。
2. 合并操作:
   • 一旦子序列被分解到足够小，算法接着将这些子序列合并成较大的有序序列。
   • 在merge方法中，两个有序子序列被合并。方法使用两个指针s1和s2分别遍历左右两个子序列，通过比较它们的元素，将较小的元素依次放入临时数组tmp中。
3. 创建临时数组:
   • 为了合并两个子序列，算法创建了一个临时数组tmp，它的大小等于正在合并的两个子序列的总长度。
4. 比较和复制:
   • 算法逐个比较两个子序列的元素，并将较小的元素先移入tmp数组。如果一个子序列的元素先被完全移入tmp，则将另一个子序列的剩余部分直接复制到tmp的后面。
   • 合并完成后，将tmp数组中的元素复制回原数组对应的位置，确保原数组在该段是有序的。
5. 整体流程:
   • 归并排序的整个过程是一个递归分解然后合并的过程。它首先将数组分解到不能再分解为止（即每个子序列只有一个元素），然后再逐步将这些子序列合并成一个完整的有序数组。

---

静图分析:

动图演示:

7.1 递归实现归并排序:

1. 时间复杂度：归并排序的时间复杂度为 O(N log N)。这是因为归并排序将数组分成两半，对每半进行排序，然后将它们合并。每次分割将数组大小减半，导致其分割的深度为 log N。在每一层分割中，合并操作的时间复杂度为 O(N)。因此，总体时间复杂度为 O(N log N)。
2. 空间复杂度：归并排序的空间复杂度为 O(N)，主要是因为它需要一个与原数组同样大小的辅助数组来暂时存储合并后的元素。虽然归并操作是递归进行的，但由于合并操作中使用的是同一个辅助数组，因此所需的额外空间总量不超过数组的大小。
3. 稳定性：归并排序是一种稳定的排序算法。在合并两个子序列时，如果遇到相等的元素，它会先拷贝左侧子序列的元素，保持了相等元素原有的相对顺序，因此不会改变相等元素之间的先后顺序。

public class MergeSort {
    /**
     * 归并排序的主方法。
     * @param array 要排序的整数数组。
     * @param left 排序的起始位置。
     * @param right 排序的结束位置。
     */
    public static void mergeSort(int[] array, int left, int right) {
        // 递归终止条件：当子序列只剩下一个元素或没有元素时，不再继续分解
        if (left >= right) {
            return;
        }
        // 找到子序列的中间位置
        int mid = (left + right) / 2;

        // 递归地对左半部分进行归并排序
        mergeSort(array, left, mid);

        // 递归地对右半部分进行归并排序
        mergeSort(array, mid + 1, right);

        // 合并两个已排序的子序列
        merge(array, left, right, mid);
    }

    /**
     * 合并两个有序子序列的方法。
     * @param array 数组。
     * @param start 合并的起始位置。
     * @param end 合并的结束位置。
     * @param mid 两个有序子序列的分界位置。
     */
    public static void merge(int[] array, int start, int end, int mid) {
        // 创建一个临时数组用于存放合并后的序列
        int[] tmp = new int[end - start + 1];

        // 初始化两个指针，分别指向两个有序子序列的起始位置
        int s1 = start; // 左序列的起始位置
        int s2 = mid + 1; // 右序列的起始位置
        int k = 0; // 临时数组的索引

        // 遍历两个子序列，比较并合并
        while (s1 <= mid && s2 <= end) {
            if (array[s1] <= array[s2]) {
                // 如果左序列的当前元素小于或等于右序列的当前元素
                // 则将左序列的当前元素加入临时数组
                tmp[k++] = array[s1++];
            } else {
                // 否则将右序列的当前元素加入临时数组
                tmp[k++] = array[s2++];
            }
        }

        // 将剩余的左序列元素加入临时数组
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }

        // 将剩余的右序列元素加入临时数组
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        // 将临时数组的内容复制回原数组的对应位置
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}

在归并排序中，使用i + start将临时数组tmp中的内容复制回原数组的对应位置的原因是，我们在合并过程中并不是总是操作整个数组，而是处理数组的子段。这个子段是从索引start到索引end的部分。

让我来解释一下这一点：

• 当我们在合并两个有序子序列时，我们不是总是从数组的起始位置（即索引0）开始的，而是从start索引开始的。这意味着合并操作可能发生在数组的任意位置。
• 临时数组tmp是从0开始索引的，它用于存储合并过程中排序后的元素。这个数组仅反映了从start到end的子段，而不是整个原数组。
• 因此，当我们将tmp中的元素复制回原数组时，我们需要将这些元素放置回它们在原数组中的正确位置。这就是为什么我们使用array[i + start] = tmp[i]。这里的i + start确保我们从原数组的start位置开始放置tmp数组中的元素。

举个例子，如果我们正在处理原数组中从索引3到索引7的子段，那么tmp数组中索引0的元素应该被复制到原数组的索引3的位置，tmp数组中索引1的元素应该被复制到原数组的索引4的位置，依此类推。这就是i + start在这里起到的作用。

---

7.2 非递归实现归并排序:

解题思路：利用将数组如树进行拆开后，回到原来的模样，由1个单独的数据，变成2个有序的数据，变成4个有序的数据，直至当它变成与原待排序列等长的数据为止

1. 迭代分组：通过外层循环控制分组的间隔gap，从1开始，每次翻倍。每个间隔gap代表当前处理的子序列长度。
2. 合并子序列：对于每个间隔gap，内层循环遍历数组，合并每两个相邻的有序子序列。
3. 动态增加间隔：每轮合并后，子序列的长度增大，间隔gap也相应增大。这个过程持续进行，直到gap大于或等于数组长度，此时整个数组排序完成。

时间复杂度:O(N log N)

• 外层循环：外层循环的间隔gap从1开始，每次翻倍，直到超过数组长度。由于每次翻倍，所以外层循环的迭代次数是对数级别的，即 log N。
• 内层循环：内层循环中，每次合并操作的时间复杂度是 O(N)，因为每个元素最多被复制和比较一次。虽然内层循环看起来包含两个嵌套循环（while循环），但实际上每轮合并的总工作量仅涉及整个数组的每个元素一次。

public class MergeSort2 {
    /**
     * 非递归实现的归并排序。
     * @param array 要排序的整数数组。
     */
    public static void mergeSort(int[] array) {
        int gap = 1; // 初始的分组间隔，从1开始，代表每组只有一个元素

        // 外层循环控制间隔大小，每次翻倍
        while (gap < array.length) {
            // 内层循环遍历数组，按照当前的间隔大小合并子序列
            for (int i = 0; i < array.length; i += gap * 2) {
                int left = i; // 当前子序列的开始位置
                int mid = left + gap - 1; // 当前子序列的中间位置，可能会越界
                if (mid >= array.length) {
                    mid = array.length - 1; // 防止越界
                }
                int right = mid + gap; // 当前子序列的结束位置，可能会越界
                if (right >= array.length) {
                    right = array.length - 1; // 防止越界
                }
                // 调用合并函数，合并两个有序子序列
                merge(array, left, right, mid);
            }
            gap *= 2; // 增大间隔，下一轮处理更大的子序列
        }
    }

    /**
     * 合并两个有序子序列。
     * @param array 数组。
     * @param start 合并的起始位置。
     * @param end 合并的结束位置。
     * @param mid 两个有序子序列的分界位置。
     */
    public static void merge(int[] array, int start, int end, int mid) {
        int s1 = start; // 左序列的起始位置
        int s2 = mid + 1; // 右序列的起始位置
        int[] tmp = new int[end - start + 1]; // 临时数组存放合并后的序列
        int k = 0; // 临时数组的索引

        // 遍历两个子序列，将较小的元素先加入到临时数组中
        while (s1 <= mid && s2 <= end) {
            if (array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }

        // 将剩余的元素加入到临时数组中
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }

        // 将临时数组的内容复制回原数组对应的位置
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}

---

7.3 归并排序的应用场景

海量数据的排序问题：我们有100G的数据待排序，内存只有一个G，我们应该怎么办？？？

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每份 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了​

8. 计数排序(了解)

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

动图演示：

1. 找出最大最小值：首先遍历数组，找出数组中的最大值和最小值，以确定计数数组的长度。
2. 创建计数数组：根据最大值和最小值的差值创建一个计数数组，长度为max - min + 1，用于记录每个整数值出现的次数。
3. 计数：再次遍历原数组，对每个元素出现的次数进行计数。计数时，将元素值相对于最小值的偏移量作为计数数组的索引。
4. 重构原数组：最后，遍历计数数组，根据每个元素的计数重构原数组。每次从计数数组取出一个值，就将其转换回原数组的元素，并减少相应的计数。

class CountSort {
    /**
     * 计数排序的实现。
     * @param array 要排序的整数数组。
     */
    public static void countSort(int[] array) {
        // 找出数组中的最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i]; // 更新最小值
            }
            if (array[i] > max) {
                max = array[i]; // 更新最大值
            }
        }

        // 计算计数数组的长度
        int len = max - min + 1;
        int[] count = new int[len]; // 创建计数数组

        // 遍历原始数组，记录每个值出现的次数
        for (int i = 0; i < array.length; i++) {
            count[array[i] - min]++; // 对应计数数组的位置加一
        }

        // 根据计数数组，重构原始数组
        int index = 0; // 原始数组的索引
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                array[index] = i + min; // 根据计数数组的下标恢复原始值
                index++;
                count[i]--; // 减少计数
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 5, 1, 3, 11, 0, 4, -1, -5, 7};
        System.out.println("排序前" + Arrays.toString(array));
        countSort(array);
        System.out.println("排序后" + Arrays.toString(array));
    }
}

注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。

数组中元素有正有负的情况时不适用计数排序。

计数排序的特性总结：

1. 时间复杂度：O(N + K)，其中N是原数组的长度，K是原数组中最大值与最小值的差。
2. 空间复杂度：O(K)，主要是计数数组的开销。
3. 稳定性：计数排序是稳定的排序算法，但实现时需要注意保持稳定性。
4. 适用性：计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

9. 基数排序 (了解)

基数排序是依次根据个位数、十位数、百位数......的大小来排序 ，最终的结果就是排好序的序列

思路：

1.根据所给序列，找到序列中数据的最大值，并求该值的位数。

2.创建十个队列，这里可以将队列形象为桶。根据数据每一位的值放在相应桶中

3.再将桶里面的数据依次取出来

动图如下：

实现代码：

1.时间复杂度O(n)

2.当元素取值范围较大，但元素个数较少时可以利用基数排序

class Soultion_ {
    /**
     * 计算数字的长度。
     * @param data 输入的数字。
     * @return 数字的长度。
     */
    public static int countlen(int data) {
        return (data + "").length();
    }

    /**
     * 获取数字在特定位上的数字。
     * @param num 原始数字。
     * @param r 位数（个位为1，十位为2，依此类推）。
     * @return 特定位上的数字。
     */
    public static int index(int num, int r) {
        int ret = 0;
        for (int i = 1; i <= r; i++) {
            ret = num % 10;
            num /= 10;
        }
        return ret;
    }

    /**
     * 基数排序的主要逻辑。
     * @param array 要排序的数组。
     */
    public static void sort(int[] array) {
        // 找出数组中最大数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) max = array[i];
        }
        // 计算最大数的长度
        int len = countlen(max);

        // 创建10个桶，用于基数排序
        LinkedList<Integer>[] list = new LinkedList[10];
        for (int i = 0; i < list.length; i++) {
            list[i] = new LinkedList<>();
        }

        // 按每个位进行排序
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < array.length; j++) {
                // 根据当前位的数值，将元素加入到相应的桶中
                list[index(array[j], i)].offer(array[j]);
            }
            // 从桶中取出元素，重新放回数组中
            int k = 0;
            for (int j = 0; j < list.length; j++) {
                while (!list[j].isEmpty()) {
                    array[k++] = list[j].poll();
                }
            }
        }
    }
}

public class RadixSort {
    public static void main(String[] args) {
        Soultion_ solution = new Soultion_();
        int[] arr = { 23, 1, 4, 9, 98, 132, 42 };
        solution.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

10. 桶排序 (了解)

桶排序是根据所给序列中数据来划分区间，一个区间就是一个桶，将元素之间差值不大的放进一个桶中。然后对桶内数据进行排序，最后将排好序的桶内数据倒出给原来的数组。

步骤：

1、设置一定数量的空桶

2、遍历待排序序列，将每个元素放入对应桶里

3、对每个不空的桶进行排序

4、从不空的桶将元素从桶中取出

动图如下：

实现代码:

• 时间复杂度:O(N)
• 空间复杂度:O(N+M)
• 稳定性:不稳定

class Sort {
    /**
     * 桶排序的实现。
     * @param array 要排序的整数数组。
     */
    public static void bucketSort(int[] array) {
        // 找出数组中的最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }

        // 计算桶的数量
        int range = (max - min) / array.length + 1;
        PriorityQueue<Integer>[] queue = new PriorityQueue[range];

        // 初始化每个桶，这里使用优先队列（小顶堆）作为桶
        for (int i = 0; i < range; i++) {
            queue[i] = new PriorityQueue<>();
        }

        // 将每个元素放入对应的桶中
        for (int i = 0; i < array.length; i++) {
            int num = (array[i] - min) / array.length;
            queue[num].offer(array[i]);
        }

        // 将桶中的元素取出，放回原数组中
        int k = 0;
        for (int i = 0; i < queue.length; i++) {
            while (!queue[i].isEmpty()) {
                array[k++] = queue[i].poll();
            }
        }
    }
}

public class BucketSort {
    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] array = new int[]{3, 0, 19, 15, 24, 30};
        System.out.println("排序前" + Arrays.toString(array));
        sort.bucketSort(array);
        System.out.println("排序后" + Arrays.toString(array));
    }
}

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n)	O(n^1.3)	O(n^2)	O(1)	不稳定
堆排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	不稳定
快速排序	O(n * log(n))	O(n * log(n))	O(n^2)	O(log(n)) ~ O(n)	不稳定
归并排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	稳定