1. 关系

常见的八大排序算法，他们之间关系如下：
此处输入图片的描述

2. 插入排序

2.1 直接插入排序

2.1.1 基本思想

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

2.1.2 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

动态效果如下：
此处输入图片的描述

注意：
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

2.1.3 算法实现

public class Main {
    public static void main(String[] args) {
        int[] list1=new int []{2,4,1,6,2,3};
        int[] list2=new int []{2,4,1,6,2,3};
        System.out.println(Arrays.toString(sort1(list1)));
        System.out.println(Arrays.toString(sort1(list2)));
    }
    /**
     * 通过交换进行插入排序
     * @param list
     * @return
     */
    public static int[] sort1(int[] list){
        for (int i = 0; i < list.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (list[j] < list[j - 1]) {
                    int temp = list[j];
                    list[j] = list[j - 1];
                    list[j - 1] = temp;
                }
            }
        }
        return list;
    }


    /**
     * 通过将较大的元素都向右移动实现插入排序
     * @param list
     * @return
     */
    public static int[] sort2(int[] list) {
        for (int i = 1; i < list.length; i++) {
            int j;
            for (j = i; j > 0 && list[i] < list[j - 1]; j--) {
                list[j] = list[j - 1];
            }
            list[j] = list[i];
        }
        return list;
    }
}
运行结果：
[1, 2, 2, 3, 4, 6]
[1, 2, 2, 3, 4, 6]

2.1.4 复杂度分析

直接插入排序复杂度如下：

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n²)	O(n²)	O(1)

2.1.5 比较与总结

插入排序所需的时间取决于输入元素的初始顺序。例如，对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多。

2.2. 希尔排序

2.2.1 简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

2.2.2 基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。更好的步长序列取值可以参考维基百科。

2.2.3 算法描述

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1
时，整个序列作为一个表来处理，表长度即为整个序列的长度。

效果如下：
此处输入图片的描述

2.2.4 算法实现

public class Main {
    public static void main(String[] args) {
        int[] list1=new int []{2,4,1,6,2,3};
        System.out.println(Arrays.toString(sort(list1)));
    }
    public static int[] sort(int[] list) {
        int length = list.length;
        int h = 1;
        while (h < length / 3) h = 3 * h + 1;
        for (; h >= 1; h /= 3) {
            for (int i = 0; i < list.length - h; i += h) {//直接插入排序
                for (int j = i + h; j > 0; j -= h) {
                    if (list[j] < list[j - h]) {
                        int temp = list[j];
                        list[j] = list[j - h];
                        list[j - h] = temp;
                    }
                }
            }
        }
        return list;
    }
}
运行结果：
[1, 2, 2, 3, 4, 6]

2.2.5 步长取法

增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

2.2.6 复杂度分析

以下是希尔排序复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
$O(nlog_2 n)$	$O(nlog_2 n)$	$O(nlog_2 n)$	O(1)

2.2.7 总结与思考

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

3. 选择排序

3.1 简单选择排序

3.1.1 基本思想

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

3.1.2 算法描述

从未排序序列中，找到关键字最小的元素
如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
重复1、2步，直到排序结束。

动图效果如下所示：
此处输入图片的描述

3.1.3 算法实现

public class Main {
    public static void main(String[] args) {
        int[] list1 = new int[]{2, 4, 1, 6, 2, 3};
        System.out.println(Arrays.toString(sort(list1)));
    }

    private static int[] sort(int[] list) {
        for (int i = 0; i < list.length; i++) {
            int min = i;
            //选出之后待排序中值最小的位置
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[min]) {
                    min = j;
                }
            }
            //最小值不等于当前值时进行交换
            if (i != min) {
                int temp = list[min];
                list[min] = list[i];
                list[i] = temp;
            }
        }
        return list;
    }
}
运行结果：
[1, 2, 2, 3, 4, 6]

3.1.4 复杂度分析

以下是选择排序复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n²)	O(n²)	O(1)

3.1.5 总结与思考

选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。唯一值得高兴的是，它并不耗费额外的内存空间

