凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

数据结构与算法专栏笔记_排序算法篇_算法数据排序有值相等

作者：凡人多烦事01 | 2024-04-30 04:22:47

踩

算法数据排序有值相等

文章目录

摘要
一. 排序上——冒泡,插入,选择排序
二. 排序下
三. 线性排序分析总结

摘要

算法如果按照模块分，排序算法绝对算得上割据一方的存在。我们无可避免地会想，对一组数据进行排序让你玩得这么花，有这个必要吗？我想被要求手写快排的人至少是认为有的~

就如同以前历史老师所说的那般：学习历史学的不是历史本身，而是历史背后的故事。

而排序算法背后，分治思想，二分思想，优化，时空复杂度都是需要我们去探寻的故事，而不同的排序算法在相同场景下的性能大相径庭，到底选谁呢？有没有什么衡量依据呢？人们更常用的是哪种呢？故事的大幕就此拉开——

注：文章中的图均来自于极客时间数据结构与算法专栏。文章初衷是作为笔记使用，所以缺乏详细推导，仅用于回顾知识点。

一. 排序上——冒泡,插入,选择排序

1.1 从一个问题开始

Q：插入排序和冒泡排序的时间复杂度都为O(n2),但为什么人们更倾向于选择插入排序呢？

A：插入排序和冒泡排序的时间复杂度都为O(n2),且他们都是稳定的原地排序算法，但他们的性能区别在于比较次数和交换次数。

冒泡排序不管怎么优化，它的交换次数，也就是移动元素次数都是固定值，即原始数据的逆序度。插入排序同样如是。

但从代码实现上来说，冒泡排序需要三次赋值，而插入排序只需要一次赋值。也就是说冒泡排序的数据交换比插入排序的数据交换更复杂，我们来具象的看一下——

//冒泡排序中的交换操作
if(a[j]>a[j+1]){
    int tmp = a[j];
    a[j] = a[j+1];
    a[j+1] = tmp;
    flag = true;
}

