13518219792
本篇内容主要讲解“常用排序算法以及怎么用Java实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“常用排序算法以及怎么用Java实现”吧!
成都创新互联专业提供雅安电信机房服务，为用户提供五星数据中心、电信、双线接入解决方案，用户可自行在线购买雅安电信机房服务，并享受7*24小时金牌售后服务。
插入排序是往有序的数组中快速插入一个新的元素。把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的。（注：插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序…）
①. 从第一个元素开始，该元素可以认为已经被排序
②. 取出下一个元素，在已经排序的元素序列中从后向前扫描
③. 如果该元素（已排序）大于新元素，将该元素移到下一位置
④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤. 将新元素插入到该位置后
⑥. 重复步骤②~⑤
如图（1-1）所示：
（图：1-1）
/**
* 插入排序
*
* 1. 从第一个元素开始，该元素可以认为已经被排序
* 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 5. 将新元素插入到该位置后
* 6. 重复步骤2~5
* @param arr 待排序数组
*/
public static void insertionSort(int[] arr){
for( int i=0; i0; j-- ) {
if( arr[j-1] <= arr[j] )
break;
int temp = arr[j]; //交换操作
arr[j] = arr[j-1];
arr[j-1] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
} 注意：
如果 比较操作 的代价比 交换操作 大的话，可以采用二分查找法来减少 比较操作 的数目。该算法可以认为是 插入排序 的一个变种，称为二分查找插入排序。
复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
总结：
由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。
插入排序所需的时间取决于输入元素的初始顺序，这样数组有序或接近有序，更适合插入排序。
希尔排序，也称 递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是 非稳定排序算。
操作如下：
将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 2. 按增量序列个数 k，对序列进行 k 趟排序； 3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
如图（2-1）所示：
图（2-1）
/**
* 希尔排序（Wiki官方版）
*
* 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（注意此算法的gap取值）
* 2. 按增量序列个数k，对序列进行k 趟排序；
* 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param arr 待排序数组
*/
public static void shell_sort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3)
gap = gap * 3 + 1; // : 1, 4, 13, 40, 121, ...
for (; gap > 0; gap /= 3) {
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
} 复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog2 n) | O(nlog2 n) | O(nlog2 n) | O(1) |
总结：
选择合理的步长很重要，更好的步长序列取值可以参考维基百科。
排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。
希尔排序与插入排序对如下：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动。
希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
1. 从未排序序列中，找到关键字最小的元素 2. 如果最小元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换 3. 重复1、2步，直到排序结束。
如图（3-1）所示：
图（3-1）
/**
* 选择排序
*
* 1. 从待排序序列中，找到关键字最小的元素；
* 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
* 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束。
* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
* @param arr 待排序数组
*/
public static void selectionSort(int[] arr){
for(int i = 0; i < arr.length-1; i++){
int min = i;
for(int j = i+1; j < arr.length; j++){ //选出之后待排序中值最小的位置
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i){
int temp = arr[min]; //交换操作
arr[min] = arr[i];
arr[i] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
}复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) |
总结：
选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n²/2次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。
堆：n个元素的序列{k1,k2,···,kn}，当且仅当满足下关系时，称之为堆。ki <= k(2i) 且 ki <= k(2i+1)或： ki >= k(2i) 且 ki >= k(2i+1)
把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排序, 使用小顶堆进行降序排序。
先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.
再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1…n-1]和有序区K[n], 且满足K[1…n-1].keys <= K[n].key
交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1…n-1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
如图（4-1）所示：
图（4-1）
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数，二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。
总结起来就是定义了以下几种操作：
最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
对于堆节点的访问：
父节点i的左子节点在位置：(2*i+1); 父节点i的右子节点在位置：(2*i+2); 子节点i的父节点在位置：floor((i-1)/2);
/**
* 堆排序
*
* 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]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.
* @param arr 待排序数组
*/
public static void heapSort(int[] arr){
for(int i = arr.length; i > 0; i--){
max_heapify(arr, i);
int temp = arr[0]; //堆顶元素(第一个元素)与Kn交换
arr[0] = arr[i-1];
arr[i-1] = temp;
}
}
private static void max_heapify(int[] arr, int limit){
if(arr.length <= 0 || arr.length < limit) return;
int parentIdx = limit / 2;
for(; parentIdx >= 0; parentIdx--){
if(parentIdx * 2 >= limit){
continue;
}
int left = parentIdx * 2; //左子节点位置
int right = (left + 1) >= limit ? left : (left + 1); //右子节点位置，如果没有右节点，默认为左节点位置
int maxChildId = arr[left] >= arr[right] ? left : right;
if(arr[maxChildId] > arr[parentIdx]){ //交换父节点与左右子节点中的最大值
int temp = arr[parentIdx];
arr[parentIdx] = arr[maxChildId];
arr[maxChildId] = temp;
}
}
System.out.println("Max_Heapify: " + Arrays.toString(arr));
}复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) |
总结：
1. 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n); 2. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn); 3. 堆排序的过程由n次第2步完成, 时间复杂度为O(nlgn).
总结：由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3. 针对所有的元素重复以上的步骤，除了最后一个。 4. 持续每次对越来越少的元素重复上面的1-3步骤，直到没有任何一对数字需要比较。
如图（5-1） 所示：
图（5-1）
/**
* 冒泡排序
*
* 1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
* 3. 针对所有的元素重复以上的步骤，除了最后一个。
* 4. 持续每次对越来越少的元素重复上面的1-3步骤，直到没有任何一对数字需要比较。
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr){
for (int i = arr.length - 1; i > 0; i--) { //外层循环移动游标
for(int j = 0; j < i; j++){ //内层循环遍历游标及之后(或之前)的元素
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
System.out.println("Sorting: " + Arrays.toString(arr));
}
}
}
}复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(n²) | O(n) | O(n²) | O(1) |
总结：
冒泡排序是最容易实现的排序，最坏的情况是每次都需要交换， 共需遍历并交换将近n²/2次， 时间复杂度为O(n²)， 最佳的情况是内循环遍历一次后发现排序是对的，因此退出循环， 时间复杂度为O(n)。 平均来讲， 时间复杂度为O(n²) 由于冒泡排序中只有缓存的temp变量需要内存空间， 因此空间复杂度为常量O(1)。
由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
快速排序是在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：
从数列中挑出一个元素，称为"基准"（pivot）。
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
如图（6-1）所示：
图（6-1）
/**
* 快速排序（递归）
*
* ①. 从数列中挑出一个元素，称为"基准"（pivot）。
* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* @param arr 待排序数组
* @param low 左边界
* @param high 右边界
*/
public static void quickSort(int[] arr, int low, int high){
if(arr.length <= 0) return;
if(low >= high) return;
int left = low;
int right = high;
int temp = arr[left]; //挖坑1：保存基准的值
while (left < right){
while(left < right && arr[right] >= temp){ //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
right--;
}
arr[left] = arr[right];
while(left < right && arr[left] <= temp){ //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
left++;
}
arr[right] = arr[left];
}
arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
System.out.println("Sorting: " + Arrays.toString(arr));
quickSort(arr, low, left-1);
quickSort(arr, left+1, high);
}上面是递归版的快速排序：通过把基准temp插入到合适的位置来实现分治，并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢？
因为递归的本质是栈，所以我们非递归实现的过程中，可以借助栈来保存中间变量就可以实现非递归了。在这里中间变量也就是通过Pritation函数划分区间之后分成左右两部分的首尾指针，只需要保存这两部分的首尾指针即可。
/**
* 快速排序（非递归）
*
* ①. 从数列中挑出一个元素，称为"基准"（pivot）。
* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* ③. 把分区之后两个区间的边界（low和high）压入栈保存，并循环①、②步骤
* @param arr 待排序数组
*/
public static void quickSortByStack(int[] arr){
if(arr.length <= 0) return;
Stack stack = new Stack();
//初始状态的左右指针入栈
stack.push(0);
stack.push(arr.length - 1);
while(!stack.isEmpty()){
int high = stack.pop(); //出栈进行划分
int low = stack.pop();
int pivotIdx = partition(arr, low, high);
//保存中间变量
if(pivotIdx > low) {
stack.push(low);
stack.push(pivotIdx - 1);
}
if(pivotIdx < high && pivotIdx >= 0){
stack.push(pivotIdx + 1);
stack.push(high);
}
}
}
private static int partition(int[] arr, int low, int high){
if(arr.length <= 0) return -1;
if(low >= high) return -1;
int l = low;
int r = high;
int pivot = arr[l]; //挖坑1：保存基准的值
while(l < r){
while(l < r && arr[r] >= pivot){ //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
r--;
}
arr[l] = arr[r];
while(l < r && arr[l] <= pivot){ //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
l++;
}
arr[r] = arr[l];
}
arr[l] = pivot; //基准值填补到坑3中，准备分治递归快排
return l;
} 复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog₂n) | O(nlog₂n) | O(n²) | O(1)（原地分区递归版） |
总结：
1. 快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。 2. 快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
注：归并排序可通过两种方式实现（自上而下的递归，自下而上的迭代）
递归法（假设序列共有n个元素）：
将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
重复步骤2，直到所有元素排序完毕。
如图（7-1）所示：
图（7-1）
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
归并排序其实要做两件事：
分解：将序列每次折半拆分
合并：将划分后的序列段两两排序合并
因此，归并排序实际上就是两个操作，拆分+合并
/**
* 归并排序（递归）
*
* ①. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
* ②. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
* ③. 重复步骤②，直到所有元素排序完毕。
* @param arr 待排序数组
*/
public static int[] mergingSort(int[] arr){
if(arr.length <= 1) return arr;
int num = arr.length >> 1;
int[] leftArr = Arrays.copyOfRange(arr, 0, num);
int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr)); //不断拆分为最小单元，再排序合并
}
private static int[] mergeTwoArray(int[] arr1, int[] arr2){
int i = 0, j = 0, k = 0;
int[] result = new int[arr1.length + arr2.length]; //申请额外的空间存储合并之后的数组
while(i < arr1.length && j < arr2.length){ //选取两个序列中的较小值放入新数组
if(arr1[i] <= arr2[j]){
result[k++] = arr1[i++];
}else{
result[k++] = arr2[j++];
}
}
while(i < arr1.length){ //序列1中多余的元素移入新数组
result[k++] = arr1[i++];
}
while(j < arr2.length){ //序列2中多余的元素移入新数组
result[k++] = arr2[j++];
}
System.out.println("Merging: " + Arrays.toString(result));
return result;
}复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) |
总结：
从效率上看，归并排序可算是排序算法中的”佼佼者”. 假设数组长度为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方式适用于位数少的序列。
如图（8-1）所示：
图（8-1）
我们以LSD为例，从最低位开始，具体算法描述如下：
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中 收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[]。对新形成的序列L[]重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束
/**
* 基数排序（LSD 从低位开始）
*
* 基数排序适用于：
* (1)数据范围较小，建议在小于1000
* (2)每个数值都要大于等于0
*
* ①. 取得数组中的最大数，并取得位数；
* ②. arr为原始数组，从最低位开始取每个位组成radix数组；
* ③. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
* @param arr 待排序数组
*/
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;
}
System.out.println("maxDigit: " + maxDigit);
//申请一个桶空间
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;
}
}复杂分析如下：
| 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|
| O(d*(n+r)) | O(d*(n+r)) | O(d*(n+r)) | O(n+r) |
其中，d 为位数，r 为基数，n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r))。
总结：
基数排序更适合用于对时间, 字符串等这些 整体权值未知的数据 进行排序。
基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
到此，相信大家对“常用排序算法以及怎么用Java实现”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
