经典排序算法

排序算法概述

算法分类

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序；
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

以下是常用的十一种排序算法：

算法时间复杂度

排序算法实现

公共代码实现

// 交换两个元素值
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
// 得到最大值
private int getMaxValue (int[] nums) {
    int maxValue = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (maxValue < nums[i]) {
            maxValue = nums[i];
        }
    }
    return maxValue;
}

// 得到最小值
private int getMinValue (int[] nums) {
    int minValue = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (minValue > nums[i]) {
           minValue = nums[i];
        }
    }
    return minValue;
}

冒泡排序（Bubble Sort）

概述
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"数列的顶端。
算法思路
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对；
3. 针对所有的元素重复以上的步骤，最后已排序好的元素不需要再次比较；
4. 重复步骤1~3，直到排序完成。

代码实现

public void bubbleSort (int[] nums) {
    int len = nums.length;
    // 当最外层循环遍历完毕, 则代表着数组有序
    for(int i = 0; i < len; i++) {
        // 从头开始依次两两比较, 比较结束条件为len - i - 1
        for(int j = 0; j < len - i - 1; j++) {
            // 比较相邻的两个元素, 若前者大于后者, 则进行交换
            if (nums[j] > nums[j + 1]){
                swap(nums, j + 1, j);
            }
        }
    }
}

快速排序（Quick Sort）

概述
快速排序的基本思想是：通过一趟排序以基准元素为基础将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序（分别进行划分），整个排序过程可以递归进行，使整个数据变成有序序列。
算法思路
1. 数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置，该位置称为 K ；
3. 根据第2步得到的基准元素位置 K，递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列进行1~2步的分区操作。

代码实现

public void sort (int[] nums) {
    int len = nums.length;
    quickSort(nums, 0, len - 1);
}

private void quickSort(int[] nums, int left, int right) {
    // 1. 递归结束条件 - left >= right时
    if (left < right) {
        // 2. 递进操作
        // 递归排序分区, 返回基准元素所在位置
        int partitionIndex = partition(nums, left, right);
        quickSort(nums, left, partitionIndex - 1);
        quickSort(nums, partitionIndex + 1, right);
    }
    // 3.递归返回值 - 暂无
}

private int partition(int[] nums, int left, int right) {
    // 选择最左边的数为基准元素
    int pivot = left;
    // 以基准元素为比较元素开始分区操作
    int index = pivot + 1;
    // 从 左->右开始扫描, 若基准元素值nums[pivot] > nums[i], 则进行 
    index 与 i 交换, 否则不进行交换, 保持不变   
    for(int i = index; i <= right; i++) {
        if (nums[i] < nums[pivot]) {
            swap(nums, i, index);
            index++;
        }
    }
    // 将基准元素放在正确的位置, 并返回基准元素的位置
    swap(nums, pivot, index - 1);
    return index - 1;
}

排序优化
快速排序的运行时间与划分是否对称有关。最坏情况下，每次划分过程产生两个区域分别包含n-1个元素和1个元素，其时间复杂度会达到O(n^2)。在最好的情况下，每次划分所取的基准都恰好是中值，即每次划分都产生两个大小为n/2的区域。此时，快排的时间复杂度为O(nlogn)。所以基准的选择对快排而言至关重要。
如果数组元素已经基本有序时，此时的划分就容易产生最坏的情况，即快速排序变成冒泡排序，时间复杂度为O(n^2)。
为了解决上述问题，可以采用随机基准的方式来应对上述特殊情况。

private int partition(int[] nums, int left, int right) {
     
    // 将随机选择一个元素作为基准元素
    // Math.Random()函数能够返回带正号的double值, 该值大于等于0.0且小于1.0
    int randomIndex = (int)(Math.random() * (right - left + 1) + left);
    // 将随机索引处的元素与left处进行交换
    swap(nums, left, randomIndex);

    // 1. 定义变量index，其[pivot + 1,index)范围内的元素小于基准元素
    int index = left + 1;

    // 从 左->右开始扫描, 若基准元素值nums[pivot] > nums[i], 则进行
    // index 与 i 交换, 否则不进行交换, 保持不变   
    // 2. 定义变量i，其[index, i - 1]范围内的元素大于基准元素
    for(int i = index; i <= right; i++) {
        // 3. 触发index变量转移条件，保证循环不变量定义正确
        if (nums[i] < nums[left]) {
            swap(nums, i, index);
            index++;
        }
    }
    // 将基准元素放在正确的位置, 并返回基准元素的位置
    swap(nums, left, index - 1);
    // 4. 返回结果
    return index - 1;
}