//插入排序中的交换操作
if(a[j] > value){
	a[j+1] = a[j];
}else{
	break;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.2 如何分析一个排序算法

1.2.1 排序算法的执行效率

最好情况，最坏情况，平均情况时间复杂度

在之前的学习中，我们只需要粗略的比较时间复杂度，那为什么在排序时，又需要引入这些具体的参数呢?

有些排序算法有区分的必要；
对于要排序的数据，有序度是截然不同的。

时间复杂度的系数，常数和低阶

同样的困惑，但这个要好解答的多，无非是数据规模小的情况下，这些参数本身就可以表达一种趋势。

比较次数和交换次数

排序算法有两类，一类基于排序，一类不基于排序。在分析基于排序的算法中，数据交换就意味着数据搬移，是要耗费性能的，所以有必要区分。

1.2.2 排序算法的内存消耗

为了描述内存消耗，我们引入原地排序的概念，所谓原地排序，就是指空间复杂度为O(1)。

1.2.3 排序算法的稳定性

稳定性的大致意思是在新的需求被引入后，原本系统能够维持相对稳定。而在这里，排序算法的稳定性指的是，如果待排序的序列中存在值相等的元素，经过排序以后，相等元素之间的原有的先后顺序不变。

但是业务中的排序，往往不是对单纯的整数进行排序，而是一组对象，我们需要根据对象的某个KEY进行排序。来看一个小例子——

假如说，我们需要给电商交易系统中的订单排序。订单有两个属性，一个是下单时间，一个是订单金额。如果我们现在有10万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照订单时间排序，对于这样的需求，我们要怎么做？

很明显，先入为主的一种方式是，首先根据订单金额进行排序，在对订单金额相同的区间按照时间排序。

很自然没错，但在每个小区间要交换元素的次数太多了，有没有性能更高的方法呢？

我们需要选择一种稳定的排序算法，也就是先对订单按照时间进行排序，再使用稳定排序算法按照金额进行排序，这样的话，我们就能确保金额相同的两个对象，在排序后的前后顺序不变。

1.3 冒泡排序

1.3.1 冒泡排序概述

冒泡排序比较相邻的两个元素，如果不满足大小关系，则互换位置，一次冒泡会让至少一个元素移动到它应该在的位置。重复n次即可完成排序。

下面我们来看具体的例子：对一组数据4,5,6,3,2,1从小到大进行排序。

那么第一次冒泡的过程是这样的——

这样重复n次即可完成冒泡排序。但这样的排序方式是可以优化的，因为在某次冒泡后，整个数据已经是有序的了，就不需要再排序。所以我们需要一个标志量来标识有序的状态，下面是优化后的代码——

 /**
     * 冒泡排序
     */
    public void bubbleSort(int[] a,int n){
        if(n <= 1)
            return;
        //比较n-1趟
        for(int i=0;i<n-1;i++){
            boolean flag = false;
            for(int j=0;i<n-i-1;j++){
                if(a[j] > a[j+1]){
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    //表明有数据交换
                    flag = true;
                }
            }
            //如果没有数据交换，则退出
            if(!flag)
                break;;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.3.2 冒泡排序的分析

原地排序算法:冒泡的过程只涉及相邻两个元素的交换操作，只需要常量级的临时空间，所以空间复杂度为O(1),即原地排序算法。
稳定的排序算法:在比较时，相等的元素不需要交换位置，所以是稳定的排序算法
时间复杂度均为O(n2):最好情况即是整个数据都是有序的，只需要进行一次冒泡就ok了，即最好时间复杂度为O(N)。同理，最坏情况下的时间复杂度为O(N2)。

那平均时间复杂度如何计算呢?按部就班的说，应该计算期望，但规模大的数据，计算期望是非常麻烦的，为了更好地描述平均时间复杂度，我们这里引入有序度的概念。

有序度是数组中具有有序关系的元素对的个数。用数学表达式表示就是——
$a [i] > a [j], i > j$

同理，假如有6个元素，那这组数据的满序度就是6*(6-1)/2,应用到更宽泛的范围，满序度可以表示为——
$n * (n - 1) / 2$
自然，我们也可以得到逆序度的概念：逆序度=满序度-有序度。

我们现在再来描述平均时间复杂度。最坏情况下，有序度为0，需要进行n*(n-1)/2次交换。最好情况下，有序度为n，不需要进行交换，则平均时间复杂度为
$n * (n - 1) / 4$

1.4 插入排序

1.4.1 插入排序概述

插入排序是借助区分已排序区间和未排序区间的思路来展开描述的。

插入算法的核心是取未排序区间中的元素，将其插入到已排序区间的合适位置，并保证已排序区间数据一致有序。

如下图所示，要排序的数据为4,5,6,1,3,2——

插入排序同冒泡排序，包含元素的比较进而元素的移动两种操作，那我们如何描述需要移动元素多少次呢？

这里直接给出概念，移动次数就等于逆序度。当然，也容易理解，移动完成后逆序度为0，那么移动次数自然等于逆序度。

来看下插入排序的代码——

/**
     * 插入排序
     */
    public void insertionSort(int[] a,int n){
        if(n == 1)
            return;
        //需要将未排序区间的n-1个元素放置到已排序区间合适的位置
        for(int i=1;i<n;i++){
            //记录要排序的值
            int value = a[i];
            int j = i-1;
            //已排序区间
            for(;j>=0;j--){
                if(a[j] > value){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
            //插入数据
            a[j+1] = value;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.4.2 插入排序分析

原地排序算法：比较数据交换元素时只需要常数级的空间，即空间复杂度为O(1);
稳定的排序算法：当遇到相同元素时，只需要将未排序数据中的元素插入到已排序相同元素的后面即可，因此也是稳定的排序算法。
时间复杂度：最好时间复杂度为O(N),最坏情况下，时间复杂度为O(N2).在分析平均时间复杂度时，可以看做是将n-1个数据分别插入到有序的数组中去，一次这样的过程时间复杂度为O(N),那么整个过程的平均时间复杂度就为O(N2)

1.5 选择排序

1.5.1 选择排序概述

选择排序的思路类似于插入排序，同样基于已排序区间和未排序区间的思路。不同的是，选择排序依次找出未排序区间中的最小元素，将其与未排序区间的第一个元素互换位置,排好序的部分作为已排序区间。

我们来看下面的小例子——

再来看下具体的代码实现——

/**
* 选择排序
*/
    public void selectSort(int[] a,int n){
        if(n == 0)
            return;
        //每一趟最小值的初始值
        for(int i=0;i<n-1;i++){
            int min = a[i];
            //标志位
            boolean isSwap = false;
            //记录最小值的下标
            int index = i;
            int j = i+1;
            for(;j<n;j++){
                //存在比最小值更小的值
                if(min > a[j]){
                    min = a[j];
                    //记录新的最小值的下标
                    index = j;
                    isSwap = true;
                }
            }
            //该趟中存在需要互换位置的元素
            if(isSwap){
                a[index] = a[i];
                a[i] = min;
            }
        }
    }
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

1.5.2 选择排序分析

原地排序算法：代码执行时只需要常数级的空间，即空间复杂度为O(1).
不稳定的算法：交换位置导致有可能颠倒相同值的相对位置，所以是不稳定的排序算法。
时间复杂度分析：最好，最坏，平均时间复杂度均为O(N2).

二. 排序下

摘要

在排序上中提及到了冒泡排序，选择排序，插入排序。这三种排序是因为时间复杂度较高，所以适用于规模小的数据排序，因为y = x 2曲线的数据规模较小时增长趋势并不快。但在实际项目开发中，动辄上万的数据排序，我们应该怎样处理呢？这就涉及到时间复杂度相对较小的快速排序与归并排序，这两种排序都是使用分治的编程思想，理解起来相对困难一点，但在面试时，出于他们性能折中又适用范围广的特点，因此成为面试的宠儿。好啦，接下来进入正题——

2.1 从一个问题开始

如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？

乍看上去，不管是快排还是归并排序，他们的时间复杂度都是O(NlogN),但使用分区技巧的快速排序在合并之前就已经是一个有序的数据集了。

假设原始的数据集是这样的：4,2,5,12,3,要找到第3大的元素4.

我们将数据已分区点为界分为三个区间，如果K等于分区点，则直接返回即可，假设不等于，我们就去递归的分治的另外两个区间，直到区间缩小为1.

来计算下时间复杂度：首先遍历数据集找到分区点，时间复杂度为O(n),第二次只需要分治一半的元素，也就是时间复杂度为O(n/2).递推得到第n次分治需要的时间复杂度为O(n/2的n-1次方)，最后一次不需要分治，时间复杂度为O(1)，把这些时间复杂度加起来，构成一个等比数列的求和，求和结果为2n-1,也就是时间复杂度为O(n).

2.2 归并排序

2.2.1 概述

归并排序是用分治的思想，将大问题分成小问题，小问题解决了，大问题自然也就解决了。

归并排序时，首先执行递，将数组从中间分成两部分，对这两部分分别进行分治，直到区间为1为止。然后是归的过程，依次排序合并每个小区间成大区间，直到得到排好序的数据集。

这样说总归是不形象的，我们来看下图解——

2.2.2 代码实现

有了大致的思路，我们来使用递归实现归并排序，既然是递归问题，那就先找递归终止条件和递归公式咯——

递归终止条件：
$merge_sort(p...r) = merge(merge_sort(p,q),merge_sort(q+1,r))$
递归公式：
$p > = r$

我们再将其转化为代码——

 /**
     * 归并排序
     */
    public static int[] mergeSort(int[] a,int n){
        mergeSort_s(a,0,n-1);
        return a;
    }

    private static void mergeSort_s(int[] a, int from, int to) {
        //递归终止条件
        if(from >= to)
            return;
        //得到该区间的中间位置
        int mid = (from+to)/2 ;
        //分治递归
        mergeSort_s(a, from, mid);
        mergeSort_s(a, mid + 1, to);
        merge(a,from,mid,to);
    }

    /**
     * 合并两个有序数组并返回
     * @param a
     * @param from
     * @param mid
     * @param to
     * @return
     */
    private static void merge(int[] a, int from, int mid, int to) {
        //申请一个临时数组来存储合并结果
        int[] tmp = new int[to-from+1];
        //合并
        int i = from,j = mid+1,k = 0;
        while(i<=mid && j<=to){
            if(a[i] <= a[j])
                tmp[k++] = a[i++];
            else{
                tmp[k++] = a[j++];
            }
        }
        //下面这句的思路好厉害！
        int start = i;
        int end = mid ;
        //右边还有剩余元素
        if(j <= to){
            start = j;
            end = to;
        }
        //拷贝剩余元素到tmp中
        while(start <= end){
            tmp[k++] = a[start++];
        }
        //拷贝临时数组到a中
        for(i=0;i<=to-from;i++){
            a[from+i] = tmp[i];
        }
    }
}
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
48
49
50
51
52
53
54
55
56
57
58

这里加点私货，在写归并排序代码的时候，犯了一个从来没有去主动意识的致命错误，这个错误就是在某些场景下，else要不要写？我们先分析一段代码——

public static void main(String[] args) {
        int res = 0;
        if (res == 0) {
            res = 1;
        }
        res = -1;
        System.out.println(res);
}
1
2
3
4
5
6
7
8

这是一段很简洁的代码，小伙伴们认为会输出什么呢？

我以前有些完整的if与else的习惯，今天犯懒了，索性没有写else，因为我认为if之后部分的第一行就是else的代码，但是真的是这样吗？

这里我没有写else，系统会认为else不执行任何事情，而不是默认执行if语句块后的第一行代码。

那么怎样的编程习惯更值得提倡呢？

先给出结论，if和else要写就写成对！，因为这样对测试人员友好一些，另外检测bug也容易检测出来，我们再延伸一下，什么情况下用if，什么情况下用if else.

if用于逻辑追加
if else用于逻辑分支

另外，针对硬件的设计，我们可以给出一个小技巧：为真的条件写在前面。

这是因为现代CPU并不会做逻辑判断，而是顺序执行，假如发现不满足条件，则会回滚并执行下一条语句。所以在写if,else的前提下尽可能将为真的条件写在前面。

2.2.3 性能分析

稳定的排序算法：归并排序的稳定与否取决于合并的方式，在合并时针对相同元素，不改变他们的相对位置即可。所以归并排序是稳定的排序算法。
时间复杂度分析：这里先给出一个结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。归并排序的时间复杂度包括子问题的时间复杂度与合并代码的时间复杂度加和。假设包括b和c两个子问题，则：
$T (a) = T (b) + T (c) + K$
这里的K指的是合并的时间复杂度，即为O(N).又因为两个子问题的时间复杂度都为O(N/2),则归并排序的时间复杂度为：
$$
T(1) = C\

T(n) = 2T(N/2)+N n>1
$我们求解后可以得到 — —$
T(n) = 2T(n/2) + n\
= 2*(2T(n/4) + n/2) + n = 4T(n/4) + 2n\
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n\
= 8*(2T(n/16) + n/8) + 3n = 16T(n/16) + 4n\
…\
= 2^k * T(n/2^k) + k * n\
…
$$
当T(n/2^k) = T(1)时，即k = log2N，将其带入上式，可以得到，T(n)=Cn+nlogn,即归并排序的时间复杂度为O(nlogn).
不是原地排序算法:归并排序用到递归的思想，所以自然不会是原地排序算法。那它的空间复杂度是什么呢?

在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

2.3 快速排序

2.3.1 概述

Java1.8源码中Arrays.sort()排序函数使用快速排序算法。

快速排序是用递归与分治，将数据集按照某个分区点分为比分区点小的区间和比分区间大的区间，然后在区间内再递归这项操作直到区间内只有一个元素为止。

既然是递归，我们同样写出递归终止条件和递推公式——
$递推公式： quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r) \\ 终止条件： p >= r$
到这，我们只需要选出适合的分区点即可，通常将区间内的最后一个元素作为分区点，然后将比分区点小的元素放到一个数组中，把比分区点大的元素放到一个数组中。

思路完全合理，但并不优雅，因为这意味着需要额外的空间。那怎样才能不申请额外空间呢？这里我们借助选择排序的思路，即核心是交换元素。

那归并与快排有什么区别呢？归并排序的处理过程是自下往上的，而快排则是自上往下的。

我们通过图解来认识排序的过程——

2.3.2 代码实现

/**
     * 快速排序
     */
    public static void quickSort(int[] a,int n){
        quickSort_c(a,0,n-1);
    }

    private static void quickSort_c(int[] a, int from, int to) {
        if(from >= to)
            return;
        int p = partition(a,from,to);
        quickSort_c(a,from,p-1);
        quickSort_c(a,p+1,to);
    }
    /**
     * 分区函数
     */
    private static int partition(int[] a, int from, int to) {
        //将最后一个元素作为分区点
        int pivot = a[to];
        int i = from;
        for(int j=from;j<to;j++){
            //小于分界点，则使用交换的方式将元素放到已排序区间
            if(a[j] < pivot){
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                //
                ++i;
            }
        }
        int tmp = a[to];
        a[to] = a[i];
        a[i] = tmp;
        return i;
    }
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

2.3.3 性能分析

这里不再推到具体过程，直接给出结论——

归并排序是一种不稳定的原地排序算法，它大部分情况下的时间复杂度为O(nlogn),只有个别情况下才会退化为O(n2)

三. 线性排序分析总结

3.1 前言

在已经学习了五种基于比较的排序算法的基础上，我们仍要继续学习三种特定场景下更优的不基于比较的排序算法，那我们肯定会困惑，为什么不基于比较的算法在某些场景下性能更优呢，换句话说，基于比较的算法有什么不能逾越的天花板呢？

这就需要引入CBA理论：任何基于比较的排序算法的性能天花板就是O(nlogn).我们来探究一下这个结论是如何得出的——

来自：https://yfsyfs.github.io/2019/05/25/CBA%E7%90%86%E8%AE%BA-%E4%B8%BA%E4%BB%80%E4%B9%88%E5%9F%BA%E4%BA%8E%E6%AF%94%E8%BE%83%E7%9A%84%E6%8E%92%E5%BA%8F%E6%96%B9%E6%B3%95%E7%9A%84%E6%80%A7%E8%83%BD%E6%9E%81%E9%99%90%E6%98%AFO-nlogn/

原因很简单, n个元素的全排列是n!. 而最终排序的结果只是其中一种（一棵含有n!个叶子节点的二叉树）. 每次比较, 我们可以砍掉一半的元素. 所以比较的次数就是树的高度.而此树的高度是
$log_2n!$
由分析数学中的Stirling公式便知.速度不可能突破NlogN.

既然是基因限制，那我们就有必要另辟蹊径，学习一下**时间复杂度为O(N)**的线性排序咯。

3.2 桶排序

3.2.1 概述

这三种排序方式都会用到桶，而桶排序的核心思想是将要排序的数据发到几个有序的桶里，每个桶里的数据再单独进行排序，排完序后再将每个桶中的数据按照顺序依次取出，组成的序列就是有序的了。

按照它的核心思想，我们来拆解一下桶排序的实现过程：

显然，桶的个数是首先应该被确定的，如果你再完后看的话，就会发现三种线性排序核心的区别就是桶的大小粒度不同，也就是每个桶中放的数据个数不同，就拿桶排序来说，它适用外部排序，也就是磁盘空间很充足，但内存不足,这就需要将磁盘中的文件分批地放入内存.

桶排序的桶的大小一般会预设好。所以桶的个数就等于数据的范围除以桶的大小。
接着就需要将数据按照映射函数的规则放置到对应的桶中。具体实现无非就是按大小分类到相应的桶下标。
然后自然就是排序啦，排序选用java封装的快排方法还是很舒适的，最后将排序后的桶元素放置到原数组即可。

复杂度分析

时间复杂度：假设有n个数据，分成m个桶，那每个桶中就有数据k=n/m个，每个桶中使用快排，时间复杂度为O(klogk),代入后可以得到O(n/mlog(n/m)),那总体的时间复杂度就是
$O (n l o g (n / m))$
当桶的个数趋近与数据量时，桶排序的时间复杂度就可看做O(N).
空间复杂度：在将源数据分配到对应的桶时需要申请额外的空间，所以N个数据就需要额外申请N个空间，也就是空间复杂度为O(N).

总结

桶排序堆排序数据的要求很苛刻，首先，要排序的数据需要很容易就能划分成m个桶，并且，桶和桶之间之间有着天然的大小关系。其次，数据在每个桶中的分布是比较均匀的，如果将数据都划分到同一个桶中，就会退化为O(nlogn)的排序算法啦。

3.2.2 趣味图解

3.2.3 代码演示

package com.practice.sort;

import java.util.Arrays;

/**
 *桶排序
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] arry = {1,4,2,6,3,5,3,rry,2);
        for (int value:arry};
        arry = sort(arry) {
            System.out.print(value+" ");
        }
    }

    private static int[] sort(int[] sourceArr,int bucketSize){
        //首先拷贝数据,防止源数据因为没有备份而乱序
        int[] arr = Arrays.copyOf(sourceArr, sourceArr.length);
        return BucketSort(arr,5);
    }

    private static int[] BucketSort(int[] arr,int bucketSize){
        //根据最小值，最大值确定分多少个桶
        int max = arr[0];
        int min = arr[0];
        for (int data:arr) {
            if(data > max){
                max = data;
            }else if(data < min){
                min = data;
            }
        }
        //确定桶数的原则
        int bucketCount = (int)Math.floor((max-min)/bucketSize)+1;
        //声明桶的标号
        int[][] buckets = new int[bucketCount][0];
        //通过映射函数将数据放到桶中
        for(int i=0;i<arr.length;i++){
            //确定数据对应的桶下标
            int index = (int)Math.floor(arr[i]-min)/bucketSize;
            //扩充二维数组对应行的列
            buckets[index] = arrAppand(buckets[index], arr[i]);
        }
        int arryIndex = 0;
        //为每个桶排序
        for (int[] bucket:buckets) {
            //特判
            if(bucket.length <= 0)
                continue;
            Arrays.sort(bucket);
            for (int value:bucket) {
                arr[arryIndex++] = value;
            }
        }
        return arr;
    }

    /**
     * 动态扩容,并保存数据
     */
    private static int[] arrAppand(int[] arr,int value){
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length-1] = value;
        return arr;
    }
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

3.3 计数排序

3.3.1 概述

计数排序可以看做是桶排序的一种特殊情况，当要排序的数据所处的范围并不大时，我们将按数据最大值作为痛的个数，这样就省却了桶内排序的时间。

我们同样聊聊来计数排序的实现：

类似于桶排序，计数排序同样首先确定桶的个数，这个就不再赘述。
然后，我们需要将源数据分配到对应的桶中，显然，如果分配到了对应的桶中，排序就已经完成了。那如何分配呢？

这个环节就是计数排序的核心啦——

假设有一组数据A[8]:2,5,3,0,2,3,0,3,我们首先遍历一遍数据，得到对应数据的个数C[6]——

再对数据做顺序求和：

也就是说C[i]里面存储的是小于等于I的数据个数。

最后的最后，最容易蒙圈的一步——

逆序遍历数组，然后在数组C中找到与其相同的下标，然后通过下标对应的元素确定排序后数据的下标，再将个数减1。

王争老师的图绝了，非常有用！！！

复杂度分析

时间复杂度：计数的量级最大，但也不过于O(N).
空间复杂度：只需要额外申请一个计数数组，即计数的桶，则空间复杂度为O(N).

总结

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

3.3.2 趣味图解

3.3.3 代码演示

package com.practice.sort;

/**
 * 计数排序
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] arry = {1,5,2,4,3};
        countSort(arry,arry.length);
        for (int value:arry) {
            System.out.print(value+" ");
        }
    }

    private static void countSort(int[] arry,int n){
        //特判
        if(n <= 1)
            return ;
        //计数排序的特征：值的范围小，将最大值作为桶的个数
        int max = arry[0];
        for(int i=0;i<n;i++){
            if(arry[i] > max){
                max = arry[i];
            }
        }
        int bucketCount = max+1;
        //声明并初始化桶
        int[] buckets = new int[bucketCount];
        for(int j=0;j<buckets.length;j++){
            buckets[j] = 0;
        }
        //计数
        for (int value:arry) {
            ++buckets[value];
        }
        //累加
        for(int k=1;k<buckets.length;k++){
            buckets[k] += buckets[k-1];
        }
        //声明用于存储结果的tmp
        int[] tmp = new int[arry.length];
        //猎杀时刻~
        for(int m=n-1;m>=0;m--){
            int index = buckets[arry[m]]-1;
            tmp[index] = arry[m];
            buckets[arry[m]]--;
        }
        for(int i=0;i<n;i++){
            arry[i] = tmp[i];
        }
    }
}
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
48
49
50
51
52

3.4 基数排序

3.4.1 概述

基数排序要求数据可以划分成高低位，位之间有递进关系，比较两个数，我们只需要比较高位，高位相同再去比较低位，而且每一位的数据范围不能太大，因为基数排序需要借助桶排序或者计数排序来完成每一位的排序。

还是熟悉的配方，我们来复现一下实现的过程——

首先根据数据中的最大值位数确定桶的个数。
接着按位逆序排序，我们这里只考虑通过最后一位对数据的划分：

通过取余运算得到的余数即为桶对应的下标，这里将数据分配到桶可以使用二维数组实现，最后将桶中的元素按序放回数组，准备下一位的比较。

3.4.2 趣味图解

3.4.3 代码演示

package com.practice.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arry = {2,5,24,12,30,50,0};
        radixSort(arry,arry.length);
        for (int value:arry) {
            System.out.print(value+" ");
        }
    }

    private static void radixSort(int[] arry,int n){
        //确定桶的个数
        int max = arry[0];
        for(int i=1;i<arry.length;i++){
            if(max < arry[i]){
                max = arry[i];
            }
        }
        //得到它的位数
        int bitCount = getBitCount(max);
        //按位逆序排序,首先声明除数和余数
        int mod = 10;
        int dev = 1;
        //bitcount趟比较
        for(int j=0;j<bitCount;j++,mod*=10,dev*=10){
            //声明临时数组
            int[][] tmp = new int[mod * 2][0];
            //将数据按照当前位放置到对应的桶中
            for(int k=0;k<arry.length;k++){
                //最好手绘验证一下
                int bucket = (arry[k]%mod)/dev+mod;
                tmp[bucket] = arryAppand(tmp[bucket],arry[k]);
            }
            //分别遍历每个桶中的元素，并将它们按序再放回数组中
            int pos = 0;
            for (int[] bucket:tmp) {
                for(int value:bucket){
                    arry[pos++] = value;
                }
            }
        }
    }

    /**
     * 数组扩容并保存
     * @param arry
     * @param value
     * @return
     */
    private static int[] arryAppand(int[] arry, int value) {
        arry = Arrays.copyOf(arry, arry.length + 1);
        arry[arry.length-1] = value;
        return arry;
    }

    /**
     * 获取整数位数
     * @param value
     * @return
     */
    private static int getBitCount(int value){
        if(value == 0)
            return 1;
        int count = 0;
        while(value > 0){
            value /=10;
            count++;
        }
        return count;
    }

}

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

日拱一卒，功不唐捐。

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