共计 12538 个字符，预计需要花费 32 分钟才能阅读完成。
Java 八大排序算法
一：定义
排序：对一序列对象依据某一关键词进行排序
二：冒泡排序
冒泡排序算是接触的第一个排序算法
根本思维：
冒泡排序（Bubble Sort）是一种简略的排序。它反复地走访过要排序的数列，一次比拟两个元素，如果他们的程序谬误就把他们替换过去。走访数列的工作是反复地进行直到没有须要替换，也就是说该数列曾经排序实现。
算法形容
1. 比拟相邻的元素，如果第一个比第二个大，就替换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对。这步做完后，最初的元素会是最大的数。
3. 针对所有的元素反复以上的步骤，除了最初一个。
4. 继续每次对越来越少的元素反复下面的步骤，直到没有任何一对数字须要比拟。
代码实现
public static void BubbleSort(int[] numbers){
// 外层循环管制比拟次数
for (int i=0;i<numbers.length-1;i++){
// 内层循环管制达到地位
for (int j=0;j<numbers.length-1-i;j++){
// 比拟后面的元素比前面元素大替换，同理也能够比拟小
if (numbers[j]>numbers[j+1]){int temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
}
}
}
}
// 调用
int[] n={60,38,5,14,7,23,89,77,88,4,35,45,67,99,87};
System.out.println(Arrays.toString(n));
BubbleSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]冒泡排序的优化
有这种状况，可能在最初几趟曾经排序好了，还在持续排序操作，所以咱们能够在替换的中央加一个标记，如果那一趟排序没有替换元素，阐明这组数据曾经有序，不必再继续下去。
// 缩小一些可能循环的次数
public static void BubbleSort(int[] numbers){
// 外层循环管制比拟次数
for (int i=0;i<numbers.length-1;i++){
int flag=0;// 默认标记为 0
// 内层循环管制达到地位
for (int j=0;j<numbers.length-1-i;j++){
// 比拟后面的元素比前面元素大替换，同理也能够比拟小
if (numbers[j]>numbers[j+1]){int temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
flag=1;// 如果还有替换，标记为 1
}
}
if (flag==0){// 如果没有替换过的元素，则曾经有序了
return;
}
}
}复杂度剖析
冒泡排序是最容易实现的排序, 最坏的状况是每次都须要替换, 共需遍历并替换将近 n²/ 2 次, 工夫复杂度为 O(n²). 最佳的状况是内循环遍历一次后发现排序是对的, 因而退出循环, 工夫复杂度为 O(n). 均匀来讲, 工夫复杂度为 O(n²). 因为冒泡排序中只有缓存的 temp 变量须要内存空间, 因而空间复杂度为常量 O(1).
三：疾速排序
疾速排序是由东尼·霍尔所倒退的一种排序算法。在均匀情况下，排序 n 个我的项目要 Ο(nlogn) 次比拟。在最坏情况下则须要 Ο(n2) 次比拟，但这种情况并不常见。事实上，疾速排序通常显著比其余 Ο(nlogn) 算法更快，因为它的外部循环（inner loop）能够在大部分的架构上很有效率地被实现进去
根本思维
疾速排序的根本思维：挖坑填数 + 分治法。
疾速排序应用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
疾速排序又是一种分而治之思维在排序算法上的典型利用。实质上来看，疾速排序应该算是在冒泡排序根底上的递归分治法。
疾速排序的名字起的是简略粗犷，因为一听到这个名字你就晓得它存在的意义，就是快，而且效率高！它是解决大数据最快的排序算法之一了。尽管 Worst Case 的工夫复杂度达到了 O(n²)，然而人家就是优良，在大多数状况下都比均匀工夫复杂度为 O(n logn) 的排序算法体现要更好。
算法形容
疾速排序应用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
1. 从数列中挑出一个元素，称为“基准”
2. 从新排序数列，所有比基准值小的元素摆在基准的后面，所有比基准大的元素摆在基准的前面雷同的数能够到任一边）。在这个分区完结之后，该基准就处于数列的两头地位。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是曾经排序好了。这个算法肯定会完结，因为在每次的迭代（iteration）中，它至多会把一个元素摆到它最初的地位去。
代码实现
public static void QuickSort(int[] a, int low, int high) {
// 这里的 low 和 hight 传递的是数组的起始地位 0，和数组的完结地位 length-1
// 曾经排完
if (low >= high) {return;}
int left = low;// 起始地位 0, 这地位是扭转的
int right = high;// 完结地位 length-1, 这地位是扭转的
// 保留基准值
// 这里是把起始地位的数，设置为基准数，如 60
int pivot = a[left];
while (left < right) {
// 从后向前找到比基准小的元素
while (left < right && a[right] >= pivot)
right--;
a[left] = a[right];
// 从前往后找到比基准大的元素
while (left < right && a[left] <= pivot)
left++;
a[right] = a[left];
}
// 搁置基准值，筹备分治递归快排
a[left] = pivot;
QuickSort(a, low, left - 1);
QuickSort(a, left + 1, high);
}
// 应用
int[] n={60,38,5,14,7,23,89,77,88,4,35,45,67,99,87};
System.out.println(Arrays.toString(n));
QuickSort(n,0,n.length-1);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]下面是递归版的疾速排序：通过把基准插入到适合的地位来实现分治，并递归地对分治后的两个划分持续快排。那么非递归版的快排如何实现呢？
常识的扩容
因为 递归的实质是栈 ，所以咱们非递归实现的过程中，能够借助栈来保留两头变量就能够实现非递归了。在这里两头变量也就是通过 Pritation 函数划分区间之后分成左右两局部的首尾指针，只须要保留这两局部的首尾指针即可。
public static void QuickSortByStack(int[] a) {Stack<Integer> stack = new Stack<Integer>();// 定义栈
// 初始状态的左右指针入栈
stack.push(0);
stack.push(a.length - 1);
while (!stack.isEmpty()) {
// 出栈进行划分
int high = stack.pop();
int low = stack.pop();
int pivotIndex = partition(a, low, high);
// 保留两头变量
if (pivotIndex > low) {stack.push(low);
stack.push(pivotIndex - 1);
}
if (pivotIndex < high && pivotIndex >= 0) {stack.push(pivotIndex + 1);
stack.push(high);
}
}
}
private static int partition(int[] a, int low, int high) {if (low >= high) return -1;
int left = low;
int right = high;
// 保留基准的值
int pivot = a[left];// 最右边的数值为基准
while (left < right) {
// 从后向前找到比基准小的元素，插入到基准地位中
while (left < right && a[right] >= pivot) {right--;}
a[left] = a[right];
// 从前往后找到比基准大的元素
while (left < right && a[left] <= pivot) {left++;}
a[right] = a[left];
}
// 搁置基准值，筹备分治递归快排
a[left] = pivot;
return left;
}
// 应用
int[] n={60,38,5,14,7,23,89,77,88,4,35,45,67,99,87};
System.out.println(Arrays.toString(n));
QuickSortByStack(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]下面两个冒泡排序和疾速排序属于替换排序
四：间接插入排序
根本思维
通常人们整顿桥牌的办法是一张一张的来，将每一张牌插入到其余曾经有序的牌中的适当地位。在计算机的实现中，为了要给插入的元素腾出空间，咱们须要将其余所有元素在插入之前都向右挪动一位。
算法形容
一般来说，插入排序都采纳 in-place 在数组上实现。具体算法形容如下：
1. 从第一个元素开始，该元素能够认为曾经被排序
2. 取出下一个元素，在曾经排序的元素序列中从后向前扫描（从第 2 个元素开始和后面曾经排序好的比拟）
3. 如果该元素（已排序）大于新元素，将该元素移到下一地位
4. 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位
5. 将新元素插入到该地位后
6. 反复步骤 2~5
代码实现
public static void InsertSort(int[] numbers){for (int i=0;i<numbers.length-1;i++){
// 外层循环管制比拟次数
for (int j=i+1;j>0;j--){
// 从第二个元素开始比拟
if (numbers[j]<numbers[j-1]) {
// 例如第一次，如果第 2 个元素小于默认排好的第一个元素
int temp=numbers[j];// 第二个元素赋值给长期变量
numbers[j]=numbers[j-1];// 第一个元素赋值给第二元素
numbers[j-1]=temp;// 长期变量赋值给第一个元素
}
}
}
}
插入排序的变种，二分插入排序
public static void binaryInsertSort(int[] numbers) {if (numbers != null && numbers.length > 1) {for (int i = 1; i < numbers.length; i++) {
int left = 0;
int right = i-1;
int mid;
int temp = numbers[i];
if(temp < numbers[right]){ // 以后值小于有序序列的最大值时，开始查找插入地位
while(left <= right){mid = (left + right)/2;
if(numbers[mid] < temp){left = mid + 1; // 放大插入区间}else if(numbers[mid] > temp){right = mid - 1; // 放大插入区间}else{// 待插入值与有序序列中的 target[mid]相等，保障稳定性的解决
left = left + 1;
}
}
// left 及其前面的数据程序向后挪动，并在 left 地位插入
for (int j = i; j > left; j--) {numbers[j] = numbers[j-1];
}
numbers[left] = temp;
}
}
}
}
// 应用
int[] n={60,38,5,14,7,23,89,77,88,4,35,45,67,99,87};
System.out.println(Arrays.toString(n));
binaryInsertSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
五：希尔排序
希尔排序，也称 递加增量排序算法，是插入排序的一种更高效的改良版本。希尔排序是 非稳固排序算法。
希尔排序是基于插入排序的以下两点性质而提出改良办法的：
插入排序在对简直曾经排好序的数据操作时，效率高，即能够达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据挪动一
希尔排序是先将整个待排序的记录序列宰割成为若干子序列别离进行间接插入排序，待整个序列中的记录“根本有序”时，再对整体记录进行顺次间接插入排序。
根本思维
将待排序数组依照步长 gap 进行分组，而后将每组的元素利用间接插入排序的办法进行排序；每次再将 gap 折半减小，循环上述操作；当 gap= 1 时，利用直接插入，实现排序。
能够看到步长的抉择是希尔排序的重要局部。只有最终步长为 1 任何步长序列都能够工作。一般来说最简略的步长取值是首次取数组长度的一半为增量，之后每次再减半，直到增量为 1。
算法形容
1. 抉择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2. 按增量序列个数 k，对序列进行 k 趟排序；
3. 每趟排序，依据对应的增量 ti，将待排序列宰割成若干长度为 m 的子序列，别离对各子表进行间接插入排序。仅增量因子为 1 时，整个序列作为一个表来解决，表长度即为整个序列的长度。
代码实现
/**
* 希尔排序 针对有序序列在插入时采纳交换法
*/
public static void ShellSort(int[] arr) {
// 增量 gap，并逐渐放大增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从第 gap 个元素，一一对其所在组进行间接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
while (j - gap >= 0 && arr[j] < arr[j - gap]) {
// 插入排序采纳交换法
swap(arr, j, j - gap);
j -= gap;
}
}
}
}
public static void swap(int[] arr, int a, int b) {arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
希尔排序更高效的起因是它衡量了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是局部有序的，这两种状况都很适宜插入排序。
六：简略抉择排序
根本思维
抉择排序（Selection sort）是一种简略直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位，而后，再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。以此类推，直到所有元素均排序结束。
算法形容
1. 从未排序序列中，找到关键字最小的元素
2. 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素调换
3. 反复 1、2 步，直到排序完结。
代码实现
public static void SelectSort(int[] numbers) {for (int i = 0; i < numbers.length; i++) {
int min = i;// 默认从 0 开始的序号的值为最小值
// 选出之后待排序中值最小的地位
for (int j = i + 1; j < numbers.length; j++) {if (numbers[j] < numbers[min]) {// 比拟值的大小，拿到序号
min = j;// 拿到序号
}
}
// 最小值不等于以后值时进行替换
if (min != i) {int temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
}
// 调用
int[] n = {60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87};
System.out.println(Arrays.toString(n));
SelectSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
抉择排序的简略和直观货真价实，这也造就了它”出了名的慢性子”，无论是哪种状况，哪怕原数组已排序实现，它也将破费将近 n²/ 2 次遍从来确认一遍。即使是这样，它的排序后果也还是不稳固的。惟一值得快乐的是，它并不消耗额定的内存空间。
七：堆排序
堆的定义如下：n 个元素的序列 {k1,k2,..,kn}
当且仅当满足下关系时，称之为堆
把此序列对应的二维数组看成一个齐全二叉树。那么堆的含意就是：齐全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字必定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因而咱们可应用大顶堆进行升序排序, 应用小顶堆进行降序排序。
根本思维
此处以大顶堆为例，堆排序的过程就是将待排序的序列结构成一个堆，选出堆中最大的移走，再把残余的元素调整成堆，找出最大的再移走，反复直至有序
算法形容
1. 先将初始序列 K[1..n] 建成一个大顶堆, 那么此时第一个元素 K1 最大, 此堆为初始的无序区.
2. 再将关键字最大的记录 K1 (即堆顶, 第一个元素)和无序区的最初一个记录 Kn 替换, 由此失去新的无序区 K[1..n−1]和有序区 K[n], 且满足 K[1..n−1].keys⩽K[n].key
3. 替换 K1 和 Kn 后, 堆顶可能违反堆性质, 因而需将 K[1..n−1]调整为堆. 而后反复步骤 2, 直到无序区只有一个元素时进行。
代码实现
从算法形容来看，堆排序须要两个过程，一是建设堆，二是堆顶与堆的最初一个元素替换地位。所以堆排序有两个函数组成。一是建堆函数，二是重复调用建堆函数以抉择出残余未排元素中最大的数来实现排序的函数。
- 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创立最大堆（Build_Max_Heap）：将堆所有数据从新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
public static void HeapSort(int[] numbers) {for (int i = numbers.length - 1; i > 0; i--) {max_heapify(numbers, i);
// 堆顶元素 (第一个元素) 与 Kn 替换
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
}
}
/***
*
* 将数组堆化
* i = 第一个非叶子节点。* 从第一个非叶子节点开始即可。无需从最初一个叶子节点开始。* 叶子节点能够看作已合乎堆要求的节点，根节点就是它本人且本人以下值为最大。*
* @param a
* @param n
*/
public static void max_heapify(int[] a, int n) {
int child;
for (int i = (n - 1) / 2; i >= 0; i--) {
// 左子节点地位
child = 2 * i + 1;
// 右子节点存在且大于左子节点，child 变成右子节点
if (child != n && a[child] < a[child + 1]) {child++;}
// 替换父节点与左右子节点中的最大值
if (a[i] < a[child]) {int temp = a[i];
a[i] = a[child];
a[child] = temp;
}
}
}
// 调用
int[] n = {60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87};
System.out.println(Arrays.toString(n));
HeapSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
因为堆排序中初始化堆的过程比拟次数较多, 因而它不太实用于小序列。同时因为屡次任意下标相互交换地位, 雷同元素之间本来绝对的程序被毁坏了, 因而, 它是不稳固的排序。
八：归并排序
归并排序是建设在归并操作上的一种无效的排序算法，1945 年由约翰·冯·诺伊曼首次提出。该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用，且各层分治递归能够同时进行。
根本思维
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。而后再把有序子序列合并为整体有序序列
算法形容
归并排序可通过两种形式实现:
- 自上而下的递归
- 自下而上的迭代
递归法（假如序列共有 n 个元素）：
1. 将序列每相邻两个数字进行归并操作，造成 floor(n/2)个序列，排序后每个序列蕴含两个元素；
2. 将上述序列再次归并，造成 floor(n/4)个序列，每个序列蕴含四个元素；
3. 反复步骤 2，直到所有元素排序结束。
迭代法
1. 申请空间，使其大小为两个曾经排序序列之和，该空间用来寄存合并后的序列
2. 设定两个指针，最后地位别离为两个曾经排序序列的起始地位
3. 比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位
4. 反复步骤 3 直到某一指针达到序列尾
5. 将另一序列剩下的所有元素间接复制到合并序列尾
代码实现
归并排序其实要做两件事：
- 合成：将序列每次折半拆分
- 合并：将划分后的序列段两两排序合并
因而，归并排序实际上就是两个操作，拆分 + 合并
// 归并所需的辅助数组
private static int[] aux;
public static void MergeSort(int[] numbers) {
// 一次性调配空间
aux = new int[numbers.length];
sort(numbers, 0, numbers.length - 1);
}
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) {// 将 a[low..mid]和 a[mid+1..high]归并
int i = low, j = mid + 1;
for (int k = low; k <= high; k++) {aux[k] = a[k];
}
for (int k = low; k <= high; k++) {if (i > mid) {a[k] = aux[j++];
} else if (j > high) {a[k] = aux[i++];
} else if (aux[j] < aux[i]) {a[k] = aux[j++];
} else {a[k] = aux[i++];
}
}
}
应用
int[] n = {60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87};
System.out.println(Arrays.toString(n));
MergeSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假如数组长度为 n，那么拆分数组共需 logn，, 又每步都是一个一般的合并子数组的过程，工夫复杂度为 O(n)，故其综合工夫复杂度为 O(nlogn)。另一方面，归并排序屡次递归过程中拆分的子数组须要保留在内存空间，其空间复杂度为 O(n)。
九：基数排序
基数排序（Radix sort）是一种非比拟型整数排序算法，其原理是将整数按位数切割成不同的数字，而后按每个位数别离比拟。因为整数也能够表白字符串（比方名字或日期）和特定格局的浮点数，所以基数排序也不是只能应用于整数
根本思维
它是这样实现的：将所有待比拟数值（正整数）对立为同样的数位长度，数位较短的数后面补零。而后，从最低位开始，顺次进行一次排序。这样从最低位排序始终到最高位排序实现当前，数列就变成一个有序序列。
基数排序依照优先从高位或低位来排序有两种实现计划：
- MSD（Most significant digital）从最左侧高位开始进行排序。先按 k1 排序分组, 同一组中记录, 关键码 k1 相等, 再对各组按 k2 排序分成子组, 之后, 对前面的关键码持续这样的排序分组, 直到按最次位关键码 kd 对各子组排序后. 再将各组连接起来, 便失去一个有序序列。MSD 形式实用于位数多的序列。
- LSD（Least significant digital）从最右侧低位开始进行排序。先从 kd 开始排序，再对 kd- 1 进行排序，顺次反复，直到对 k1 排序后便失去一个有序序列。LSD 形式实用于位数少的序列。
算法形容
咱们以 LSD 为例，从最低位开始，具体算法形容如下：
1. 获得数组中的最大数，并获得位数；
2.arr 为原始数组，从最低位开始取每个位组成 radix 数组；
3. 对 radix 进行计数排序（利用计数排序实用于小范畴数的特点）；
代码实现
基数排序：通过序列中各个元素的值，对排序的 N 个元素进行若干趟的“调配”与“收集”来实现排序。
调配 ：咱们将 L[i] 中的元素取出，首先确定其个位上的数字，依据该数字调配到与之序号雷同的桶中
收集 ：当序列中所有的元素都调配到对应的桶中，再依照程序顺次将桶中的元素收集造成新的一个待排序列 L[]。对新造成的序列 L[] 反复执行调配和收集元素中的十位、百位 … 直到调配完该序列中的最高位，则排序完结
public static void RadixSort(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;
}
}应用
int[] n = {60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87};
System.out.println(Arrays.toString(n));
RadixSort(n);
System.out.println(Arrays.toString(n));
// 后果
System.out: [60, 38, 5, 14, 7, 23, 89, 77, 88, 4, 35, 45, 67, 99, 87]
System.out: Sorting: [60, 23, 14, 4, 5, 35, 45, 7, 77, 67, 87, 38, 88, 89, 99]
System.out: Sorting: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
System.out: [4, 5, 7, 14, 23, 35, 38, 45, 60, 67, 77, 87, 88, 89, 99]
其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比拟操作，所以在简单上，最好的状况与最坏的状况在工夫上是统一的，均为 O(d*(n + r))。
结尾：人的常识是有局限的
