数据结构与算法 - 基础：排序

排序

排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。

排序的主要目的就是实现快速查找。

排序分类

增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。
稳定排序和不稳定排序：具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之是不稳定的。
内部排序和外部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之成为外部排序。

本文目录

1、冒泡排序；

一、冒泡排序（Bubble Sort）

1.1 思想

冒泡排序(bubble sort)：每个回合都从第一个元素开始和它后面的元素比较，如果比它后面的元素更大的话就交换，一直重复，直到这个元素到了它能到达的位置。每次遍历都将剩下的元素中最大的那个放到了序列的“最后”(除去了前面已经排好的那些元素)。注意检测是否已经完成了排序，如果已完成就可以退出了。

1.2 算法步骤

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

1.3 动画演示

1.4 代码实现

public class Demo{
    public static void BubbleSort(int[] arr){
        int temp = 0;
        for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
            for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }//loop j
        }//loop i
    }// method bubbleSort
    public static void main(String[] args){
        int[] arr = {10,30,20,60,40,50};
        Demo.BubbleSort(arr);
        for(int i:arr){
            System.out.print(i+",");
        }
    }
}

1.5 时空复杂度

冒泡排序的关键字比较次数与数据元素的初始状态无关。第一趟的比较次数为n-1，第i趟的比较次数为n-i，第n-1趟（最后一趟）的比较次数为1，因此冒泡排序总的比较次数为n(n−1)/2

冒泡排序的数据元素移动次数与序列的初始状态有关。

在最好的情况下，移动次数为0次；

在最坏的情况下，移动次数为n(n−1)/2

冒泡排序的时间复杂度为O(n2)。冒泡排序不需要辅助存储单元，其空间复杂度为O(1)。如果关键字相等，则冒泡排序不交换数据元素，他是一种稳定的排序方法。

时间复杂度：最好O(n)；最坏O(n2)；平均O(n2)
空间复杂度：O(1)
稳定性：稳定

二、选择排序（Selection Sort）

2.1 思想

每个回合选择出剩下的元素中最小(大)的，选择的方法是默认第一个元素是最小的，如果后面的元素比它小，则与它交换。第二回则默认第二个元素是最小的，同理，重复以上操作即可；这个过程相当于把数据分为两段，一段是有序的，一段是未排序的，选择排序即是在未排序的数据中选择元素插入到有序数据中。

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

2.2 算法步骤

1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
3、重复第二步，直到所有元素均排序完毕；

2.3 动画演示

2.4 代码实现

public class Demo{
    public static void selectionSort(int[] arr) {
        int temp, min = 0;
        for (int index = 0; index < arr.length - 1; ++index) {
            min = index;
            // 循环查找最小值
            for (int j = index + 1; j < arr.length; ++j) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != index) {
                temp = arr[index];
                arr[index] = arr[min];
                arr[min] = temp;
            }
        }
    }
    public static void main(String[] args){
        int[] arr = {10,30,20,60,40,50};
        Demo.selectionSort(arr);
        for(int i:arr){
            System.out.print(i+",");
        }
    }
}

2.3 时空复杂度

对具有n个数据元素的序列进行排序时，选择排序需要进行n-1趟选择。进行第 i 趟选择时，前面已经有 i-1个数据

元素排好序，第i趟从剩下的n−i+1个数据元素中选择一个关键字最小的数据元素，并将它与第i个数据元素交换，这样即可使前面的 i 个数据元素排好序。

选择排序的关键字比较次数与序列的初始状态无关。

对n个数据元素进行排序时，第一趟的比较次数为n−1，第i趟的比较次数是n−i次，第n−1趟（最后一趟）的比较次数是1次。因此，总的比较次数为n(n−1)/2

选择排序每一趟都可能移动一次数据元素，其总的移动次数与序列的初始状态有关。当序列已经排好序时，元素的移动次数为0。当每一趟都需要移动数据元素时，总的移动次数为n−1

选择排序的时间复杂度为O(n2)。选择排序不需要辅助的存储单元，其空间复杂度为O(1)。选择排序在排序过程中需要在不相邻的数据元素之间进行交换，它是一种不稳定的排序方法。

时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：不稳定

三、插入排序（Insertion Sort）

3.1 思想

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这种是直接插入排序，它有一种优化算法，结合二分查找，这种叫折半插入。