二路快速排序（Quick Sort 2 Ways）

概述
二路快速排序的时间和空间复杂度同随机化快速排序。但是对于有大量重复元素的数组，如果使用随机化快速排序效率是非常低的，导致 partition 后大于基点或者小于基点数据的子数组长度会极度不平衡，甚至会退化成 O(n^2)时间复杂度的算法，对这种情况可以使用双路快速排序算法。
算法思路
双路快速排序算法是随机化快速排序的改进版本，partition 过程使用两个索引值（i、j）用来遍历数组，将 <= V 的元素放在索引i所指向位置的左边，而将 >= V的元素放在索引 j 所指向位置的右边，V 代表标定值，平衡左右两边子数组。

代码实现

public void quickSort2ways (int[] nums, int left, int right) {
    // 1. 递归结束条件
    if (left > right)
        return;

    // 2. 递进操作
    int index = partition2(nums, left, right);
    quickSort3Ways(nums, left, index - 1);
    quickSort3Ways(nums, index + 1, right);

    // 3. 递归返回值 - 暂无
}

public int partition2(int[] nums, int left, int right) {
    // 随机选择一个基准
    int randomIndex = (int) (Math.random() * (right - left + 1) + left);
    // 交换left和randomIndex的位置
    swap(nums, left, randomIndex);
    int v = nums[left];

    // 1. 定义变量i, 其在[left + 1, i)范围中的元素 <= v
    //    定义变量j, 其在(j, right] 范围中的元素 >= v
    int i = left + 1, j = right;
    while (true) {

        // 3. 触发循环不变量i改变条件
        while (i <= right && nums[i] < v) {
            i++;
        }

        // 3. 触发循环不变量j改变条件
        while (j >= left + 1 && nums[j] > v) {
            j--;
        }

        // 2. 循坏退出条件
        if (i > j)
            break;

        // 交换 i, j索引处元素
        // 此时若 nums[i] == nums[j] == v, 也会进行交换
        swap(nums, i, j);
        i++;
        j--;
    }
    // 将基准元素放置到正确位置上
    swap(nums, left, j);

    return j;
}

三路快速排序（Quick Sort 3 Ways）

概述
三路快速排序时间和空间复杂度同随机化快速排序。三路快速排序算法是使用三路划分策略对数组进行划分，对处理大量重复元素的数组非常有效提高快速排序的过程。它增加了处理等于基准元素值的逻辑，将所有等于基准元素的值集中在一起。
算法思路
三路快速排序是双路快速排序的进一步改进版本，三路排序算法把排序的数据分为三部分，分别为小于 v，等于 v，大于 v，v 为标定值，这样三部分的数据中，等于 v 的数据在下次递归中不再需要排序，小于 v 和大于 v 的数据也不会出现某一个特别多的情况，通过此方式三路快速排序算法的性能更优。

代码实现

public static void quickSort3Ways(int[] nums, int left, int right) {
    // 1. 递归结束条件 left >= right
    if (left < right) {
        // 随机选择一个基准
        int randomIndex = (int)(Math.random() * (right - left + 1) + left);
        swap(nums, left, randomIndex);
        int curr = nums[left];

        // 1. 定义lt为[left + 1, lt]中的元素小于curr
        int lt = left;
        // 1. 定义gt为[gt, r]中的元素大于curr
        int gt = right + 1;
        // 1. 定义[lt + 1, i) 中的元素等于curr
        int i = left + 1;

        // 2. 递归结束条件, i碰到了gt边界
        while (i < gt) {
            if (nums[i] < curr) {
                lt++;
                // 3. 触发变量
                swap(nums, lt, i);
                i++;
            } else if (nums[i] > curr) {
                gt--;
                swap(nums, i, gt);
            } else {
                i++;
            }
        }

        // 将基准元素放置在正确位置上
        swap(nums, left, lt);

        // 对[left, lt - 1] 进行处理
        quickSort3Ways(nums, left, lt - 1);
        // 对[gt, right] 进行处理
        quickSort3Ways(nums, gt, right);

        // 4. 返回结果 - 暂无
    }
}

插入排序（Insertion Sort）

概述
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法思路
1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出有序序列的下一个元素，作为待插入的新元素，在已经排序的元素序列中从后向前扫描；
3. 如果有序序列中的元素大于新元素，则从后向前继续比较有序序列中的元素；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

