当前位置: article > 正文

【尚硅谷】Java数据结构与算法笔记07 - 排序算法_尚硅谷数据结构归并排序代码

作者：不正经 | 2024-03-10 12:30:23

踩

尚硅谷数据结构归并排序代码

文章目录

一、排序算法简介
二、排序的分类
三、冒泡排序
- 3.1 基本介绍
- 3.2 算法图解
- 3.3 代码实现
四、选择排序
- 4.1 基本介绍
- 4.2 思路分析
- 4.3 算法图解
- 4.4 代码实现
五、插入排序
- 5.1 基本介绍
- 5.2 思路分析
- 5.3 算法图解
- 5.4 代码实现
六、希尔排序
- 6.1 简单插入排序存在的问题
- 6.2 基本介绍
- 6.3 思路分析
- 6.4 算法图解
- 6.5 代码实现
七、快速排序
- 7.1 基本介绍
- 7.2 算法图解
- 7.3 代码实现
八、归并排序
- 8.1 基本介绍
- 8.2 算法图解
- 8.3 代码实现
九、基数排序
- 9.1 基本介绍
- 9.2 思路分析
- 9.3 算法图解
- 9.4 代码实现
- 9.5 基数排序说明
十、堆排序
- 10.1 基本介绍
- 10.2 基本思想
- 10.3 步骤图解
- 10.4 思路总结
- 10.5 代码实现
十一、计数排序
- 11.1 基本介绍
- 11.2 思路分析
- 11.3 算法图解
- 11.4 代码实现
十二、桶排序
- 12.1 基本介绍
- 12.2 思路分析
- 12.3 算法图解
- 12.4 代码实现
十三、常用排序算法总结和对比
- 13.1 一张排序算法的对比图
- 13.2 相关术语解释

一、排序算法简介

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

二、排序的分类

内部排序:
指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。
外部排序法:
数据量过大, 无法全部加载到内存中, 需要借助外部存储(文件等)进行排序。
常见的排序算法分类(见下图)：

在这里插入图片描述

三、冒泡排序

3.1 基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值, 若发现逆序则交换, 使值较大的元素逐渐从前移向后部, 就象水底下的气泡一样逐渐向上冒。

优化

因为排序的过程中, 各元素不断接近自己的位置, 如果一趟比较下来没有进行过交换, 就说明序列有序, 因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化, 可以在冒泡排序写好后, 在进行)

3.2 算法图解

在这里插入图片描述

小结上面的图解过程:

一共进行数组的大小-1 次大的循环
每一趟排序的次数在逐渐的减少
如果我们发现在某趟排序中, 没有发生一次交换, 可以提前结束冒泡排序。这个就是优化

3.3 代码实现

【排序算法】Java实现9大排序算法及其速度对比(附详细代码)

上面链接中包含了冒泡排序的基础代码。但是没有进行优化。下面给出的是带有优化的冒泡排序代码：

    /**
     * @param nums 要排序的数组
     * @return 返回排序后的数组
     * @Description 冒泡排序
     */
    public static int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean isChange = false;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    //交换位置
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    isChange = true;
                }
            }
            if (!isChange) {
                break;
            }
        }
        return nums;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四、选择排序

4.1 基本介绍

选择式排序也属于内部排序法, 是从欲排序的数据中, 按指定的规则选出某一元素, 再依规定交换位置后达到排序的目的。

4.2 思路分析

选择排序 (select sorting) 也是一种简单的排序方法。它的基本思想是：第一次从 arr[0] arr[n-1]中选取最小值, 与 $\operatorname{arr}[0]$ 交换, 第二次从 $\operatorname{arr}[1] \sim \operatorname{arr}[\mathrm{n}-1]$ 中选取最小值, 与 $\operatorname{arr}[1]$ 交换, 第三次从 $\operatorname{arr}[2] \operatorname{arr}[\mathrm{n}-1]$ 中选取最小值, 与 $\operatorname{arr}[2]$ 交换, $\cdots$ , 第 $\mathrm{i}$ 次从 $\operatorname{arr}[\mathrm{i}-1] \operatorname{arr}[\mathrm{n}-1]$ 中选取最小值, 与 $\operatorname{arr}[\mathrm{i}-1]$ 交换, $\cdots$ , 第 $\mathrm{n}-1$ 次从 $\operatorname{arr}[\mathrm{n}-2] \operatorname{arr}[\mathrm{n}-1]$ 中选取最小值, 与 $\operatorname{arr}[\mathrm{n}-2]$ 交换, 总共通过 $\mathrm{n}-1$ 次, 得到一个按排序码从小到大排列的有序序列。

4.3 算法图解

在这里插入图片描述