3.2 算法步骤

1、将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；
2、从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）；

3.3 动图演示

3.4 代码实现

public class SortTest {
    
    public static void insertSort(int[] arr){
        if(arr == null | arr.length ==0) return;
        
        for(int i=0; i<arr.length; i++){
            int t = arr[i];  //t相当无序序列的首元素
            int j = i;  //j相当无序序列的首元素位置
            while(j>0 && t<arr[j-1]){  //j-1相当有序序列的末元素位置
                arr[j] = arr[j-1];
                j--;
            }
            if(j != i)
                arr[j] = t;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,8,6,5,9,4,7,3,2,0};
        insertSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

3.5 时空复杂度

直接插入排序关键字比较次数和数据元素移动次数与数据元素的初始状态有关。

在最好的情况下，待排序的序列是已经排好序的，每一趟插入，只需要比较一次就可以确定待插入的数据元素的位置，需要移动两次数据元素。因此总的关键字比较次数为n−1,总的数据元素移动次数为2(n−1)

在最坏的情况下，待排序的序列是反序的，每一趟中，待插入的数据元素需要与前面已排序序列的每一个数据元素进行比较，移动次数等于比较次数。因此，总的比较次数和移动次数都是n(n−1)/2

直接插入排序的时间复杂度为O(n2)。直接插入排序需要一个单元的辅助存储单元，空间复杂度为O(1)。直接插入排序只在相邻的数据元素之间进行交换，它是一种稳定的排序方法。

最好情况O(n)；最坏情况O(n2)；平均时间复杂度为：O(n2)
空间复杂度：O(1)
稳定性：稳定

四、希尔排序（Shell Sort）

4.1 思想

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

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

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

希尔排序基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。即先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。

4.2 算法步骤

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

举例：[16，25，12，30，47，11，23，36，9，18，31]，共11个元素

第一趟：增量d=5, 我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

16，25，12，30，47
11，23，36， 9，18
31

然后每列排序：

11，23，12，9， 18
16，25，36，30，47
31

所以得到的序列为 [11，23，12，9， 18，16，25，36，30，47，31]

第二趟：增量d=2，同理

11，23，
12， 9， 
18，16，
25，36，
30，47，
31

按列排序并连接起来得：[11, 9, 12, 16, 18, 23, 25, 36, 30, 47, 31]

第三趟：增量d=1，即以1步长进行排序(即是简单的插入排序)

4.3 代码实现

    public static void shellSort(int[] arr){
        if(arr == null | arr.length ==0) return;
        
        int temp;
        for(int delta = arr.length/2; delta>=1; delta/=2){  //对每个增量进行一次排序
            for(int i=delta; i<arr.length; i++){
                for(int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){//注意每个地方增量和差值都是delta
                    swap(arr, j-delta, j);
              //  temp = arr[j-delta];
             //   arr[j-delta] = arr[j];
             //      arr[j] = temp;
                }
            }
        }
    }

4.4 时空复杂度

希尔排序在效率上比直接插入排序有很大的改进，但对希尔排序进行时间性能分析很难，原因是何种步长序列最优难以判定，通常认为其时间复杂度为O(n1.5)。

希尔排序的增量序列可以有多种取法，较优的增量序列的共同特征如下。

最后一个增量必须为。
应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

时间效率：当增量序列为d(k)=2t-k+1-1时，时间复杂度为O(n1.5）。

空间效率： O（1）

算法的稳定性：不稳定

五、归并排序（Merge Sort）

5.1 思想

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；

典型的是二路合并排序，将原始数据集分成两部分(不一定能够均分)，分别对它们进行排序，然后将排序后的子数据集进行合并，这是典型的分治法策略。

5.2 算法步骤

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

5.3 动图演示

5.4 代码实现

public class SortTest {

    public static void mergeSort(int[] arr){
        if(arr == null || arr.length < 2) return;
        mSort(arr, 0, arr.length-1);
    }
    
    private static void mSort(int[] arr, int left, int right){
        //当left==right的时，已经不需要再划分了
        if(left<right){
            int middle = (left+right)/2;  //left + ((right - left) >> 1);
            mSort(arr, left, middle);  //左子数组
            mSort(arr, middle+1, right);  //右子数组
            merge(arr, left, middle, right);  //合并两个子数组
        }
    }
    
    private static void merge(int[] arr, int left, int middle, int right){
        int[] t = new int[right - left + 1];
        int k = 0;
        int i = left;
        int j = middle+1;
        //将记录由小到大地放进temp数组
        while(i<=middle && j<=right){
            if(arr[i] <= arr[j]){
                t[k++] = arr[i++];
            }else{
                t[k++] = arr[j++];
            }
        }
        while(i<=middle){
            t[k++] = arr[i++];
        }
        while(j<=right){
            t[k++] = arr[j++];
        }
                //把数据复制回原数组
        for(i=0;i<k;i++){
            arr[left+i] = t[i];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1,8,6,5,9,4,7,3,2,0};
        mergeSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

5.4 时空复杂度

在归并排序中，进行一趟归并需要的关键字比较次数和数据元素移动次数最多为n，需要归并的趟数log2n，故归并排序的时间复杂度为O(nlog2n)。归并排序需要长度等于序列长度为n的辅助存储单元，故归并排序的空间复杂度为O(n)。归并排序是稳定的排序算法。

时间复杂度：O(nlog2n)
空间复杂度：O(n)
稳定性：稳定

六、快速排序（Quick Sort）

6.1 思想

快速排序是图灵奖得主C.R.A Hoare于1960年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法（Divide-and-Conquer Method）

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题组合为原问题的解。

6.2 算法步骤

利用分治法可将快速排序分为三步：

1、从数列中挑出一个元素作为“基准”（pivot）；
2、分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边这个操作称为“分区操作”，分区操作结束后，基准元素所处的位置就是最终排序后它的位置；
3、再对“基准”左右两边的子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

6.3 动图演示

6.4 代码实现

public class SortTest {
    
    public static void quickSort(int[] arr){
        if(arr == null || arr.length<2){
            return;
        }
        quickSort(arr, 0, arr.length-1);
    }

    private static void quickSort(int[] arr, int l, int r) {
        if(l < r){
            int p = partition(arr, l, r);
            quickSort(arr, l, p-1);
            quickSort(arr, p+1, r);
        }
    }

    private static int partition(int[] arr, int l, int r) {
        //设定基准值(pivot)
        int pivot = arr[l]; //选基准值为首位置的元素
        while (l<r){
            while(l<r && arr[r]>=pivot) r--;
            arr[l] = arr[r]; //交换比基准小的记录到左端
            while(l<r && arr[l]<=pivot) l++;
            arr[r] = arr[l]; //交换比基准大的记录到右端
        }
        //扫描完成，基准到位
        arr[l] = pivot;
        return l;
    }

    public static void main(String[] args) {
        int[] arr = {1,8,6,5,9,4,7,3,2,0};
        quickSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

有一种优化方式：分区时可能中间边界存在大量相同元素，可取其边界再划分；同时选基准时，随机选取，减小偶然性。

public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            //swap(arr, l + (int) (Math.random() * (r - l + 1)), r);  //设为随机快排
            int[] p = partition(arr, l, r);
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {  //相当最右边位置的元素为基准
                swap(arr, ++less, l++);  //l快指针(当前位置指针)，less慢指针
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l); //l指向位置不变
            } else { // == 基准
                l++;
            }
        }
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }

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

    // for test
    public static void main(String[] args) {
        int[] arr = {1,8,6,5,9,4,7,3,2,0};
        quickSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

6.5 时空复杂度

时间复杂度：最好O(nlog2n)；平均O(nlog2n)，最坏：O(n2)
空间复杂度：O(log2n)
稳定性：不稳定

七、堆排序（Heap Sort）

7.1 思想

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1、大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2、小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。

如下图，是一个堆和数组的相互关系：

对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标(源点从1开始)：

Parent(i) = floor(i/2)，i 的父节点下标
Left(i) = 2i，i 的左子节点下标
Right(i) = 2i + 1，i 的右子节点下标

7.2 算法步骤

堆排序中经常用到的两种基本动作为：建堆和筛选

1、创建一个堆H[0……n-1]；
2、把堆首（最大值）和堆尾互换；
3、把堆的尺寸缩小1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4、重复步骤2，直到堆的尺寸为1；

7.3 动图演示

7.4 代码实现

大顶堆排序

public class SortTest {
    
    public static void heapSort(int[] arr){
        if(arr==null || arr.length<2) return;
        // 将待排序的序列构建成一个大顶堆  
        for(int i=arr.length/2; i>=0; i--){
            heapAdjust(arr, i, arr.length);
        }
        // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for(int i=arr.length-1; i>0; i--){
            swap(arr, 0, i);
            heapAdjust(arr, 0, i);
        }
    }
    
    private static void heapAdjust(int[] arr, int i, int n){
        int left = 2*i+1;  //i节点的左孩子节点
        while(left<n){
            int largest = left + 1 < n && arr[left+1]>arr[left] ? left+1 : left; //如果有右节点，比较左右并找出最大节点的位置 
            largest = arr[largest] > arr[i] ? largest : i;  // 父节点i与最大子节点比较，并返回最大节点的位置
            if(largest == i) break; 
            
            swap(arr, largest, i); //有子节点比父节点大的，则交换
            i = largest;  //下沉
            left = 2*i + 1;
        }
    }
    
    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[] arr = {1,8,6,5,59,18};
        heapSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

7.5 时空复杂度

堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。

时间复杂度：O(nlog2n)

假设节点数为n,所以需要进行n - 1次调换，也就是需要n-1次堆调整，每次堆调整的时间复杂度为O(logn) ，那么总的时间复杂度就是(n - 1)O(logn) = O(nlogn)

八、计数排序

8.1 思想

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为 O(n+k)。

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

计数排序只适合元素是整数，小规模的排序。

8.2 算法步骤

1、花O(n)的时间扫描一下整个待排序列，获取最小值min和最大值max；
2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1；

8.3 动图演示

8.4 代码实现

package demo;

public class SortTest {
    
    public static void countingSort(int[] arr){
        if(arr==null || arr.length<2) return;
        int maxValue = getMaxValue(arr);
        countingSort(arr, maxValue);
    }
    
    private static int[] countingSort(int[] arr, int maxValue){
        int bucketLen = maxValue + 1;  //优化方法:长度max-min+1,放入bucket时减min,倒时加回min
        int[] bucket = new int[bucketLen];
        
        for(int value: arr)  //计数
            bucket[value]++;
        
        //倒回原arr
        int sortedIndex = 0;
        for(int j=0; j<bucketLen; j++){
            while(bucket[j]>0){
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }
    
    private static int getMaxValue(int[] arr){
        int maxValue = arr[0];
        for(int value : arr){
            if(maxValue < value)
                maxValue = value;
        }
        return maxValue;
    }

    public static void main(String[] args) {
        int[] arr = {1,8,6,5,59,18,15,3,7,10,2};
        countingSort(arr);
        
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

优化后的实现：

public static int[] countSort1(int[] arr){
    if (arr == null || arr.length == 0) {
        return null;
    }
    
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    
    //找出数组中的最大最小值
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    int help[] = new int[max];
    
    //找出每个数字出现的次数
    for(int i = 0; i < arr.length; i++){
        int mapPos = arr[i] - min;
        help[mapPos]++;
    }
    
    int index = 0;
    for(int i = 0; i < help.length; i++){
        while(help[i]-- > 0){
            arr[index++] = i+min;
        }
    }
    
    return arr;
}

View Code

8.5 时空复杂度

n个0 到 k 之间的整数时，它的运行时间是 O(n + k)

九、桶排序

9.1 思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的N个数据均匀的分配到K个桶中；

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.2 算法步骤

1、假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶；
2、将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序；
3、将各个桶中的数据有序的合并起来；

9.3 示图演示

元素分布在桶中：

然后，元素在每个桶中排序：

Data Structure Visualizations 提供了一个桶排序的分步动画演示。

9.4 代码实现

public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

9.5 时空复杂度

O(n+k)

(1)什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

(2)什么时候最慢

当输入的数据被分配到了同一个桶中。

十、基数排序

10.1 思想

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

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

MSD（Most significant digital）从最左侧高位开始进行排序。
LSD （Least significant digital）从最右侧低位开始进行排序。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；

10.2 算法步骤

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

步骤：

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

通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

[]nbsp_nbsp 15

在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。
1、按照个位数进行排序；
2、按照十位数进行排序；
3、按照百位数进行排序；
排序后，数列就变成了一个有序序列。

10.3 动图演示

10.4 代码实现

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}