代码实现

public void insertSort(int[] nums) {
    int len = nums.length;
    // 从下标为1的元素开始选择合适的位置插入, 因为下标0默认是有序的
    for(int i = 1; i < len; i++) {
        // 需要插入的新元素
        int curr = nums[i];
        // 从已经排序的序列的最右->左开始比较
        int j = i;
        while (j > 0 && nums[j - 1] > curr) {
            // 进行数组的移动
            nums[j] = nums[j - 1];
            j--;
    }

    // 找到了插入位置
    if(j != i)
        nums[j] = curr;
    }
}

希尔排序（Shell Sort）

概述
希尔排序是简单插入排序的改进版，是基于插入排序的以下两点性质而提出的一种排序方法：
1. 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 —> 希尔排序会优先比较距离较远的元素，从而达到更远的移动距离；
2. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 —> 希尔排序在整个序列"基本有序"的时候，直接采用插入排序来进行一次比较。
  希尔排序又叫缩小增量排序。
算法思路
1. 选择一个增量序列t1，t2，…，ti，tj，….tk，其中ti>tj，tk=1，增量序列在排序的过程中不断递减；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为 m 的子序列，分别对各个子序列进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现

public void shellSort(int[] nums) {
    int len = nums.length;
    int gap = 1;
    
    // 选择合适的初始值, 如果直接用len/3的话, 后面可能无法递减为1
    while (gap < len / 3)
        gap = gap * 3 + 1;  // 1, 4, 13, 40, 121....  // Tk, Tk-1,.....,T1
    
    // 对序列进行k趟排序
    while (gap >= 1) {
        // 从下标为gap的元素(从后往前)开始选择合适的位置插入, 因为子序列的第一个元素默认是有序的
        for(int i = gap; i < len; i++) {
            int cur = nums[i];
            int j = i - gap;
            while (j >= 0 && nums[j] > cur) {
                nums[j + gap] = nums[j];
                j -= gap;
            }
            // 将新元素放置到正确位置, j + gap是因为while循环中最后进行了一次j = j - gap
            nums[j + gap] = cur;
        }
        // 缩小增量
        gap = gap / 3;
    }
}

选择排序（Shell Sort）

概述
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法思路
1. 初始未排序区域为nums[0…nums.length - 1]
2. 从未排序区域找到元素值最小的元素，将它和数组中第一个元素交换位置；未排序区域更新为nums[1…nums.length - 1]，从该区域找到第二个元素值最小的元素，将它和数组中第二个元素交换位置，如此反复，直到整个数组排序完成。

代码实现

public void selectionSort(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        // 将nums[i] 与 nums[i+1..len - 1]中最小的元素交换
        int min = i;
        // 从无序区域找到一个最小的元素
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums, i, min);
    }
}

堆排序（Heap Sort）

概述
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法思路
1. 初始化堆：堆将待排序序列构造成一个大顶堆/小顶堆（升序 - 大顶堆，降序 - 小顶堆），此时，整个序列的最大值就是堆顶的根节点；
2. 将根节点与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n 个元素的次大值；
3. 如此反复执行，便能得到一个有序序列。

代码实现

// 堆排序算法
public void heapSort(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);
    }
}

// 调整堆
public void adjustHeap(int[]arr,int i,int len){
    //取出当前元素
    int curr = arr[i];
    //从当前节点的左节点开始比较
    for(intk=i*2+1;k<len;k=k*2+1){
        //若右节点存在且大于左节点,则切换到左节点进行操作
        if(k+1<len&&arr[k]<arr[k+1]){
            k=k+1;
        }
        //如果子节点的值大于父节点
        if(arr[k]>curr){
            //交换元素值
            arr[i]=arr[k];
            //以孩子节点作为父节点继续进行调整
            i=k;
        }
    }
    arr[i]=curr;
}

归并排序（Merge Sort）

概述
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
1. 自上而下的递归；
2. 自下而上的迭代。
算法思路
1. 递归法
  在每一层递归上分为三个步骤：
  a. 分解（Divide）：将n个元素分为 n / 2 个元素的子序列，然后一直递归分解，直到只剩一个元素；
  b. 解决（Conquer）：用合并排序法对两个子序列进行排序；
  c. 合并（Combine）：合并两个已排序的子序列得到当前递归层的排序结果。
