排序算法的介绍
排序也称排序算法(SortAlgorithm)，排序是将 一组数据，依 指定的顺序进行 排列的过程。
排序的分类
按照是否使用内存可以分为内部排序和外部排序两种：
-
内部排序: 指将需要处理的所有数据都加载到 内部存储器( 内存)中进行排序。
-
外部排序法： 数据量过大，无法全部加载到内存中，需要借助 外部存储( 文件等)进行排序。
按照是否稳定可以分为稳定排序和非稳定排序两种：
如果一个排序算法能够保留数组中重复元素的相对位置则可以被称为是 稳定 的。反之，则是 非稳定 的。
排序算法的实现
参考一：Java实现八大排序算法
参考二：尚硅谷Java数据结构和java算法，韩顺平数据结构和算法
冒泡排序
基本思想
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述
冒泡排序算法的运作如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码实现
public class BubbleSort {
/**
* 冒泡排序(从小到大)：比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* @param array
*/
private static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
bubbleSort(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n) | O(n²) | O(1) |
冒泡排序是最容易实现的排序,。
- 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²)。
- 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n)。
- 平均来讲, 时间复杂度为O(n²)。
- 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1)。
总结与思考
由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
选择排序
基本思想
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
- 从未排序序列中，找到关键字最小的元素
- 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
- 重复1、2步，直到排序结束。
代码实现
public class SelectSort {
/**
* 选择排序：在未排序序列中找到最小元素，存放到排序序列的起始位置。
* @param array
*/
private static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int min = i;
//选出之后待排序中值最小的位置
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
//最小值不等于当前值时进行交换
if (min != i) {
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
selectSort(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
以下是选择排序复杂度:
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
总结与思考
选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。
即便是这样，它的排序结果也还是不稳定的。
唯一值得高兴的是，它并不耗费额外的内存空间。
插入排序
基本思想
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
代码实现
public class InsertSort {
/**
* 插入排序：对于欲排序的元素以插入的方式找寻该元素的适当位置
* @param array
*/
private static void insertSort(int[] array) {
int insertVal;
int insertIndex;
for (int i = 1; i < array.length; i++) {
insertVal = array[i];
insertIndex = i - 1;
// 给 insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给 insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < array[insertIndex]) {
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
if (insertIndex + 1 != i) {
array[insertIndex + 1] = insertVal;
}
}
}
/**
* 插入排序
* @param array
*/
private static void insertSort2(int[] array) {
for (int i = 1; i < array.length; i++) {
// 待插入的值
int num = array[i];
int j;
for (j = i; j > 0 && num < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = num;
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
insertSort2(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
直接插入排序复杂度如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
总结与思考
插入排序所需的时间取决于输入元素的初始顺序。
例如，对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多。
希尔排序
希尔排序，也称 递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是 非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一
基本思想
希尔排序是把记录按下标的一定增量（gap）分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多， 当增量减至 1 时，整个文件恰被分成一组，算法便终止
算法描述
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
如下图所示：
代码实现
public class ShellSort {
/**
* 希尔排序：交换法
*
* @param array
*/
private static void shellSort(int[] array) {
int tmp;
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
// 遍历各组中所有的元素(共 gap 组，每组有个元素), 步长 gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，说明交换
if (array[j] > array[j + gap]) {
tmp = array[j];
array[j] = array[j + gap];
array[j + gap] = tmp;
}
}
}
}
}
/**
* 希尔排序：移位法
*
* @param array
*/
private static void shellSort2(int[] array) {
// 增量 gap, 并逐步的缩小增量
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int j = i;
int tmp = array[j];
if (array[j] < array[j - gap]) {
while (j - gap >= 0 && tmp < array[j - gap]) {
//移动
array[j] = array[j - gap];
j -= gap;
}
//当退出 while 后，就给 tmp 找到插入的位置
array[j] = tmp;
}
}
}
}
/**
* 《算法》中给出的步长选择策略
* @param a
*/
private static void shellSort3(int[] a) {
int length = a.length;
int gap = 1;
while (gap < length / 3) {
gap = 3 * gap + 1;
}
for (; gap >= 1; gap /= 3) {
for (int i = 0; i < a.length - gap; i += gap) {
for (int j = i + gap; j > 0; j -= gap) {
if (a[j] < a[j - gap]) {
int temp = a[j];
a[j] = a[j - gap];
a[j - gap] = temp;
}
}
}
}
}
public static void main(String[] args) {
int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
System.out.println("排序前顺序：" + Arrays.toString(array));
shellSort3(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
以下是希尔排序复杂度:
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) |
总结与思考
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。
快速排序
基本思想
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法描述
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
- 从数列中挑出一个元素，称为”基准”（pivot）。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
代码实现
public class QuickSort {
/**
* 快速排序：以第一个元素为基准值
*
* @param array
* @param low
* @param high
*/
private static void quickSort(int[] array, int low, int high) {
if (low > high) {
return;
}
int left = low;
int right = high;
// 中轴值
int pivot = array[low];
while (left < right) {
// 从右边找比基准值小的
while (left < right && array[right] >= pivot) {
right--;
}
// 从左边找比基准值大的
while (left < right && array[left] <= pivot) {
left++;
}
if (left < right) {
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
// 当左右指针相遇时重新调整基准值
int tmp = array[left];
array[left] = array[low];
array[low] = tmp;
quickSort(array, low, left - 1);
quickSort(array, left + 1, high);
}
/**
* 快速排序：以中间值为基准
*
* @param array
* @param low
* @param high
*/
private static void quickSort2(int[] array, int low, int high) {
int left = low;
int right = high;
int mix = array[(low + high) / 2];
int tmp;
while (left < right) {
while (array[left] < mix) {
left++;
}
while (array[right] > mix) {
right--;
}
if (left >= right) {
break;
}
tmp = array[right];
array[right] = array[left];
array[left] = tmp;
if (array[left] == mix) {
right--;
}
if (array[right] == mix) {
left++;
}
}
if (left == right) {
left++;
right--;
}
if (low < right) {
quickSort2(array, low, left - 1);
}
if (high > left) {
quickSort2(array, right + 1, high);
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
quickSort2(array, 0, array.length - 1);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
以下是快速排序算法复杂度:
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog₂n) | O(nlog₂n) | O(n²) | O(1)（原地分区递归版) |
堆排序
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复 杂度均为 O(nlogn)，它也是不稳定排序。
- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有 要求结点的左孩子的值和右孩子的值的大小关系。
基本思想
此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
算法描述
- 先将初始序列K[1..n]K[1..n]建成一个大顶堆, 那么此时第一个元素K1K1最大, 此堆为初始的无序区.
- 再将关键字最大的记录K1K1 (即堆顶, 第一个元素)和无序区的最后一个记录 KnKn 交换, 由此得到新的无序区K[1..n−1]K[1..n−1]和有序区K[n]K[n], 且满足K[1..n−1].keys⩽K[n].keyK[1..n−1].keys⩽K[n].key
- 交换K1K1 和 KnKn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]K[1..n−1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止。
代码实现
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。
总结起来就是定义了以下几种操作：
- 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
对于堆节点的访问：
- 父节点i的左子节点在位置：
(2*i+1); - 父节点i的右子节点在位置：
(2*i+2); - 子节点i的父节点在位置：
floor((i-1)/2);
public class HeapSort {
/**
* 堆排序：构建大顶堆
*
* @param array
*/
private static void headSort(int[] array) {
for (int i = array.length - 1; i > 0; i--) {
maxHeapify(array, i);
//堆顶元素(第一个元素)与Kn交换
int temp = array[0];
array[0] = array[i];
array[i] = temp;
}
}
/***
*
* 将数组堆化
* i = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
*
* @param array
* @param n
*/
public static void maxHeapify(int[] array, int n) {
int child;
for (int i = (n - 1) / 2; i >= 0; i--) {
//左子节点位置
child = 2 * i + 1;
//右子节点存在且大于左子节点，child变成右子节点
if (child != n && array[child] < array[child + 1]) {
child++;
}
//交换父节点与左右子节点中的最大值
if (array[i] < array[child]) {
int temp = array[i];
array[i] = array[child];
array[child] = temp;
}
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
headSort(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
- 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
- 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
- 堆排序的过程由n次第2步完成, 时间复杂度为O(nlgn).
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) |
总结与思考
由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
基本思想
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法描述
归并排序可通过两种方式实现:
- 自上而下的递归
- 自下而上的迭代
递归法（假设序列共有n个元素）：
- 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
- 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
- 重复步骤2，直到所有元素排序完毕。
迭代法
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
代码实现
归并排序其实要做两件事：
- 分解：将序列每次折半拆分
- 合并：将划分后的序列段两两排序合并
因此，归并排序实际上就是两个操作，拆分+合并
public class MergeSort {
/**
* 归并所需的辅助数组
*/
private static int[] aux;
/**
* 归并排序
* @param array
*/
public static void mergeSort(int[] array) {
//一次性分配空间
aux = new int[array.length];
decompose(array, 0, array.length - 1);
}
/**
* 分解
* @param array
* @param low
* @param high
*/
public static void decompose(int[] array, int low, int high) {
if (low >= high) {
return;
}
int mid = (low + high) / 2;
//将左半边排序
decompose(array, low, mid);
//将右半边排序
decompose(array, mid + 1, high);
merge(array, low, mid, high);
}
/**
* 该方法先将所有元素复制到aux[]中，然后在归并会array[]中。方法咋归并时(第二个for循环)
* 进行了4个条件判断：
* - 左半边用尽(取右半边的元素)
* - 右半边用尽(取左半边的元素)
* - 右半边的当前元素小于左半边的当前元素(取右半边的元素)
* - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
* @param array
* @param low
* @param mid
* @param high
*/
public static void merge(int[] array, int low, int mid, int high) {
//将a[low..mid]和a[mid+1..high]归并
int i = low, j = mid + 1;
for (int k = low; k <= high; k++) {
aux[k] = array[k];
}
for (int k = low; k <= high; k++) {
if (i > mid) {
array[k] = aux[j++];
} else if (j > high) {
array[k] = aux[i++];
} else if (aux[j] < aux[i]) {
array[k] = aux[j++];
} else {
array[k] = aux[i++];
}
}
}
/**
* 更容易理解，参照图解
* @param arr
* @param left
* @param mid
* @param right
*/
private static void merge2(int[] arr, int left, int mid, int right) {
//左序列指针
int i = left;
//右序列指针
int j = mid + 1;
//临时数组指针
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
aux[t++] = arr[i++];
} else {
aux[t++] = arr[j++];
}
}
while (i <= mid) {
//将左边剩余元素填充进temp中
aux[t++] = arr[i++];
}
while (j <= right) {
//将右序列剩余元素填充进temp中
aux[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right) {
arr[left++] = aux[t++];
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
mergeSort(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
以下是归并排序算法复杂度:
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) |
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程， 时间复杂度为O(n)， 故其综合时间复杂度为O(nlogn)。另一方面， 归并排序多次递归过程中拆分的子数组需要保存在内存空间， 其空间复杂度为O(n)。
总结与思考
归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比，它的主要缺点则是他所需的额外空间和N成正比。
基数排序
基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基本思想
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
- MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。
- LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
算法描述
我们以LSD为例，从最低位开始，具体算法描述如下：
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
代码实现
public class RadixSort {
/**
* 基数排序
* @param array
*/
public static void radixSort(int[] array) {
if (array.length <= 1) {
return;
}
//取得数组中的最大数，并取得位数
int max = 0;
for (int value : array) {
if (max < value) {
max = value;
}
}
int maxDigit = 1;
while (max / 10 > 0) {
maxDigit++;
max = max / 10;
}
//申请一个桶空间
int[][] buckets = new int[10][array.length];
int base = 10;
//从低位到高位，对每一位遍历，将所有元素分配到桶中
for (int i = 0; i < maxDigit; i++) {
//存储各个桶中存储元素的数量
int[] bktLen = new int[10];
//分配：将所有元素分配到桶中
for (int value : array) {
int whichBucket = (value % base) / (base / 10);
buckets[whichBucket][bktLen[whichBucket]] = value;
bktLen[whichBucket]++;
}
//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
int k = 0;
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktLen[b]; p++) {
array[k++] = buckets[b][p];
}
}
base *= 10;
}
}
public static void main(String[] args) {
int[] array = {4, 3, 5, 2, 1};
System.out.println("排序前顺序：" + Arrays.toString(array));
radixSort(array);
System.out.println("排序后顺序：" + Arrays.toString(array));
}
}
复杂度分析
以下是基数排序算法复杂度，其中k为最大数的位数：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(d*(n+r)) | O(d*(n+r)) | O(d*(n+r)) | O(n+r) |
其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。
总结与思考
基数排序更适合用于对时间, 字符串等这些 整体权值未知的数据 进行排序。
基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶
- 计数排序：每个桶只存储单一键值
- 桶排序：每个桶存储一定范围的数值
总结和对比
排序性能对比：
| 排序类型 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 直接插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(nlogn) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(nlogn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n²) | O(n+k) | 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+kd)) | O(n+kd) | 稳定 |
解释：n: 数据规模 k: “桶”的个数
上篇AQS源码解析