Java八大排序算法

https://moonshuo.cn/posts/61237.html

冒泡排序

public class BubbleSort {
    //这个冒泡排序我们使用从小到大进行排序
    public int[] sort1(int []array){
        long count=0;
        for (int i=0;i<array.length;i++){
            for (int j=0;j<array.length-1;j++){
                if (array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;

                }
                count++;
            }
        }
        System.out.println("总共走了"+count+"次循环");
        return array;
    }

    public static void main(String[] args) {
        BubbleSort bubbleSort=new BubbleSort();
        System.out.println(Arrays.toString(bubbleSort.sort1(new int[]{1, 5, 6, 2, 8, 6, 4})));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这里的时间复杂度为n*n-1，这里没有进行优化，不在中间进行判断排序提前结束，强制执行这么多次循环

我们仔细观察这个冒泡排序，可以每一次进行排序完毕，其实都可以确定一个最大值，所以我们可以改进代码，也就是每一次执行得到的最大值，可以不进行循环遍历了，可以在确定的最大值之前提前结束

这里的复杂度为n-1+…+1=(n-1+1)*(n-1)/2

优化

其实到上面的冒泡排序已经比较完整，但是我们发现如果数组已经是排好序的，还是会循环这么多次，同时其他情况也会出现提前排序结束的情况，这个时候其实后面的排序就会多余，当整个过程没有交换发生的时候，其实排序已经完成

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-15 11:06:39
 * @description
 */
public class BubbleSort {
    //这个冒泡排序我们使用从小到大进行排序
    public int[] sort1(int []array){
        int count=0;
        for (int i=0;i<array.length;i++){
            boolean flag=false;
            for (int j=0;j<array.length-i-1;j++){
                if (array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    //发生交换，flag为true
                    flag=true;
                }
                count++;
            }
            if (!flag){
                System.out.println("提前结束，总共走了"+count+"次循环");
                return array;
            }
        }
        System.out.println("总共走了"+count+"次循环");
        return array;
    }

    public static void main(String[] args) {
        BubbleSort bubbleSort=new BubbleSort();
        System.out.println(Arrays.toString(bubbleSort.sort1(new int[]{1,2,3,5,7,6})));
    }
}
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

选择排序

选择排序又叫最小选择排序，每一次选择最小的元素与前面的元素进行交换

//这种方式进行排序的过程中，需要经过n-1+n-2+....+1+0=(n-1)*n/2
public int[] sort1(int []array){
        long count=0;
        for (int i=0;i<array.length-1;i++){
            int temp=array[i];
            int index=i;
            for (int j=i;j<array.length-1;j++){
                if (temp>array[j+1]){
                     temp=array[j+1];
                     index=j+1;
                }
                count++;
            }
            array[index]=array[i];
            array[i]=temp;
        }
        System.out.println("一共经过了"+count+"次循环");
        return array;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

其实相比较来说，选择排序是不稳定的，比如5，4，5，2，1我们在排序的过程中我们将第一个5与2交换，这样导致第一个5变成了第二个5，如果仅仅是数字排序问题可能不大，但是如果数字表示某一种含义，会导致问题发发生。

速度比较

这里的选择排序和冒泡排序其实时间复杂度都为n(n-1)/2,不考虑冒泡提前结束，那么这两个排序算法的效率如何？？？

		long beginTime=System.currentTimeMillis();
        selectionSort.sort1(array);
        long overTime=System.currentTimeMillis();
        System.out.println("选择排序时间为"+(overTime-beginTime));


        long beginTime1=System.currentTimeMillis();
        bubbleSort.sort1(array1);
        long overTime1=System.currentTimeMillis();
        System.out.println("冒泡排序时间为"+(overTime1-beginTime1));
1
2
3
4
5
6
7
8
9
10

这里虽然两个排序对应的数组相同，但是数组的大小相同，并不会影响结果，我们多的测试几下，看最终的结果

最终导致这种差异的原因是什么？？？，在这个过程中循环次数相同，那么最终导致结果不同的原因是因为冒泡排序在一次循环过程中交换的次数比较多，耗费时间，而选择排序一次循环仅仅进行一次交换

插入排序

插入排序的思想是我们刚开始进行排序的时候，从第二个数开始，依次与前面的数进行比较，找到对应的位置，并插入其中

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-19 09:20:43
 * @description
 */
public class InsertionSort {
    public int[] sort1(int []arr){
        long count =0;
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
                count++;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        System.out.println("循环了"+count+"次");
        return arr;
    }


    public static void main(String[] args) {
        InsertionSort insertionSort=new InsertionSort();
        System.out.println(Arrays.toString(insertionSort.sort1(new int[]{5, 8, 9, 7, 5, 1, 5, 68})));
    }
}

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

与其他排序算法比较

插入排序和冒泡排序对比 - 知乎 (zhihu.com)，在这个过程之中，冒泡排序位置交换进行了三次，而插入排序进行了位置交换进行了一次

在插入排序中，比如34,8,64,51,32,21存在9个逆序，即（34，8）、（34，32）…（32，21），而这9个逆序，则是我们排序中执行的交换的次数，我们假设一个数组的逆序数为I,那么插入排序的运行时间为O(N+I)

希尔排序

对于插入排序，每一次需要将下一个元素插入对应的位置，而这个过程需要不断的和前面的数进行比较，如果要插入的数比较小，那么可以知道他需要比较很多次才可以找到对应的位置。

希尔排序是插入排序一个更高版本的排序，又叫做缩小增量排序

希尔排序算法（排序详解）_lghhtoto的博客-CSDN博客_希尔排序算法

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 10:26:15
 * @description
 */
public class HillSort {
    public void sort1(int[] array) {
        for (int gap = array.length / 2; gap > 0; gap = gap / 2) {
            //这里定义gap是相当于定义了从gap开始插入操作
            for (int i = gap; i < array.length; i++) {
                int j = i;
                int temp = array[i];
                while (j - gap >= 0 && temp < array[j - gap]) {
                    array[j] = array[j - gap];
                    j = j - gap;
                }
                if (j != i) {
                    array[j] = temp;
                }
            }
            System.out.println("本次排序完毕数组为" + Arrays.toString(array));
        }
    }

    public static void main(String[] args) {
        HillSort hillSort = new HillSort();
        hillSort.sort1(new int[]{9, 1, 2, 5, 7, 4, 8, 6, 3, 5});
    }
}
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

这里只是将希尔排序的编码写了出来，但是其实这个希尔排序并不是稳定的排序，加入现在是6，5，5，9，那么经过一次排序之后，我们会将第二个5调用到第一个前面。

速度比较

我们现在比较希尔排序与插入排序的速度

public static void main(String[] args) {
        SelectionSort selectionSort=new SelectionSort();
        BubbleSort bubbleSort=new BubbleSort();
        InsertionSort insertionSort=new InsertionSort();
        HillSort hillSort=new HillSort();
        int []array=new int[100000];
        int []array1=new int[100000];
        int []array2=new int[100000];
        int []array3=new int[100000];
        for (int i=0;i<array.length;i++){
            array[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array1.length;i++){
            array1[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array2.length;i++){
            array2[i]= (int) (Math.random()*(100000));
        }
        for (int i=0;i<array3.length;i++){
            array3[i]= (int) (Math.random()*(100000));
        }

        long beginTime=System.currentTimeMillis();
        selectionSort.sort1(array);
        long overTime=System.currentTimeMillis();
        System.out.println("选择排序时间为"+(overTime-beginTime));


        long beginTime1=System.currentTimeMillis();
        bubbleSort.sort1(array1);
        long overTime1=System.currentTimeMillis();
        System.out.println("冒泡排序时间为"+(overTime1-beginTime1));

        long beginTime2=System.currentTimeMillis();
        insertionSort.sort1(array2);
        long overTime2=System.currentTimeMillis();
        System.out.println("插入排序时间为"+(overTime2-beginTime2));

        long beginTime3=System.currentTimeMillis();
        hillSort.sort1(array3);
        long overTime3=System.currentTimeMillis();
        System.out.println("希尔排序时间为"+(overTime3-beginTime3));
    }
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

现在我们总结一下各个排序算法的为什么时间会加快？？？

快速排序

我们先来看快速排序的示意图

我们首先选取基准值，这里选择第一个为基准值，将比其小的值放到前面，将比其大的值放到后面，为了实现这个目标我们

初始数组，我们设置初始值为6，现在我们设置一个left指针和right指针分别指向除开6之外的第一个数和最后一个数，left用红色，right用绿色

现在我们开始寻找，left负责寻找比6大的数，而right寻找比6小的数，知道之后，将两个进行交换，记住left与right不能同时移动，必须有一个找到符合条件的位置之后，才可以移动另外一个

交换之后，变为下面的函数

紧接着，继续移动，找到之后，进行交换

交换之后，继续移动，发现right与left相遇了，此时，将6与相遇的地方进行交换

交换之后，结束第一轮交换，此时完成目标

然后我们在将6左边的部分与右边的部分都进行相应的运算，下面以左边为举例

3 1 2 5 4

这个时候我们首先移动right指针，检测到2小于3，此时再移动left，移动一下发现在2相遇，则2与3发生交换

2 1 3 5 4

对2 1，在开始便相遇的，交换21成为12

首先给大家展示一个错误的写法，

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 18:28:47
 * @description
 */
public class QuickSort {
    public void sort1(int []array,int left,int right){
        if (left>right){
            return;
        }
        int refValue=array[left];
        int i=left+1;
        int j=right;
        while (i<j){
            //从右边找比基准值小的数
            while (refValue<array[j]&&j>i){
                j--;
            }
            //从左边寻找到比基准值大的数
            while (refValue>array[i]&&j>i){
                i++;
            }
            if (j>i) {
                //都找成功之后，交换值
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //当i==j的时候
        array[left]=array[j];
        array[j]=refValue;
        //左右边都进行相应操作
        System.out.println("本次交换完毕，数组变为"+ Arrays.toString(array));
        sort1(array,left,i-1);
        sort1(array,i+1,right);
    }

    public static void main(String[] args) {
        QuickSort quickSort=new QuickSort();
        int []array=new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSort.sort1(array,0,array.length-1);

    }
}
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

这是我犯的错误，比较愚蠢

仔细看这个报的错误以及前面输出的例子，前三行还是没有问题的，但是第四行发生了问题，是什么问题的导致的？？？

其实这里的思路没有问题的，问题出现在我们递归调用的方式上面，下面我们看一下递归调用的顺序

所以说我们现在需要解决这个循环问题，同时使得交换能够正常进行，微调一下即可

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-20 18:28:47
 * @description
 */
public class QuickSort {
    public void sort1(int []array,int left,int right){
        if (left>=right){
            return;
        }
        int refValue=array[left];
        int i=left;
        int j=right;
        while (i<j){
            //从右边找比基准值小的数
            while (refValue<=array[j]&&j>i){
                j--;
            }
            //从左边寻找到比基准值大的数
            while (refValue>=array[i]&&j>i){
                i++;
            }
            if (j>i) {
                //都找成功之后，交换值
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //当i==j的时候
        array[left]=array[j];
        array[j]=refValue;
        //左右边都进行相应操作
        System.out.println("本次交换完毕，数组变为"+ Arrays.toString(array));
        sort1(array,left,i-1);
        sort1(array,i+1,right);
    }

    public static void main(String[] args) {
        QuickSort quickSort=new QuickSort();
        int []array=new int[]{6,1,2,7,9,3,4,5,10,8};
        quickSort.sort1(array,0,array.length-1);

    }
}
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

优化

其实在这个过程之中，基准值的选择对于算法的速度有较大的影响，如果这个数组是随机的，没有预排序，那么选取第一个元素可能没有什么影响，但是如果此时数组已经是正序或者反序，那么对速度的影响比较大

上述的例子中加入一开始便是

12345678910，那么这个便会将2345678910都划入右边，同时下一次之中也会将345678910也都划入右边，这样循环需要不断右递归10次，那么快速排序的花费时间是o(n*n),这样的话快速排序的又是就不会存在

所以说我们要找到一个合适的基准值

在这种情况下，我们可以发现其实中值是最好的选择，但是如果过我们使用中值，这个过程反而会拖累速度，所以我们采用选择arr[0],arr[（0+length-1）/2],a[length-1]中中间值的数

public int getRefValue(int[] array,int left,int right){
    int center=(left+right)/2;
    if (array[left]<array[center]){
        swapReferences(array,left,center);
    }
    if (array[right]<array[left]){
        swapReferences(array,left,right);
    }
    if (array[right]<array[center]){
        swapReferences(array,center,right);
    }

    return array[left];

}
//这一段来自《数据结构与算法分析Java版》，final会加快执行，但是不知道为什么，插眼！！！！

public final void swapReferences(int []array,int index1,int index2){
    int temp=array[index1];
    array[index1]=array[index2];
    array[index2]=temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

归并排序

图片来自：【算法】排序算法之归并排序 - 知乎 (zhihu.com)

这个算法中基本的操作是合并两个已经排序的表，应为这两个表已经排序，所以将输出放到第三个表格中，该算法可以通过对输入数据的一趟排序来完成。

基本的排序算法是两个已经排好序的数组A与B,一个输出数组C

将AB指针指向的位置不断比较大小，小的进入到C中，对应指针++

如果一方先完成，则将剩余的全部加入到C中，此时A已经完成

B不需要比较直接加入即可

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-06-21 10:15:23
 * @description
 */
public class MergeSort {
    //判断是否继续排序
    public void judgeSort(int[] array,int []tempArr,int left,int right){
        if (left<right){
            int center=(left+right)/2;
            judgeSort(array,tempArr,left,center);
            judgeSort(array,tempArr,center+1,right);
            //如果满足条件，则开始排序
            sort(array,tempArr,left,center+1,right);
        }
    }

    //制造临时数组
    public  void makeArray(int []array){
        int []tempArr=new int[array.length];
        judgeSort(array,tempArr,0,array.length-1);
    }

    public void sort(int []array,int []tempArr,int left,int center,int right){
        //我们分析两个数组，发现这两个数组的边界为left~center-1和center~right
        int leftEnd=center-1;
        int tempLeft=left;
        int tempCenter=center;
        //定义开始存储数组的位置
        int tempArrIndex=left;
        //当两个数组都在范围之内的时候
        while (tempLeft<=leftEnd&&tempCenter<=right){
            if (array[tempLeft]<=array[tempCenter]){
                tempArr[tempArrIndex]=array[tempLeft];
                tempLeft++;
                tempArrIndex++;
            }else {
                tempArr[tempArrIndex]=array[tempCenter];
                tempCenter++;
                tempArrIndex++;
            }
        }
        //当结束的时候，我们将另外一个数组中的未赋值的元素全部加入其中
        while (tempLeft<=leftEnd){
            tempArr[tempArrIndex++]=array[tempLeft++];
        }
        while (tempCenter<=right){
            tempArr[tempArrIndex++]=array[tempCenter++];
        }

        //全部赋值完毕之后，将这个数放到其中
        if (right + 1 - left >= 0) {
            System.arraycopy(tempArr, left, array, left, right + 1 - left);
        }
        System.out.println(Arrays.toString(array));
    }

    public static void main(String[] args) {
        MergeSort mergeSort=new MergeSort();
        mergeSort.makeArray(new int[]{14,12,15,13,11,16});
    }

}
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

《数据结构与算法分析》：虽然归并排序的运行时间是较小的，但是合并两个已经排序的表用到线性附加内存中，在整个算法中还要花费将数据拷贝到临时数组在拷贝回来的这样的附加操作，明显减慢了速度。

与其他排序算法比较，归并排序的运行时间严重依赖比较数组和数组移动的开销，这些开销与语言有关，在Java中执行一次泛型排序，进行一次元素排序是昂贵的，但是移动元素是省时的，因为特们是引用赋值，而不是对象拷贝。归并排序是所有排序算法中比较次数最小的，在Java中是较好的选择。

​ p287页

只能看懂一部分<(￣︶￣)↗[GO!]

堆排序

堆排序是利用堆的方法进行的排序，堆分为大顶堆与小顶堆，其中的大顶堆是中间节点永远比两边的大，而小顶堆则是中间节点比两边的节点小

此时我们按照堆的节点进行排序，映射之后得到数组

堆排序思路

将待排序的序列构造成一个大顶堆，此时，整个序列最大值就是中间节点，将其与尾部元素进行交换，此时尾部成为最大值，将n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复。

而堆排序的难点是构造大顶堆或者小顶堆，假设原先的堆结构如下

现在我们需要从最底层的非叶子节点开始比较，逐个将这个堆调节成大顶堆

错误代码

package 排序;

/**
 * @author 21050
 * @date 2022-07-03 09:14:29
 * @description
 */

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5,6,8,96,1,5,82,3,8,53,5,7,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int length=arr.length;
        //我们首先构造大顶堆，而对于长度为length的数组来说，除去叶子节点，其节点有length/2-1个，也就是说除去叶子节点右边的节点代表序列为length/2-1
        //从节点开始依次向上构造大顶堆
        for (int j=length;j>0;j--){
            for (int i=j/2-1;i>=0;i--){
                percDown(arr,i,j);
            }
            //构造完毕之后我们进行交换
            int temp=arr[j-1];
            arr[j-1]=arr[0];
            arr[0]=temp;
        }
    }

    /**
     * i表示我们要调整比较的中间节点在数组的位置
     * 这个函数使得一个节点和左右节点完成大顶堆
     */
    public static void percDown(int[] arr, int i, int length) {
        int temp=arr[i];
        //那么我们可以得知这个左节点为2i+1
        int leftChild = 2 * i + 1;
        int child;
        //现在我们需要找出左节点，右节点，和中间节点的最大值
        //leftChild!=length-1表示判断是否存在右节点，arr[leftChild]<arr[leftChild+1]比较左右两个节点的大小
        if (leftChild < length - 1 && arr[leftChild] < arr[leftChild + 1]) {
            //如果说右节点比较大
            child = leftChild + 1;
        } else {
            child = leftChild;
        }
        //如果temp小于左右节点中比较大的节点，那么交换位置
        if (temp < arr[child]) {
            arr[i] = arr[child];
            arr[child] = temp;
        }
    }

}
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

以上的代码虽然可以实现了排序但是，这个过程还是存在错误，这只是一个顾头不顾屁股的错误的方法，错在并没有实现大顶堆，只是将最大值筛选出来，下面看一下过程

那么初始为

第一次交换为

紧接着轮换到498这个节点，交换完毕之后变为

然后在将9与6交换位置

其实根据我写的代码分析，到这里已经交换完毕，但是其实此时并没有实现大顶堆，这只是一个冒泡排序的变种，每一次筛选出最大值

所以说我们在堆上面的元素排序时，还要注意是否影响到了下面元素的大顶堆的操作

正确代码

package 排序;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int []arr= {4,6,8,5,9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 堆排序
     */
    private static void sort(int[] arr) {
        // 1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--)
        {
            // 从第一个非叶子节点从下到上，从右往左调整结构
            adjustHeap(arr,i,arr.length);
        }
        // 2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--)
        {
            // 将堆顶元素与末尾元素进行交换
            swap(arr,0,j);
            // 重新对堆进行调整
            adjustHeap(arr, 0, j);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int temp=arr[i];
        // 从i节点的左子节点开始，也就是2*i+1 然后继续往下调整 就是保证以他为首的树是大根堆
        for(int k=i*2+1;k<length;k=k*2+1)
        {
            // 如果左子节点小于右子节点，k指向右子节点
            if(k+1<length&&arr[k]<arr[k+1]){
                k++;
            }

            // 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            //找到第一个需要交换的点
            if(arr[k]>temp) {
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;//将temp值放到最终的位置
    }
}
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

这个代码与上面的不同的特点是在检测每一个节点的时候，不单单检测此节点是否符合特点，还检测是否会影响到子节点

比如变换496节点变换的时候，通过for循环的检测，会对一次变换的元素进行检测

变换为，但是子节点不符合大顶堆的定义，继续进行变换

这样才算变化完毕

基数排序

基数排序是桶排序的一种优化，基数排序将0123456789看成10个桶，每一位数进行之后可以得到一个正确的排序

1.10 基数排序 | 菜鸟教程 (runoob.com)

基本思想：基数排序是将整数按照位数分割为不同的数字，每一个位数进行比较。

实现逻辑：

1. 将所有待比较的数统一为同样的数位长度，数位较短的前面补0
2. 从低位开始，依次进行排序
3. 这样从最低位排序一直到最高位排序完成后，数列变为一个有序数列

现在我们比较这个需要确定的两点：

1. 基数排序循环到数组的次数如何确定？ 根据最大位数进行确定，比如上面的列子，最大位数为2，则需要循环到数组中两次
2. 如何在存储这些排序的每一次排序的结果可以使用二维数组的方法，第一行代码对应的位数，而剩下的代表对应的可能存储的数

思考

package 排序;

import java.util.Arrays;

/**
 * @author 21050
 * @date 2022-07-03 14:51:26
 * @description
 */
public class RadixSort {
    public void sort(int[] array) {
        int maxLength = getMaxLength(array);
        //需循环maxLength才可以将所有位数比较完毕
        for (int i = 0; i < maxLength; i++) {
            //建立一个array.length行，10列的二维数组，列数为0，代表存储为0的数,其中第一行的数代表已经存入数的个数
            int[][] arr = new int[array.length][10];
            //每一次循环分割出1位进行比较，并存入对应的数组中
            for (int j = 0; j < array.length; j++) {
                //假设这是第一次循环，则应该分割出个位，第二次则应该分割出十位
                String str = array[j] + "";
                int temp = 0;
                if (str.length() - 1 - i >= 0) {
                    temp = Integer.parseInt(str.substring(str.length() - 1 - i, str.length() - i));
                }
                //将得到的数存入数组中,并且计数+1
                arr[0][temp]++;
                //计数为1，则存入第一行，计数为2，则存入第二行
                arr[arr[0][temp]][temp] = array[j];
            }
            //第一轮循环完毕，我们要将二维数组的数重新存入array数组中
            int flag=0;
            for (int k=0;k<arr[0].length;k++){
                int m=arr[0][k];
                int count=1;
                while (m>=count){
                    array[flag]=arr[count][k];
                    count++;
                    flag++;
                }
            }
            System.out.println("经过第"+(i+1)+"次循环，数组变为"+ Arrays.toString(array));
        }
    }

    //将数字转换为字符串，根据str.length可以直接得到位数
    public int getMaxLength(int[] array) {
        int maxLength = (array[0] + "").length();
        for (int i = 1; i < array.length; i++) {
            String str = array[i] + "";
            int temp = str.length();
            if (temp > maxLength) {
                maxLength = temp;
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int []arr=new int[]{15, 89, 5, 63, 4, 75, 2};
        radixSort.sort(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

上述的代码时根据排序的思路得到的，我们可以看到在中间其实经过了很多for循环，我们看一看别人的代码

别人代码

这是一种比较主流的代码，仔细查看我们可以看出在得到循环次数（也就是最大位数）的代码不同，上面是通过字符串进行比较，而这里是通过乘法进行比较。而在存储的方面这里使用了Java的api中ArrayList进行存储，操作更加方便，而上面的代码实现是更加原始的代码，更加清晰中间的替换过程

import java.util.ArrayList;
 
public class Main {
 
    public static void main(String[] args) {
        int[] arr = new int[] { 321, 1234, 543, 324, 24, 960, 540, 672, 783, 1000 };
        radixSort(arr);
        printArray(arr);
    }
 
    public static void radixSort(int[] arr) {
        int digit = getMaxDigit(arr); // 获取最大的数是多少位
        for (int i = 0; i < digit; i++) {
            bucketSort(arr, i); // 执行 digit 次 bucketSort 排序即可
        }
    }
 
    public static int getMaxDigit(int[] arr) {
        int digit = 1; // 默认只有一位
        int base = 10; // 十进制每多一位，代表其值大了10倍
        for (int i : arr) {
            while (i > base) {
                digit++;
                base *= 10;
            }
        }
        return digit;
    }
 
    public static void bucketSort(int[] arr, int digit) {
        int base = (int) Math.pow(10, digit);
        // init buckets
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) { // 只有0~9这十个数，所以准备十个桶
            buckets.add(new ArrayList<Integer>());
        }
        // sort
        for (int i : arr) {
            int index = i / base % 10;
            buckets.get(index).add(i);
        }
        // output: copy back to arr
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (int i : bucket) {
                arr[index++] = i;
            }
        }
    }
 
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[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

计数基数排序

技术基数排序是对计数排序的优化，不用使用那么临时二维数组进行存储，for循环复杂度也下降

假如初始的数组如下：

我们统计个位数的个数

现在我们将每一个位数进行进行累加和

那么根据第二个表格的顺序，我们可以得到这一次排列之后顺序为

122-56-956-78

接下来我们对十位进行检验，然后是百位，最终可以得到正确的排序

计数基数排序法_sherilindas的博客-CSDN博客_计数基数排序

感觉差一点东西，回来在写，插眼