2. 迭代法
  先归并那些微型的数组，然后再成对归并得到的子数组，如此这般，直到将整个数组归并完成。
  a. 先进行两两归并（归并子数组长度为1），得到一个"部分有序"（两两相邻有序）的数组；
  b. 然后对第一步得到的数组进行四四归并（将两个大小为2的数组归并为一个有四个元素的子数组），又得到一个相比于第一步更加有序的数组；
  c. 然后是八八归并，一直归并下去，直到整个数组有序；
  d. 注意对最后一个子数组的处理，其长度可能小于归并的默认长度。

代码实现

公共代码实现

//将nums数组进行归并, 将nums[start..end]和data[mid+1, end]归并成一个更大的有序数组, 其中nums[start..mid],
// nums[mid+1,end]已有序
private void mergeResult(int[] nums, int start, int mid, int end) {
    int i = start, j = mid + 1, len = nums.length;
    
    // 归并所需要的辅助数组
    int[] temp = new int[len];

    // 辅助数组
    for (int k = start; k <= end; k++) {
        temp[k] = nums[k];
    }

    // 在temp数组上进行大小比较, 然后temp中的值放回到nums中,返回过程中进行排序
    // 比较方法 - nums[start..mid]和data[mid+1, end]依次开始比较
    for (int k = start; k <= end; k++) {
        // nums[start..mid]的数据排序完成
        if (i > mid) {
            nums[k] = temp[j++];
        // nums[mid + 1..end]的数据排序完成
        } else if (j > end) {
            nums[k] = temp[i++];
        } else if (temp[i] < temp[j]) {
            nums[k] = temp[i++];
        } else{
            nums[k]= temp[j++];
        }
    }
}

递归法代码实现

public void mergeSort(int[] nums) {
    merge(nums, 0, nums.length - 1);
}

private void merge (int[] nums, int start, int end) {
    // 1. 递归结束条件 -只有一个元素
    if (start == end)
        return;

    // 2. 递进操作
    int mid = (start + end) / 2;
    // 对左边进行排序
    merge(nums, start, mid);
    // 对右边进行排序
    merge(nums, mid + 1, end);
    // 对上述排序结果进行合并
    mergeResult(nums, start, mid, end);
}

迭代法代码实现

public void mergeSort(int[] nums) {
    int len = nums.length;
    // sz表示子数组的长度
    for (int sz = 1; sz < len; sz = sz + sz) {
        // 以sz为基准, 把nums分为若干个长度为2sz的子数组, 对其进行归并排序                                  
        //  若下一个子数组的起始位置大于等于len-sz则表示剩余的元素小于sz个，则不需要再进行合并排序了（上一个归并已经处理了）
        for (int lo = 0; lo < len - sz; lo += sz + sz) {
            // 后面的Math.min(lo + sz + sz - 1, len - 1) 是为了保证对未能组成两个归并数组的处理
            mergeResult(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, len - 1));
        }
    }
}

多路归并排序（Merge Sort）

插入排序、选择排序、归并排序等等，这些算法都属于内部排序算法，即排序的整个过程只是在内存中完成。而当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助于外部存储器（例如硬盘、U盘、光盘），这时就需要外部排序算法来解决。
外部排序算法由两个阶段构成：

按照内存大小，将大文件分成若干长度为 L 的子文件（L 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为"归并段"或者"顺段"），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；
对得到的顺段进行合并，直至得到整个有序的文件为止。

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。
想要达到减少访问外存的次数（归并次数）从而提高算法效率的目的，可以从两个角度实现：

增加 k-路平衡归并中的 k 值 — 多路归并算法；
尽量减少初始归并段的数量 m，即增加每个归并段的容量 — 置换-选择排序算法；

计数排序（Counting Sort）

概述
在于将输入的数据值转化为键（数组索引）存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。
额外开辟的数组空间的长度为输入数组的最大值+1，这也意味着计数排序对于数据范围很大的输入数据，它需要很大的空间来用来进行计数，所以计数排序是一种典型的空间换时间的算法。
算法思路
1. 找出待排序数组的最大值，开辟一个额外数组，其长度为最大值+1；
2. 遍历待排序数组，计算数组中每个元素的出现次数，并且将元素值作为索引，出现的次数作为值存入到额外数组中；
3. 遍历额外数组，若其元素值（出现次数）大于0，则将其索引作为元素值回写到待排序数组中，并且出现次数-1，直到完成排序；
如果按照上述的算法（朴素的计数排序）思路来进行排序的话，还存在着如下两个问题：
1. 额外数组在某些情况下利用率低。例如待排序数组范围 90 ~ 99，那么额外数组的长度为99+1，这造成前0~89个数组空间的浪费。
  要解决这个问题，可以使用（maxValue - minValue）+ 1作为额外数组的长度，以minValue作为偏移量，nums[i] - minValue来定位nums[i] 在额外数组中的位置；