4.4 代码实现

    /**
     * @param nums 要排序的数组
     * @return 返回排序后的数组
     * @Description 选择排序
     */
    public static int[] selectSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    minIndex = j;
                }
            }
            // 把找到的最小值和当前i位置替换
            int temp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = temp;
        }
        return nums;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、插入排序

5.1 基本介绍

插入式排序属于内部排序法, 是对于要排序的元素以插入的方式找寻该元素的适当位置, 以达到排序的目的。

5.2 思路分析

插入排序（Insertion Sorting）的基本思想是：把 $\mathbf{n}$ 个待排序的元素看成为一个有序表和一个无序表, 开始时有序表中只包含一个元素, 无序表中包含有 $\mathbf{n - 1}$ 个元素, 排序过程中每次从无序表中取出第一个元素, 把它的排序码依次与有序表元素的排序码进行比较, 将它插入到有序表中的适当位置, 使之成为新的有序表。

5.3 算法图解

在这里插入图片描述

5.4 代码实现

    public static int[] insertSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 把当前遍历的数字存起来
            int temp = nums[i];
            // 遍历当前数字前面所有的数字
            int j;
            for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
                // 把前一个数字赋给后一个数字
                nums[j + 1] = nums[j];
            }
            // 把临时变量赋给不满足条件的后一个元素
            nums[j + 1] = temp;
        }
        return nums;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六、希尔排序

6.1 简单插入排序存在的问题

我们看简单的插入排序可能存在的问题。

数组 $\operatorname{arr}=\{2,3,4,5,6,1\}$ 这时需要插入的数 1 (最小), 这样的过程是：

\begin{aligned} {2, 3, 4, 5, 6, 6} \\ {2, 3, 4, 5, 5, 6} \\ {2, 3, 4, 4, 5, 6} \\ {2, 3, 3, 4, 5, 6} \\ {2, 2, 3, 4, 5, 6} \\ {1, 2, 3, 4, 5, 6} \end{aligned}

$\begin{aligned} & \{2,3,4,5,6,6\} \\ & \{2,3,4,5,5,6\} \\ & \{2,3,4,4,5,6\} \\ & \{2,3,3,4,5,6\} \\ & \{2,2,3,4,5,6\} \\ & \{1,2,3,4,5,6\} \end{aligned}$

{2, 3, 4, 5, 6, 6} {2, 3, 4, 5, 5, 6} {2, 3, 4, 4, 5, 6} {2, 3, 3, 4, 5, 6} {2, 2, 3, 4, 5, 6} {1, 2, 3, 4, 5, 6}

结论：当需要揷入的数是较小的数时, 后移的次数明显增多, 对效率有影响。

6.2 基本介绍

希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序, 它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

6.3 思路分析

希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整个文件恰被分成一组, 算法便终止

6.4 算法图解

在这里插入图片描述