3.2 堆排序

3.2.1 堆的概念

堆：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。
利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，我们通过大顶堆来实现。
把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。

3.2.2 基本思想

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

3.2.3 算法描述

先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换,
由此得到新的无序区K[1..n−1]和有序区K[n]
交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤2,直到无序区只有一个元素时停止。

动图效果如下所示：
此处输入图片的描述

3.2.4 算法实现

public class Main {
    public static void main(String[] args) {
        int[] list1 = new int[]{91,60,96,13,35,65,46,65,10,30,20,31,71,81,22};
        sort(list1);
        System.out.println(Arrays.toString(list1));
    }
    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);//重新对堆进行调整
        }

    }

    /**
     * 在左右子节点都是最大堆的情况下将父节点也构建成最大堆
     * @param arr
     * @param i 父节点
     * @param length
     */
    private static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//k指向子节点中较大的那个
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    private static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
运行结果：
[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 71, 81, 91, 96]

3.2.5 复杂度分析

建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为$O(log_2 n)$;
堆排序的过程由n次第2步完成, 时间复杂度为$O(nlog_2 n)$.

平均时间复杂度	最好情况	最坏情况	空间复杂度
$O(nlog_2 n)$	$O(nlog_2 n)$	$O(nlog_2 n)$	O(1)

3.2.6 总结与思考

由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。

4. 交换排序

4.1 冒泡排序

4.1.2 基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

4.1.3 算法描述

冒泡排序算法的运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动态图：
此处输入图片的描述

4.1.4 算法实现

public class Main {
    public static void main(String[] args) {
        int[] list1 = new int[]{91,60,96,13,35,65,46,65,10,30,20,31,71,81,22};
        sort(list1);
        System.out.println(Arrays.toString(list1));
    }
    private static void sort(int []arr){

        for(int i =0;i<arr.length; i++){
            for (int j = 0;j<arr.length-i-1; j++){
                if(arr[j]>arr [j+1]){
                    int temp = arr [j+1];
                    arr[j+1]=arr [j];
                    arr [j]=temp;
                }
            }
        }
    }
}

4.1.5 复杂度分析

以下是冒泡排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(n²)	O(n)	O(n²)	O(1)

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

4.1.6 总结与思考

由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。

4.2 快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

4.2.1 基本思想

快速排序的基本思想：挖坑填数+分治法。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

4.2.2 算法描述

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

从数列中挑出一个元素，称为”基准”（pivot）。
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
此处输入图片的描述

4.2.3 代码实现

用伪代码描述如下：

i = L; j = R; 将基准数挖出形成第一个坑a[i]。
j–，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
再重复执行2，3二步，直到i==j，将基准数填入a[i]中

public class Main {
    public static void main(String[] args) {
        int[] list1 = new int[]{91,60,96,13,35,65,46,65,10,30,20,31,71,81,22};
        sort(list1,0,list1.length-1);
        System.out.println(Arrays.toString(list1));
    }
    public static void sort(int[] a, int low, int high) {
        //已经排完
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;
        //保存基准值
        int pivot = a[left];
        while (left < right) {
            //从后向前找到比基准小的元素
            while (left < right && a[right] >= pivot)
                right--;
            //将小于pivot的值放在左边，此时a[left]是坑位
            a[left] = a[right];
            //从前往后找到比基准大的元素
            while (left < right && a[left] <= pivot)
                left++;
            //将大于pivot的值放在左边，此时a[right]是坑位
            a[right] = a[left];
        }
        // 放置基准值，准备分治递归快排
        a[left] = pivot;
        sort(a, low, left - 1);
        sort(a, left + 1, high);
    }
}

4.2.4 复杂度分析

以下是快速排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(nlog₂n)	O(nlog₂n)	O(n²)	O(1)（原地分区递归版）

5. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

5.1 基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

5.2 算法描述

归并排序可通过两种方式实现:
自上而下的递归
自下而上的迭代

递归法（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
重复步骤2，直到所有元素排序完毕。

迭代法

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

此处输入图片的描述