2. 朴素的计数排序不是稳定的排序，它只是简单遍历的额外数组，然后对于值不为0的元素输出其下标，若待排序数组有nums[i] == nums[j]（i < j），排序之后，nums[i] == nums[j]（i > j）。若是单纯的进行整数排序，排序之后交换了位置也没关系，但是如果面临现实业务（比如考试分数的排序）中，就行不通了。
  要解决这个问题，需要对额外数组进一步操作，依次将当前位置的值和前一个位置的值相加（代码描述为：countNums[i] += countNums[i - 1]），这样额外数组中存储的值代表了元素的最终排序位置。
  
  输入待排序数组为[4,0,9,5,5]，经过计数之后得到上述图片的上半部分，进行处理后得到下半部分，那么下标为9的的值为5，则代表中元素9最终排序的位置为5。

代码实现

public void countingSort (int[] nums) {
    // 得到最大值
    int maxValue = getMaxValue(nums);
    // 开辟额外数组
    int[] countNums = new int[maxValue + 1];

    // 计算数组中每个元素出现的次数, 并且将元素值作为索引, 出现次数作为值存到countNums中
    for (int value : nums) {
        countNums[value]++;
    }

    // 遍历额外数组countNums, 将其索引回写到nums数组中
    int sortIndex = 0;
    for (int i = 0; i < countNums.length; i++) {
        while (countNums[i] > 0) {
            nums[sortIndex++] = i;
            countNums[i]--;
        }
    }
}

优化之后的代码如下:

public void countingSort (int[] nums) {
    // 得到最大值
    int maxValue = getMaxValue(nums);
    // 得到最小值
    int minValue = getMinValue(nums);
    // 开辟额外数组
    int[] countNums = new int[(maxValue - minValue) + 1];
    // 计算数组中每个元素出现的次数, 并且将元素值 - 偏移量(minValue)作为索引, 出现次数作为值存到countNums中
    for (int value : nums) {
        countNums[value - minValue]++;
    }
    // 对额外数组进行处理
    for (int i = 1; i < countNums.length; i++) {
        countNums[i] += countNums[i - 1];
    }
    // 倒序遍历(才能保证稳定)待排序数组, 从额外数组countNums中找到每个元素属于自己的排序位置
    // 开辟一个数组来保存排序结果, 如果原地进行的话会覆盖还未排序的元素
    int[] sortArray = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        // countNums[nums[i] - minValue]为 nums[i]的最终位置
        sortArray[countNums[nums[i] - minValue] - 1] = nums[i];
        countNums[nums[i] - minValue]--;
    }
    nums = sortArray.clone();
}

桶排序（Bucket Sort）

概述
桶排序是计数排序的升级版，降低了额外空间的大小和提高了额外空间的利用率。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定，对于桶的内部，选择何种内部排序算法也对性能有着重要的影响。为了使桶排序更加高效，需要做到这两点：
1. 在额外空间充足的情况下，尽量增大桶的数量；
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。
算法思路
1. 根据待排序数组中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数
  ，设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 选择一种排序算法，对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

代码实现

public void bucketSort (int[] nums) {
    bucketSort(nums, 5);
}

private void bucketSort(int[] nums, int bucketSize) {
    // 根据最大值和最小值计算需要的桶的个数 - 映射规则(可以选择不同的映射规则)
    int minValue = nums[0];
    int maxValue = nums[0];
    for (int value : nums) {
        if (value > maxValue) {
            maxValue = value;
        } else if (value < minValue) {
            minValue = value;
        }
    }

    // 得到所需桶个数
    int bucketCount = (int) (Math.floor((maxValue - minValue) / bucketSize) + 1);
    // 创建桶
    int[][] buckets = new int[bucketCount][0];

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

    int index = 0;
    for (int[] bucket : buckets) {
        if (bucket.length < 0) {
            continue;
        }
        // 对每个桶中元素进行排序 - 采用插入排序, 可使用其他排序算法
        bucket = insertSort(bucket);
        // 将已经排序完的元素回写到数组中
        for (int value : bucket) {
            nums[index++] = value;
        }
    }
}