6.5 代码实现

    public static int[] shellSort(int[] nums) {
        // 遍历所有步长
        for (int d = nums.length / 2; d > 0; d /= 2) {
            // 遍历所有元素
            for (int i = 0; i < nums.length; i++) {
                // 遍历本组中所有元素
                for (int j = i - d; j >= 0; j -= d) {
                    // 如果当前元素大于加上步长后的那个元素
                    if (nums[j] > nums[j + d]) {
                        int temp = nums[j];
                        nums[j] = nums[j + d];
                        nums[j + d] = temp;
                    }
                }
            }
        }
        return nums;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

七、快速排序

7.1 基本介绍

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

7.2 算法图解

在这里插入图片描述

7.3 代码实现

    /**
     * @param nums  被排序的数组
     * @param start 排序开始位置
     * @param end   排序结束位置
     * @return 返回排序后的数组
     */
    public static int[] quickSort(int[] nums, int start, int end) {
        if (start < end) {
            // 低位置
            int low = start;
            // 高位置
            int high = end;
            // 取开始位置元素作为标准数
            int standard = nums[start];
            while (low < high) {
                // 如果右边的数组比标准数大
                while (nums[high] >= standard && low < high) {
                    high--;
                }
                // 使用右边的数字替换左边的数字
                nums[low] = nums[high];
                // 如果左边的数组比标准数小
                while (nums[low] <= standard && low < high) {
                    low++;
                }
                // 使用左边的数字替换右边的数字
                nums[high] = nums[low];
            }
            // 把标准数赋回给低位置或者高位置（此时低位置和高位置已经重合）
            nums[low] = standard;
            // 处理标准数左边的数字
            nums = quickSort(nums, start, low);
            // 处理标准数右边的数字
            nums = quickSort(nums, low + 1, end);
        }
        return nums;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

八、归并排序

8.1 基本介绍

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法, 该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解, 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起, 即分而治之)。

8.2 算法图解

在这里插入图片描述
再来看看治阶段, 我们需要将两个已经有序的子序列合并成一个有序序列, 比如上图中的最后一次合并, 要将 $[4, 5, 7, 8]$ 和 $[1, 2, 3, 6]$ 两个已经有序的子序列, 合并为最终序列 $[1, 2, 3, 4, 5, 6, 7, 8]$ , 来看下实现步骤
在这里插入图片描述

8.3 代码实现

	public static int[] mergeSort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mergeSort(nums, low, mid);
            mergeSort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }

        return nums;
    }

    public static void merge(int[] nums, int low, int mid, int high) {
        // 临时数组
        int[] temp = new int[high - low + 1];
        // 记录左边的数组的最左位置
        int i = low;
        // 记录右边数组的最左位置
        int j = mid + 1;
        // 记录放入temp数组中的位置,从0开始放，每次放 就++
        int index = 0;
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[index++] = nums[i++];
            } else {
                temp[index++] = nums[j++];
            }
        }
        // 处理多余的数组
        while (i <= mid) {
            temp[index++] = nums[i++];
        }
        while (j <= high) {
            temp[index++] = nums[j++];
        }
        // 将临时数组中的值赋给nums数组中对应位置
        for (int k = 0; k < temp.length; k++) {
            nums[k + low] = temp[k];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

九、基数排序

注意：基数排序不支持负数，实数排序效率不高

9.1 基本介绍

基数排序（radix sort）属于 “分配式排序” (distribution sort）, 又称 “桶子法” (bucket sort）或 bin sort, 顾名思义, 它是通过键值的各个位的值, 将要排序的元素分配至某些 “桶” 中, 达到排序的作用
基数排序法是属于稳定性的排序, 基数排序法的是效率高的稳定性排序法
基数排序(Radix Sort)是桶排序的扩展
基数排序是 1887 年赫尔曼 - 何乐礼发明的。它是这样实现的: 将整数按位数切割成不同的数字, 然后按每个位数分别比较。

9.2 思路分析

将所有待比较数值统一为同样的数位长度, 数位较短的数前面补零。然后, 从最低位开始, 依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

这样说明, 比较难理解, 下面我们看一个图文解释, 理解基数排序的步骤

9.3 算法图解

$\text { 将数组 }\{53,3,542,748,14,214\} \text { 使用基数排序, 进行升序排序 }$

在这里插入图片描述

9.4 代码实现

	public static void radixSort(int[] arr) {
        // 找出最大数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 计算最大数是几位数
        int maxLength = (max + "").length();
        // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        // 说明：
        // 二维数组包含10个一维数组，
        // 为了防止在放入数的时候，数据溢出，则每个一维数组（桶），大小定为arr.length
        // 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        // 为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        // 可以这里理解
        // 比如：bucketElementCounts[0]，记录的就是bucket[0]桶的放入的数据个数
        int[] bucketElementCounts = new int[10];
        // 这里我们使用循环将代码处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
            int index = 0;
            // 遍历每一桶，并将桶中的数据放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶即第k个桶（即第k个一维数组），放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 第i+1轮处理后，需要将每个bucketElementCounts[k] = 0
                bucketElementCounts[k] = 0;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

9.5 基数排序说明

基数排序是对传统桶排序的扩展, 速度很快.
基数排序是经典的空间换时间的方式, 占用内存很大, 当对海量数据排序时, 容易造成 OutOfMemoryError 。
基数排序是稳定的。[注:假定在待排序的记录序列中, 存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, $r [i] = r [j]$ , 且 r[i]在 r[j]之前, 而在排序后的序列中, $r [i]$ 仍在 r[j]之前, 则称这种排序算法是稳定的; 否则称为不稳定的]
有负数的数组, 我们不用基数排序来进行排序, 如果要支持负数, 参考: https://code.i-harness.com/zh-CN/q/e98fa9

十、堆排序

10.1 基本介绍

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最好最坏平均时间复杂度均为 $O(n\log n)$ 。他也不是稳定排序。
堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，注意：没有要求节点的左孩子的值和右孩子的值的大小关系。
每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆

下面是大顶堆举例说明：

在这里插入图片描述

下面是小顶堆距离说明：

在这里插入图片描述
一般升序排序采用大顶堆，降序排序采用小顶堆

10.2 基本思想

堆排序的基本思想是：

将待排序序列构造一个大顶堆
此时，整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换，此时末尾就为最大值
然后将剩余的 n-1 个元素重新构成一个堆，这样就会得到 n 个元素的次小值。如此反复进行，便能得到一个有序序列了

可以看到，在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了

10.3 步骤图解

要求：给你一个数组 {4, 6, 8, 5, 9} ，要求使用堆排序，将数组升序排序

步骤一：构造初始堆。将给定的无序序列构造为一个大顶堆（一般升序排序采用大顶堆，降序排序采用小顶堆）

假定给定的无序序列结构如下：

在这里插入图片描述
此时我们从最后一个非叶子节点开始（叶节点不用调整，第一个非叶子节点在数组中的索引是：arr.length/2-1=5/2-1=1，也就是下面的6节点），从左至右，从下至上进行调整

在这里插入图片描述
找到第二个非叶子节点4，由于 [4, 9, 8] 中 9 最大，所以 4 和 9 交换

在这里插入图片描述
这时，交换导致了子根 [4, 5, 6] 结构混乱，继续调整， [4, 5, 6] 中，6最大，交换 4 和 6

在这里插入图片描述
此时，我们就将一个无序序列构造成了一个大顶堆

步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换。

将堆顶元素 9 和末尾元素 4 进行交换

在这里插入图片描述
重新调整结构，使其继续满足堆定义

在这里插入图片描述
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8

在这里插入图片描述
后续过程，继续进行调整、交换，如此反复进行，最终使得整个序列有序

在这里插入图片描述

10.4 思路总结

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

10.5 代码实现

	public static int[] heapSort(int[] nums) {
        int start = (nums.length - 1) / 2;
        // 调整为大顶堆
        for (int i = start; i >= 0; i--) {
            maxHeap(nums, nums.length, i);
        }
        //
        for (int i = nums.length - 1; i >= 0; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            maxHeap(nums, i, 0);
        }
        return nums;
    }

    // 转大顶堆的方法
    public static void maxHeap(int[] nums, int size, int index) {
        // 当前节点
        int self = index;
        // 左子节点
        int left = 2 * index + 1;
        // 和左子节点进行对比，选出最大的节点放到自身位置
        if (left < size && nums[self] < nums[left]) {
            int temp = nums[self];
            nums[self] = nums[left];
            nums[left] = temp;
            maxHeap(nums, size, left);
        }
        // 右子节点
        int right = 2 * index + 2;
        // 和右子节点进行对比，选出最大的节点放到自身位置
        if (right < size && nums[self] < nums[right]) {
            int temp = nums[self];
            nums[self] = nums[right];
            nums[right] = temp;
            maxHeap(nums, size, right);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

十一、计数排序

11.1 基本介绍

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序的特征
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

注意：计数排序只适用于非负整数的排序

11.2 思路分析

算法的步骤如下：

（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

11.3 算法图解

在这里插入图片描述

11.4 代码实现

	public static void countSort(int[] array) {
        // 1.得到数列的最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        // 2.根据数列最大值确定统计数组的长度
        int[] countArray = new int[max + 1];
        // 3.遍历数列，填充统计数组
        for (int k : array) {
            countArray[k]++;
        }
        // 4.遍历统计数组，输出结果
        int index = 0;
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                array[index++] = i;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

十二、桶排序

12.1 基本介绍

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

12.2 思路分析

桶排序的思想近乎彻底的分治思想。

桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。

然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。

接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。

补充：映射函数一般是 f = array[i] / k; k^2 = n; n是所有元素个数
为了使桶排序更加高效，我们需要做到这两点：

1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

实现逻辑

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

12.3 算法图解

在这里插入图片描述

12.4 代码实现

	public static void bucketSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int k : arr) {
            max = Math.max(max, k);
            min = Math.min(min, k);
        }
        // 桶数
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<>());
        }
        // 将每个元素放入桶
        for (int j : arr) {
            int num = (j - min) / (arr.length);
            bucketArr.get(num).add(j);
        }
        // 对每个桶进行排序
        for (ArrayList<Integer> integerArrayList : bucketArr) {
            Collections.sort(integerArrayList);
        }
        int index = 0;
        // 将桶中的数据依次取出
        for (ArrayList<Integer> integers : bucketArr) {
            for (Integer integer : integers) {
                arr[index++] = integer;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

十三、常用排序算法总结和对比

13.1 一张排序算法的对比图

在这里插入图片描述

13.2 相关术语解释

稳定: 如果 $a$ 原本在 $b$ 前面, 而 $a = b$ , 排序之后 $a$ 仍然在 $b$ 的前面;
不稳定：如果 $a$ 原本在 $b$ 的前面, 而 $a = b$ , 排序之后 $a$ 可能会出现在 $b$ 的后面;
内排序: 所有排序操作都在内存中完成;
外排序: 由于数据太大, 因此把数据放在磁盘中, 而排序通过磁盘和内存的数据传输才能进行;
时间复杂度：一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。
$\mathrm{n}$ : 数据规模
$\mathrm{k}$ : “桶” 的个数
In-place: 不占用额外内存
Out-place: 占用额外内存

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/217994