5.3 代码实现

归并排序其实要做两件事：

分解：将序列每次折半拆分
合并：将划分后的序列段两两排序合并
因此，归并排序实际上就是两个操作，拆分+合并

下面是递归的方法：

public class Main {
    private static int[] aux;
    public static void main(String[] args) {
        int[] list1 = new int[]{91,60,96,13,35,65,46,65,10,30,20,31,71,81,22};
        aux = new int[list1.length];
        sort(list1,0,list1.length-1);
        System.out.println(Arrays.toString(list1));
    }
    public static void sort(int[] a, int low, int high) {

        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        //将左半边排序
        sort(a, low, mid);
        //将右半边排序
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    
    /**
     * 该方法先将所有元素复制到aux[]中，然后在归并会a[]中。方法咋归并时(第二个for循环)
     * 进行了4个条件判断：
     * - 左半边用尽(取右半边的元素)
     * - 右半边用尽(取左半边的元素)
     * - 右半边的当前元素小于左半边的当前元素(取右半边的元素)
     * - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
     * @param a
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] a, int low, int mid, int high) {
        int i=low;
        int j=mid+1;
        for(int m=low;m<=high; m++) {
            if (i > mid) {
                aux[m] = a[j++];
            } else if (j > high) {
                aux[m] = a[i++];
            } else if (a[i] > a[j]) {
                aux[m] = a[j++];
            } else {
                aux[m] = a[i++];
            }
        }
        for (int m = low; m <= high; m++) {
            a[m]= aux[m];
        }
    }
}

5.4 复杂度分析

以下是归并排序算法复杂度:

平均时间复杂度	最好情况	最坏情况	空间复杂度
$O(nlog_2 n)$	$O(nlog_2 n)$	$O(nlog_2 n)$	O(n)

从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn，, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)，故其综合时间复杂度为O(nlogn)。另一方面，归并排序多次递归过程中拆分的子数组需要保存在内存空间，其空间复杂度为O(n)。

5.5 总结与思考

归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比，它的主要缺点则是他所需的额外空间和N成正比。

6. 基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

6.1 基本思想

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

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital）从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,
再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

此处输入图片的描述

6.2 算法描述

我们以LSD为例，从最低位开始，具体算法描述如下：

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

6.3 代码实现

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束

public class Main {
    private static int[] aux;
    public static void main(String[] args) {
        int[] list1 = new int[]{91,60,96,13,35,65,46,65,10,30,20,31,71,81,22};
        aux = new int[list1.length];
        sort(list1);
        System.out.println(Arrays.toString(list1));
    }
    public static void sort(int[] arr) {
        if (arr.length <= 1) return;

        //取得数组中的最大数，并取得位数
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int maxDigit = 1;
        while (max / 10 > 0) {
            maxDigit++;
            max = max / 10;
        }
        //申请一个桶空间
        int[][] buckets = new int[10][arr.length];
        int base = 10;

        //从低位到高位，对每一位遍历，将所有元素分配到桶中
        for (int i = 0; i < maxDigit; i++) {
            int[] bktLen = new int[10];        //存储各个桶中存储元素的数量

            //分配：将所有元素分配到桶中
            for (int j = 0; j < arr.length; j++) {
                int whichBucket = (arr[j] % base) / (base / 10);
                buckets[whichBucket][bktLen[whichBucket]] = arr[j];
                bktLen[whichBucket]++;
            }

            //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
            int k = 0;
            for (int b = 0; b < buckets.length; b++) {
                for (int p = 0; p < bktLen[b]; p++) {
                    arr[k++] = buckets[b][p];
                }
            }
            System.out.println("Sorting: " + Arrays.toString(arr));
            base *= 10;
        }
    }
}

6.4 复杂度分析

以下是基数排序算法复杂度，其中k为最大数的位数：

平均时间复杂度	最好情况	最坏情况	空间复杂度
O(d*(n+r))	O(d*(n+r))	O(d*(n+r))	O(n+r)

其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。

6.5 总结和思考

基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序。
基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。