// 将数据添加到桶中
private int[] numsAppend (int[] bucketNums, int value) {
    bucketNums = Arrays.copyOf(bucketNums, bucketNums.length + 1);
    bucketNums[bucketNums.length - 1] = value;
    return bucketNums;
}

基数排序（Radix Sort）

概述
基数排序是一种非比较型整数排序算法，其原理是将整数按位数（通常是低位->高位进行分割）切割成不同的数字，然后将分割之后的数字分配到不同桶中，对桶中元素进行排序，然后依次输出桶中元素，接着按照下一个位数进行分割，反复进行上述操作，直到整个数组有序。
若待排序数组分割之后的位数的数值范围较小，可以不利用桶来收集分割之后的元素，可以直接采用计数排序。比如对于整数的基数排序，只需要分配固定十个桶（位数范围0~9），则直接可以基于计数排序进行。
基数排序既可以从高位优先进行排序（Most Significant Digit first，简称MSD），也可以从低位优先进行排序（Least Significant Digit first，简称LSD）。
算法思路
1. 得到待排序数据中的最大值，并得到最大值的位数digit；
2. 从低位到高位依次待排序数组进行计数排序，计数排序的次数为digit；
3. 重复第二步，直到整个数组有序。

代码实现

public void radixSort (int[] nums) {
    // 得到最大值的长度(位数), 通过这个就知道需要进行几次基数排序
    int maxDigit = getMaxDigit(nums);
    sort(nums, maxDigit);
}

private void sort (int[] nums, int maxDigit) {
    int exp = 1;
    // 最大值的位数为maxDigit, 则代表要进行maxDigit次计数排序
    for (int i = 0; i < maxDigit; i++, exp *= 10) {
        countingSort(nums, exp);
    }
}

// 对基数排序的每位进行计数排序
private static void countingSort (int[] nums, int exp) {
    // 开辟额外数组存在每个数字出现次数
    int[] countNums = new int[10];
    for (int value : nums) {
        countNums[(value / exp) % 10]++;
    }

    // 对额外数组进行处理
    for (int i = 1; i < countNums.length; i++) {
        countNums[i] += countNums[i - 1];
    }

    // 倒序遍历(才能保证稳定)待排序数组, 从额外数组countNums中找到每个元素属于自己的排序位置
    // 开辟一个数组来保存排序结果, 如果原地进行的话会覆盖还未排序的元素
    int[] sortArray = new int[nums.length];
    for (int i = nums.length - 1; i >= 0; i--) {
        sortArray[countNums[(nums[i] / exp) % 10] - 1] = nums[i];
        countNums[(nums[i] / exp) % 10]--;
    }

    // 因为需要基于nums再进行若干次计数排序, 所以将sortArray 赋值给nums
    for (int i = 0; i < sortArray.length; i++) {
        nums[i] = sortArray[i];
    }
}

// 得到最大值的位数
private static int getMaxDigit (int[] nums) {
    int maxValue = nums[0];
    for (int value : nums) {
        if (maxValue < value)
        maxValue = value;
    }
    // 得到最大值的位数
    int length = 0;
    while (maxValue != 0) {
        length++;
        maxValue = maxValue / 10;
    }
    return length
}

参考资料

[1] https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653200371&idx=1&sn=94c1882b9156bd96fa6da20c7995850e&chksm=8c99ed29bbee643f292c3d06995825a657d0c93cbabc4cc41a1a4f4073fdb663ecdc6d1d9685&scene=21#wechat_redirect
[2] https://www.cnblogs.com/onepixel/articles/7674659.html
[3] https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195533&idx=1&sn=02918dc51b07837ce1119f00d7900dbc&chksm=8c99ffd7bbee76c1d2e2e9b198259795285ec2c305d3613a5e39622195fd1c32bb6dbe52fa08&scene=21#wechat_redirect

排序算法概述

算法分类

算法时间复杂度

相关概念

排序算法实现

公共代码实现

冒泡排序（Bubble Sort）

快速排序（Quick Sort）

二路快速排序（Quick Sort 2 Ways）

三路快速排序（Quick Sort 3 Ways）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

选择排序（Shell Sort）

堆排序（Heap Sort）

归并排序（Merge Sort）

多路归并排序（Merge Sort）

计数排序（Counting Sort）

桶排序（Bucket Sort）

基数排序（Radix Sort）

参考资料