一、 选择排序
选择排序的基本思想是每次从待排序子表中挑选出最小的元素放在已经排好序子表的最后位置，直至全部元素排序完毕（默认是升序排序）。
1、简单选择排序
简单选择排序是使用顺序表这种数据结构，运用选择排序的思路的一种排序算法。时间复杂度无论是最好、最坏、平均，均为O（n * n），空间复杂度为O（1），原因是无法利用之前排序的结果，每次只能重新循环遍历，且是一个不稳定的排序算法。例如序列[2,2,1,4],进行第一次排序，1跟第一个2进行交换，更改了两个2之间的前后顺序。
/**
* 简单选择排序
*
* @param nums 待排序序列
*/
public void simpleSelectSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) { //i为当前需要归位元素的索引
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[minIndex] > nums[j]) {
//挑选出最小的元素
minIndex = j;
}
}
//交换元素i和minIndex的元素，使得未排序子表的最小值归位
if (minIndex != i) {
swap(nums, minIndex, i);
}
}
}
/**
* 交换两个元素
* @param nums
* @param x
* @param y
*/
public void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
2、堆排序
堆排序是利用堆这种数据结构进行的一种不稳定的选择排序算法，分为大根堆排序和小根堆排序。
大根堆：父节点大于等于左右两个孩子结点。即2i >=2i +1 && 2i >= 2i+2
小根堆：父节点小于等于左右两个孩子结点。即2i <= 2i +1 && 2i <= 2i+2
对于升序排序，我们用的是大根堆排序，反之降序排序用的是小根堆排序。
对于大根堆排序，首先就是原数组幻想成一棵完全二叉树（除了最后一层之外其他的每一层都被完全填充，并且所有的节点都向左对齐），对于坐标i的元素，左孩子为2i+1,右孩子为2i+2（前提没有超过边界）。
大根堆排序过程：对于数组[4,6,8,5,9]
思路
步骤一、建立大根堆
1、一开始将数组原封不动地插入完全二叉树，则初始完全二叉树为
2、从最后一个非叶子结点开始，进行从左到右、从上到下调整，也是以6为根节点的子树，6 < 孩子结点最大值9，则6与9交换位置，形成一个子大根堆。
3、找到倒数第二个非叶子结点4，4小于孩子结点最大值9，则4与9交换位置，形成整个大根堆。
但因为4下移，破环了原来的子大根堆结构[4,5,6]，因此再对其进行一次调整，4跟6交换，从而形成真正的大根堆
步骤二、交换堆顶元素与堆尾元素，使得数组的最大元素归位（移动到数组倒数第一个位置），重新调整形成新的大根堆，再交换堆顶元素与堆尾元素，使得数组的次大元素归位（移动到数组倒数第二个位置），再重新调整。不断进行这样的交换、调整过程，最后使得整个数组有序。
1、堆顶元素9与堆尾元素4交换，并调整
2、堆顶元素8与堆尾元素5交换，并调整
3、重复进行交换、调整操作，使得全部元素归位
图片来源：https://www.cnblogs.com/chengxiao/p/6129630.html
复杂度分析
对于初始化建堆过程，每次建堆就是从小往下交换，最高层次是logn，因此每次建堆的时间复杂度为O(logn)，n个元素则为O(nlogn)。对于交换调整，每个元素重新建堆的时间复杂度为O(logn)，n个元素则为O(nlogn)。所以整体时间复杂度为O(nlogn)。空间复杂度为O(1)。
代码实现
public void heapSort(int[] nums, int n) {
//循环建立大根堆
for (int i = (nums.length - 1) / 2; i >= 0; i--) { //从最后一个非叶子节点开始建堆
sift(nums, i, n - 1);
}
for (int i = n - 1; i >= 1; i--) {
//交换堆顶元素和堆尾元素，使得当前最大值归位
swap(nums, i, 0);
//对剩下的元素重新调整
sift(nums, 0, i - 1);
}
}
/**
* 从左到右、从上到下对数组进行调整，形成大根堆
*
* @param nums 数组
* @param root 根节点索引
* @param right 数组下界
*/
public void sift(int nums[], int root, int right) {
int i = root, j = 2 * i + 1; //j默认是i的左孩子
while (j <= right) { //判断是否超出边界
//找出当前结点的左右孩子结点最大值
if (j < right && nums[j] < nums[j + 1])
j = j + 1;
//判断是否需要调整父节点
if(nums[i] < nums[j]){
swap(nums, i, j);
//继续往下调整堆
i = j;
j = 2 * i + 1;
}else{
//不需要调整，则已经是大根堆了，退出循环
break;
}
}
}
public void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
二、交换排序
1、冒泡排序
冒泡排序是一种典型的交换排序算法，且是一种稳定的排序算法，基本思想是通过对无序区中从后往前相邻元素的比较，将较小元素放在前面，这样一次过程使得最小元素犹如气泡一样逐渐移动到最前面。
思路
对于序列[2,5,1,4]
第一次冒泡过程：（排序区域为[2,5,1,4]）4比1大，不用交换；1比5小，交换，变成[2,1,5,4]；1比2小，交换，变成[1,2,5,4]，则最小值1移动到最前面。
第二次冒泡过程：（排序区域为[2,5,4]）4比5小，交换，变成[2,4,5]；4比2大，不用交换，则次小值移动到第二个位置。
第三次冒泡过程：（排序区域为[4,5]）5比4小不交换，变成[4,5]，则次次小值移动到第三个位置。
第四次冒泡过程：（排序区域为[5]）只剩一个元素，不需要排序。
代码实现
public static void swap(int[] arr, int x, int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
/**
* 第一种冒泡排序，时间复杂度为O(n * n)，空间复杂度O(1)
* @param array 数组
* @param n 数组长度
*/
public static void bubbleSort(int[] array, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
if (array[j - 1] > array[j])
swap(array, j - 1, j);
}
}
}
无论是最好、最坏、平均复杂度，对应的时间复杂度为O(n * n)，空间复杂度O(1)。
代码优化
假如在一次冒泡过程中，没有进行元素的相邻交换，则当前序列已经有序，不需要进行下一次排序。例如[1,2,3,4]，在第一次冒泡过程中，没有交换，已经形成有序序列，直接退出排序过程。
/**
* 第二种冒泡
* @param array 数组
* @param n 数组长度
*/
public static void bubbleSort2(int[] array, int n) {
boolean exchange = false;
for (int i = 0; i < n - 1; i++) {
exchange = false;//记录当前冒泡过程是否有交换元素
for (int j = n - 1; j > i; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
exchange = true;
}
}
if(!exchange) //没有交换则已经有序，退出
return;
}
}
空间复杂度均为O(1)，在最好情况下，时间复杂度为O(n)，最坏和平均情况下，时间复杂度为O(n*n),
2、快速排序
快速排序是对冒泡排序的改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。是一种不稳定的排序算法。
思路
对于序列[2,4,1,3,5]，
- 选取最左边的元素2作为基准，存入临时变量中，设变量low为左边界0，right为右边界4。
- right先从右往左扫描元素，找出第一个比基准2小的元素1，将它覆盖low位置的元素2。此时low=0,right=2，序列为[1,4,1,3,5]。
- 交换扫描过程，让low从左往右扫描元素，找出第一个比基准2大的元素4，将它覆盖right位置的元素1，此时low=1，right=2，序列为[1,4,4,3,5]。
- 交换扫描过程，让right从右往左扫描元素，找出下一个比基准2小的元素，不停前移，直到low=right，证明已经将序列划分完毕，此时应该将基准放回正确的元素，即nums[left] = tmp。
- 接下来对左右两个区域再进行递归划分，直至子序列长度<=1为止。
代码实现
public static void main(String[] args) {
int[] test = new int[]{1, 6, 2, 4, 3};
quickSort(test)
System.out.println(Arrays.toString(test));
}
/**
* @param nums 待排序的数组
* @param left 左边界
* @param right 有边界
*/
public static void quickSort(int[] nums, int left, int right) {
if (left < right) { //子序列超过1个的时候才需要排序
int middle = partition(nums, left, right);//进行划分，得到基准最后的位置
quickSort(nums, left, middle - 1);//对基准左边的区域进行递归排序
quickSort(nums, middle + 1, right);//对基准右边的区域进行递归排序
}
}
/**
* 划分
*
* @param nums
* @param left
* @param right
* @return
*/
public static int partition(int[] nums, int left, int right) {
//随机挑选一个元素作为基准,索引为left~right
int index = (int) (Math.random() * (right - left + 1)) + left;
//交换第一个元素和随机元素的位置
swap(nums, left, index);
int tmp = nums[left];
while (left < right) {
while (left < right && nums[right] >= tmp)//找出比基准小的元素
right--;
nums[left] = nums[right];
while (left < right && nums[left] <= tmp)//找出比基准大的元素
left++;
nums[right] = nums[left];
}
nums[left] = tmp; //基准归位
return left;
}
代码优化
因为实现一是将小于等于基准的元素放左边、大于等于基准的元素放右边，然后等于基准的元素仍然需要参与下一次的递归排序，实际上应该不需要，因此进行优化，将序列划分三部分，左边部分是小于基准的元素，中间部分是等于基准的元素，右边部分是大于基准的部分，然后对左边和右边部分进行递归排序。
public void quickSort2(int[] nums, int left, int right) {
if (left < right) {
int[] partition = partition2(nums, left, right);
quickSort2(nums, left, partition[0] - 1);
quickSort2(nums, partition[1] + 1, right);
}
}
/**
* 划分
*
* @param nums
* @param left
* @param right
* @return
*/
public int[] partition2(int[] nums, int left, int right) {
//随机挑选一个元素作为基准,索引为left~right
int index = (int)(Math.random() * (right - left + 1)) + left;
//交换第一个元素和随机元素的位置，避免逆序的这种最坏情况发生
swap(nums, right, index);
int tmp = nums[right]; //以最后一个元素作为基准
int i = left - 1, j = right; //i为比基准小的区域有边界，j为比基准大的左边界
for (int k = i + 1; k < j; k++) {
if (nums[k] < tmp) {
i++;//左区域扩大一位
swap(nums, i, k);
} else if (nums[k] > tmp) {
//右区域扩大一位
j--;
swap(nums, k, j);
//扫描位不动，不能确定交换的元素与基准的关系，得再进行一次比较
k--;
}
}
//将基准归位
swap(nums, right, j);
return new int[]{i + 1, j};//返回与基准相等的区域左、右边界
}
/**
* 两数交换
*
* @param nums
* @param x
* @param y
*/
public void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
复杂度分析
时间复杂度在最佳情况是O(nlogn)，在最坏情况下，例如对于逆序的序列进行快速排序，每次挑选的基准是序列中的最大值，则每次只生成两部分，左边是比基准小的值，右边是基准元素，递归层度为n，时间复杂度是O(n*n)。因此可以再次优化，随机挑选一个元素作为基准，时间复杂度能够稳定在O(nlogn)。
空间复杂度在O(logn)，在最坏的情况下空间复杂度还是O(n)，平均情况下复杂度是O(logn)。
三、插入排序
插入排序的基本思想是：每次将一个待排序的元素插入到前面已经排完序的序列适当的位置，直至所有元素插入完成位置。插入排序分为直接插入排序、折半插入排序、希尔排序。
直接插入排序
直接插入排序是稳定的排序
思路
将序列分为左边的有序区和右边的无序区，例如有序区是[1,4,5],而无序区是[2,6]，
提取无序区的第一个元素2，与有序区从右往左比较，2比5小，2插入5的前面，即变成[1,4,2,5,6]。
接着2比4小，2插入4的前面，变成[1,2,4,5,6]。现在有序区变成[1,2,4,5]，无序区为[6]
提取无序区的第一个元素6，与有序区从右往左比较，6比5大，不需变换位置。现在有序区变成[1,2,4,5,6]，排序完成。
代码实现
public static void indirectInSertSort(int[] array) {
if (array == null || array.length < 2)
return;
for (int i = 1; i < array.length; i ++){
if(array[i - 1] > array[i]){//前一个元素比当前元素大才需要排序
for (int j = i; j >= 1 && array[j - 1] > array[j]; j--){
swap(array, j -1, j);
}
}
}
}
优化
上面简单的插入排序，需要可以插入的元素就两两交换，交换次数为3。如果n个可以插入的位置，交换次数则为3n。我们可以将待插入元素存入临时变量tmp，遇到前面元素比tmp大，直接后移，直到前面元素小于tmp，将tmp插入它的后面，这样减少了交换次数，这样如果有n个可以插入的位置，交换次数为n+2。
public static void indirectInSertSort2(int[] array, int n) {
if (nums == null || nums.length <= 1)
return;
int tmp = 0;//临时变量
int k = 0;
for (int i = 1; i < nums.length; i++) {
tmp = nums[i];
k = i - 1;
while (k >= 0 && nums[k] > tmp) {
//后移
nums[k + 1] = nums[k];
k--;
}
//将tmp插入到适当的位置
nums[k + 1] = tmp;
}
}
复杂度分析
最好情况就是已经是有序，时间复杂度为O(n)，最坏情况是逆序，时间复杂度为O(n * n)；平均复杂度是O(n * n)，空间复杂度为O(1)。
折半插入排序
思路
直接插入排序是每次从当前元素往前一个个遍历，找到插入的位置则插入，如果遍历的元素多，会占用太多的时间，而因为遍历的元素处于有序区，可以采用折半查找的方法找到插入的位置，直接插入。是一种稳定的排序。
实现
public static void binaryInsertSort(int[] nums) {
if (nums == null || nums.length <= 1)
return;
int tmp = 0;
int left = 0, right = 0;
int middle = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
//二分查找找到插入的位置
tmp = nums[i];
left = 0;
right = i - 1;
while (left <= right) {
middle = (left + right) / 2;
if (nums[middle] <= tmp) {
left = middle + 1;
} else {
right = middle - 1;
}
}
//将tmp插入到right+1或left的位置
for (int j = i - 1; j >= right + 1; j--) {
nums[j + 1] = nums[j];
}
nums[right + 1] = tmp;
}
}
}
复杂度分析
时间复杂度：最好O(n)， 最坏和平均复杂度为O(n*n)。空间复杂度为O(1)
希尔排序
思路
希尔排序也是一种插入排序，实际上是一种分组插入排序。其基本思想是取一个小于n的整数作为增量d(一般取n/2)，将序列进行分组，然后在分组内进行直接插入排序或折半插入排序。接着缩小增量d（d= d /2），在进行排序。重复以上过程，直至增量为0为止。是一种不稳定的排序。
详细参考：https://www.cnblogs.com/chengxiao/p/6104371.html
实现
/**
* 希尔排序
* @param nums
*/
public static void shellSort(int[] nums){
if (nums == null || nums.length <= 1)
return;
int tmp = 0;
int j = 0;
//length希尔增量
for (int length = nums.length / 2; length >= 1 ; length /= 2) {
for (int i = length; i < nums.length ; i++) {
j = i;
tmp = nums[i];
if(nums[j - length] > nums[j]){
//判断是否执行插入
while (j - length >= 0 && nums[j - length] > tmp){
nums[j] = nums[j - length];
j = j - length;
}
nums[j] = tmp;
}
}
}
}
复杂度分析
空间复杂度为O(1)，时间复杂度为O（n2/3）
四、归并排序
思路
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
二路归并排序分为分和治两个阶段。分就是将数组分成两个子数组，接着在递归分解两个子数组，直至数组长度为一。治就是将两个有序的子数组合并成一个大的有序数组。
具体参考：https://www.cnblogs.com/chengxiao/p/6194356.html
代码实现
public static void mergeSort(int[] nums, int left, int right) {
if(left < right){
int middle = (left + right) / 2;
mergeSort(nums, left, middle);//归并排序左边的子数组
mergeSort(nums, middle + 1, right);//归并排序右边的子数组
merge(nums, left, middle, right); //合并两个数组
}
}
/**
* 合并两个数组，使之有序
*
* @param nums
* @param left 左边数组的左边界
* @param middle 左边数组的右边界
* @param right 右边数组的右边界
*/
private static void merge(int[] nums, int left, int middle, int right) {
//创建辅助数组
int[] help = new int[right - left + 1];
int index = 0;//辅助数组当前元素的下标
int low1 = left;
int low2 = middle + 1;
while (low1 <= middle && low2 <= right) {
if(nums[low1] <= nums[low2]){
help[index] = nums[low1];
low1 ++;
index ++;
}else{
help[index] = nums[low2];
low2 ++;
index ++;
}
}
//将剩下的元素插入到辅助数组
while (low1 <= middle){
help[index ++] = nums[low1++];
}
while (low2 <= right){
help[index ++] = nums[low2++];
}
//将辅助数组的结果覆盖原数组
for (int i = 0; i < index; i++) {
nums[left + i] = help[i];
}
}
复杂度分析
时间复杂度在最坏、最好和平均情况下都是O(nlogn)，而空间复杂度为O(n)。
五、二叉排序树排序
思路
二叉树搜索排序用数组内的所有元素构建一个搜索二叉树，然后用中序遍历重新将所有的元素填充回原来的数组中。因为搜索二叉树不能用数组来表示，所以必须使用额外的数据结构来构建二叉树。
作者：bryansun2020
链接：https://leetcode-cn.com/problems/sort-an-array/solution/shi-er-chong-pai-xu-suan-fa-bao-ni-man-yi-dai-gift/
来源：力扣（LeetCode）
代码实现
//结点的类
class TreeNode {
int val; //结点值
TreeNode lchild; //左子树
TreeNode rchild;//右子树
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
this.lchild = this.rchild = null;
}
}
//排序
class BtreeSort{
public static void binaryTreeSort(int[] nums) {
if (nums == null || nums.length <= 1)
return;
//创建二叉搜索树
TreeNode root = new TreeNode(nums[0]);
for (int i = 1; i < nums.length; i++) {
buildTree(root, nums[i]);
}
//二叉搜索树进行中序遍历得到升序序列
inorderTraversal(root, nums, new int[1]);
}
/**
* @param root 当前子树根节点
* @param nums 目标数组
* @param ints 记录当前结点在目标数组的下标
*/
private static void inorderTraversal(TreeNode root, int[] nums, int[] pos) {
if (root != null) {
inorderTraversal(root.lchild, nums, pos);
nums[pos[0]++] = root.val;
inorderTraversal(root.rchild, nums, pos);
}
}
/**
* 将元素num插入二叉搜索树
*
* @param root
* @param num
*/
private static void buildTree(TreeNode root, int num) {
if (root.val <= num) {
//元素大于等于根节点，插入到右子树
if (root.rchild == null) {
TreeNode node = new TreeNode(num);
root.rchild = node;
} else {
buildTree(root.rchild, num);
}
} else {
//元素小于根节点，插入到左子树
if (root.lchild == null) {
TreeNode node = new TreeNode(num);
root.lchild = node;
} else {
buildTree(root.lchild, num);
}
}
}
}
时间复杂度上面根据原数组变化比较大，最差情况是整个数组是已经排好序的，这样二叉树会变成一个链表结构，时间复杂度退化到了O(n^2) ，但是最优和平均情况下时间复杂度在O(nlogn)水平。
空间复杂度是O(n)，因为要构建一个包含n个元素的二叉搜索树。
这个算法是稳定，在构建二叉树的过程中能够保证元素顺序的一致性。
六、计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）
思路
计数排序是创建长度为原数组最大元素和最小元素之差的辅助数组，用来统计原数组中每个元素出现的频度，然后遍历辅助数组，根据每个元素出现的频度，将结果输出到原数组。
代码实现
/**
* 计数排序
*
* @param nums
*/
public static void countSort(int nums[]) {
//找出数组的最大值和最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int length = nums.length; //原数组长度
for (int i = 0; i < length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
//创建统计元素出现频度的数组
int[] count = new int[max - min + 1];
//遍历原数组，统计元素出现的频度
for (int i = 0; i < length; i++) {
count[nums[i] - min]++;
}
//遍历频度数组，将结果覆盖原数组
int index = 0;
for (int i = 0; i < count.length; i++) {
for (int j = 1; j <= count[i]; j++) {
nums[index ++] = i + min;
}
}
}
复杂度分析
时间复杂度为O(n + r)，r为辅助数组的长度，空间复杂度为O(r);
七、桶排序
思想
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里，然后对于每个桶子里的元素进行排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。然后将桶中的元素输出到原数组，从而得到有序序列。桶排序是鸽巢排序的一种归纳结果，是一种稳定的排序算法。
代码实现
public static void bucketSort(int[] nums) {
if (nums == null || nums.length <= 1)
return;
int bucketSize = 100; //指定每个桶的大小
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : nums) {//找出数组的最大值和最小值
max = Math.max(max, num);
min = Math.min(min, num);
}
int count = max - min + 1;//计算数组的变化范围
int bucketNum = count % bucketSize == 0 ? count / bucketSize : count / bucketSize + 1;//计算桶的数量
ArrayList[] buckets = new ArrayList[bucketNum];
//遍历数组，将数组中的元素丢进对应的桶
for (int num : nums) {
int index = (num - min) / bucketSize;//计算元素对应的桶坐标
if (buckets[index] == null)
buckets[index] = new ArrayList<Integer>();
buckets[index].add(num);
}
int index = 0;
//对桶中的元素进行排序
for (ArrayList bucket : buckets) {
if (bucket != null) {//过滤空桶
bucket.sort(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return (Integer) o1 - (Integer) o2;
}
});
//将桶中的元素输出到原数组
for (Object num : bucket) {
nums[index ++] = (int)num;
}
}
}
}
复杂度分析
时间复杂度为O(n +r)，n为元素的数量，r为桶的数量。空间复杂度为O(n + r)。需要额外的空间来保存所有的桶和桶里面的元素。
八、基数排序
代码实现
/**
* 基数排序
*
* @param nums
*/
public static void radixSort(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
//十进制数的基数为0~9,因为右正负之分，所以基数大小为19，则建立19个桶
List<Integer>[] buckets = new List[19];
for (int i = 0 ; i < buckets.length; i++) {
buckets[i] = new ArrayList<Integer>();
}
//计算数组中最大位数
int max = Integer.MIN_VALUE;
for (int num : nums) {
max = Math.max(max, Math.abs(num));
}
int digit = 0;
while (max > 0) {
max = max / 10;
digit ++;
}
int pos = 0;
int curr = 0;
//进行分配和收集过程，从最后一位开始
for (int i = 1, mod = 1; i <= digit; i++, mod *=10) {
//遍历每个元素，将 元素装进对应的桶
for (int num : nums) {
//获取对应元素对应位数的值
pos = (num / mod) % 10;
buckets[pos + 9].add(num);
}
//将桶中的元素输出
curr = 0;
for (int j = 0; j < buckets.length; j++) {
for (Integer number : buckets[j]) {
nums[curr ++] = number;
}
//清空桶
buckets[j].clear();
}
}
}
复杂度分析
时间复杂度为O(d(n + r))，空间复杂度为O(r + n)。r为桶的个数，d为最高位数
总结
| 排序算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n*n) | O(n*n) | O(1) | 稳定 |
| 折半插入排序 | O(n) | O(n*n) | O(n*n) | O(1) | 稳定 |
| 希尔排序 | O(n2/3) | O(n2/3) | O(n2/3) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n*n) | O(n*n) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n*n) | O(logn) | 不稳定 |
| 简单选择排序 | O(n*n) | O(n*n) | O(n*n) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 二叉树排序 | O(nlogn) | O(nlogn) | O(n*n) | O（n） | 稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 计数排序 | O(n+r) | O(n+r) | O(n+r) | O(n+r) | 稳定 |
| 桶排序 | O(n+r) | O(n+r) | O(n+r) | O(n+r) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 |
