概述
排序是程序开发中一种非常常见的操作，指对一组任意的数据元素（或记录）经过排序操作后，将它们变成一组按关键字排序的有序序列。
一旦将一组杂乱无章的记录重排成一组有序记录，就能快速地从这组记录中找到目标记录。
衡量排序算法（sorting algorithm）优劣的三个方面：
- 时间复杂度：主要分析关键字的比较次数和记录的移动次数
- 空间复杂度：分析排序算法中需要多少辅助内存
- 稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的；反之就是不稳定的。
分类：
-
内部排序（整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成）
分类：
- 选择排序
- 交换排序
- 插入排序
- 归并排序
- 桶式排序
- 基数排序
内部排序一览.JPG
-
外部排序（参与排序的数据元素非常多，数据量非常大，计算机排序时必须借助于外部存储器）
常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别将每一部分调入内存完成排序，接下来再对多个有序的子文件进行归并排序。
具体步骤：
- 把两个文件中的一组记录读入内存的排序区，对读入的记录按上面讲到的内部排序法进行排序，排序之后输出到外部存储器。不断重复这一过程，每次读取一组记录，直到源文件的所有记录被处理完毕。
- 将上一步分组排序好的记录两组两组的合并排序。在内存容量允许的情况下，每组中包含的记录越大越好，以减少合并次数。
[选择排序法]
-
直接选择排序
该排序算法思路简单，需要经过n-1趟比较。
第1趟：程序将记录定位在第一个数据上，拿第1个数据依次和它后面的每一个数据进行比较，如果第1个数据大于后面某个数据，就交换它们......，以此类推。经过第1趟比较，这组数据中最小的数据被选出，被排在第1位。
第2趟：程序将记录定位在第二个数据上，拿第2个数据依次和它后面的每一个数据进行比较，如果第2个数据大于后面某个数据，就交换它们......，以此类推。经过第2趟比较，这组数据中第二小的数据被选出，被排在第2位。
......
从上面描述可知，直接选择排序算法的关键就是n-1趟比较，每趟比较的目的就是选出本趟比较中最小的数据，并将该数据放在本趟比较的第1位。
示例代码：
package com.atschool; import java.util.Arrays; class DataWrap implements Comparable<DataWrap>{ int data; String flag; public DataWrap(int data,String flag){ this.data = data; this.flag = flag; } @Override public String toString() { return data + flag; } @Override public int compareTo(DataWrap o) { return this.data > o.data ? 1 : (this.data == o.data ? 0 : -1); } } public class SelectSort { public static void selectSort(DataWrap[] dataWraps){ System.out.println("开始排序"); int arrayLen = dataWraps.length; for (int i = 0; i < arrayLen - 1; i++) { int minIndex = i; for (int j = i + 1; j < arrayLen; j++) { if (dataWraps[minIndex].compareTo(dataWraps[j]) > 0){ minIndex = j; } } if (minIndex != i){ DataWrap tmp = dataWraps[i]; dataWraps[i] = dataWraps[minIndex]; dataWraps[minIndex] =tmp; } System.out.println(Arrays.toString(dataWraps)); } } public static void main(String[] args) { DataWrap[] dataWraps = { new DataWrap(21,""), new DataWrap(30,""), new DataWrap(49,""), new DataWrap(30,""), new DataWrap(16,""), new DataWrap(9,""), new DataWrap(10,""), new DataWrap(3,"") }; System.out.println("排序之前：\n" + Arrays.toString(dataWraps)); selectSort(dataWraps); System.out.println("排序之后：\n" + Arrays.toString(dataWraps)); } }直接选择排序算法：
时间复杂度： O(n * n)
空间复杂度： O(1)
稳定性： 不稳定
-
堆排序
概念：
假设有N个数据元素的序列k0,k1,......,kn-1,当且仅当满足如下关系时，可以将这组数据称为小顶堆（小根堆），将满足小顶堆的数据序列顺序排成一颗完全二叉树，则此树所有节点的值都小于其左右子节点的值。此数的根节点的值必定最小。
ki <= k2i + 1 且 ki <= k2i + 2（其中i=0,2,......,(n-1)/2）或者，满足如下关系时，可以将这组数据称为大顶堆（大根堆），将满足大顶堆的数据序列顺序排成一颗完全二叉树，则此树所有节点的值都大于其左右子节点的值。此数的根节点的值必定最大。
ki >= k2i + 1 且 ki >= k2i + 2（其中i=0,2,......,(n-1)/2）堆排序算法的思路：
- 建堆
- 先将要排序的数组转换为完全二叉树。
- 从完全二叉树的最后一个非叶子节点开始，保证该节点的值大于等于其左、右子节点的值。如果其子节点的值大于它本身的值，则把它和较大的子节点进行交换。最后一个节点的索引为数组长度-1，即
len-1，则最后一个非叶子节点的索引应该为(len-2)/2。 - 向前处理前一个非叶子节点（索引为
(len-2) / 2 - 1）。 - 向前处理前一个非叶子节点，若某个节点和它的某个子节点交换后，该子节点又有子节点，那么系统还需要再次对该子节点进行判断。
- 拿堆的根节点和最后一个节点交换
示例代码：
package com.atschool; import com.atschool.domain.DataWrap; import java.util.Arrays; public class HeapSort { public static void heapSort(DataWrap[] dataWraps) { System.out.println("开始排序"); int arrayLen = dataWraps.length; for (int i = 0; i < arrayLen - 1; i++) { buildMaxdHeap(dataWraps,arrayLen - 1 - i); swap(dataWraps,0,arrayLen - 1 - i); System.out.println(Arrays.toString(dataWraps)); } } private static void swap(DataWrap[] dataWraps, int initialIndex, int newIndex) { DataWrap tmp = dataWraps[initialIndex]; dataWraps[initialIndex] = dataWraps[newIndex]; dataWraps[newIndex] = tmp; } private static void buildMaxdHeap(DataWrap[] dataWraps, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0 ; i--) { // 保存当前正在判断的节点 int k = i; while (k * 2 + 1 <= lastIndex){ int biggerIndex = 2 * k + 1; if (biggerIndex < lastIndex){ if (dataWraps[biggerIndex].compareTo(dataWraps[biggerIndex + 1]) < 0){ biggerIndex++; } } if (dataWraps[k].compareTo(dataWraps[biggerIndex]) < 0){ swap(dataWraps,k,biggerIndex); k = biggerIndex; }else { break; } } } } public static void main(String[] args) { DataWrap[] dataWraps = { new DataWrap(21,""), new DataWrap(30,""), new DataWrap(49,""), new DataWrap(30,""), new DataWrap(45,""), new DataWrap(12,""), new DataWrap(33,""), new DataWrap(21,""), new DataWrap(16,""), new DataWrap(9,""), }; System.out.println("排序之前：\n" + Arrays.toString(dataWraps)); heapSort(dataWraps); System.out.println("排序之后：\n" + Arrays.toString(dataWraps)); } }对于堆排序算法来说，假设有n个数据，需要进行n-1次建堆，每次建堆本身耗时为log2<span style="font-size:1.5rem">n</span>，并且需要一个附加程序单元用于交换。因此：
时间复杂度：O(n * log2n)
空间复杂度：O(1)
稳定性： 不稳定
- 建堆
[交换排序法]
交换排序的主体操作是对数据组中的数据不断地进行交换操作。交换操作主要有冒泡排序和快速排序。
-
冒泡排序
冒泡排序是最广为人知的交换排序之一，具有算法思路简单、容易实现的特点。
冒泡排序的执行步骤并不固定。假设对包含n个数据的一组记录进行排序，在最坏的情况下，需要进行n-1趟比较：
- 依次比较0和1、1和2、2和3、......、n-2和n-1索引处的元素，如果发现第一个数据大于后一个数据，则交换它们。经过第一趟比较，最大的元素排到了最后。
- 依次比较0和1、1和2、2和3、......、n-3和n-2索引处的元素，如果发现第一个数据大于后一个数据，则交换它们。经过第二趟比较，第二大的元素排到了倒数第2位。
- ......
- 第n-1趟依次比较0和1索引处的元素，如果发现第一个数据大于后一个数据，则交换它们。经过第n-1趟比较，第2小（第n-1）大的元素排到了第二位。
实际上，冒泡排序的每趟交换结束后，不仅能将当前最大值挤出最后面位置，还能部分理顺前面的其他元素；一旦某趟没有交换发生，即可提前结束排序。
示例代码：
package com.atschool; import com.atschool.domain.DataWrap; import java.util.Arrays; public class BubbleSort { public static void bubbleSort(DataWrap[] dataWraps){ System.out.println("开始排序"); int arrayLen = dataWraps.length; for (int i = 0; i < arrayLen - 1; i++) { boolean flag = false; for (int j = 0; j < arrayLen - 1 - i; j++) { if (dataWraps[j].compareTo(dataWraps[j + 1]) > 0){ DataWrap tmp = dataWraps[j + 1]; dataWraps[j + 1] = dataWraps[j]; dataWraps[j] = tmp; flag = true; } } System.out.println(Arrays.toString(dataWraps)); if (!flag){ break; } } } public static void main(String[] args) { DataWrap[] dataWraps = { new DataWrap(9,""), new DataWrap(16,""), new DataWrap(21,""), new DataWrap(23,""), new DataWrap(30,""), new DataWrap(49,""), new DataWrap(21,""), new DataWrap(30,"") }; System.out.println("排序之前：\n" + Arrays.toString(dataWraps)); bubbleSort(dataWraps); System.out.println("排序之后：\n" + Arrays.toString(dataWraps)); } }冒泡排序算法的时间效率是不确定的：
- 在最好的情况下：初始数据序列已经处于有序状态，执行1趟冒泡即可，做n-1次比较，无须任何交换。
- 在最坏的情况下：初始数据序列处于完全逆序状态，算法要执行n-1趟冒泡，第i趟做了n-i次比较，执行n-i-1次对象交换。此时的比较总次数为n * (n -1) / 2，记录移动总次数为n * (n - 1) * 3 / 2。
时间复杂度： 不确定
空间复杂度： O(1)
稳定性： 稳定
-
快速排序
总体步骤：
- 选出指定的分界的值
- 将所有比分界值小的数据元素放在左边
- 将所有比分界值大的数据元素放在右边
第2、3步具体步骤：
- 定义一个i变量，i变量从左边第一个索引开始，找大于分界值的元素的索引，并用i来记录它。
- 定义一个j变量，j变量从右边第一个索引开始，找小于分界值的元素的索引，并用j来记录它。
- 如果i < j，则交换i、j两个索引处的元素。
重复执行以上1~3步，直到i >= j，可以判断j左边的数据元素都小于分界值，j右边的数据元素都大于分界值，最后将分界值和j索引处的元素交换即可。
示例代码：
package com.atschool.algothrim; import com.atschool.domain.DataWrap; import java.util.Arrays; /** * @ClassName QuickSort * @Description TODO * @Author zhang * @Date 2020/10/2 15:16 * @Version 1.0 */ public class QuickSort { private static void swap(DataWrap[] dataWraps, int i, int j){ DataWrap tmp = dataWraps[i]; dataWraps[i] = dataWraps[j]; dataWraps[j] = tmp; } private static void subSort(DataWrap[] dataWraps, int start, int end){ if (start < end){ DataWrap base = dataWraps[start]; int i = start; int j = end + 1; while (true){ while(i < end && dataWraps[++i].compareTo(base) <= 0); while(j > start && dataWraps[--j].compareTo(base) >= 0); if (i < j){ swap(dataWraps,i,j); }else { break; } } swap(dataWraps,start,j); subSort(dataWraps,start,j - 1); subSort(dataWraps, j + 1, end); } } public static void quickSort(DataWrap[] dataWraps){ subSort(dataWraps,0,dataWraps.length - 1); } public static void main(String[] args) { DataWrap[] dataWraps = { new DataWrap(9,""), new DataWrap(-16,""), new DataWrap(21,""), new DataWrap(23,""), new DataWrap(-30,""), new DataWrap(-49,""), new DataWrap(21,""), new DataWrap(30,""), new DataWrap(13,""), }; System.out.println("排序之前：\n" + Arrays.toString(dataWraps)); quickSort(dataWraps); System.out.println("排序之后：\n" + Arrays.toString(dataWraps)); } }
时间复杂度： 较好
空间复杂度： O(log2n)
稳定性： 包含跳跃式交换，不稳定
[插入排序法]
-
直接插入排序
思路：
依次将待排序的数据元素按其关键字值的大小插入前面的有序序列。
具体步骤：（假设有一个拥有n个元素的数据序列，排序需要进行n-1趟插入操作）
将第2个元素插入前面的有序子序列中，此时前面只有一个元素，当然是有序的
将第3个元素插入前面的有序子序列中，前面两个元素是有序的
-
......
n-1. 将第n个元素插入前面的有序子序列中，前面n-1个元素是有序的。
示例代码：
package com.atschool; import com.atschool.domain.DataWrap; import java.util.Arrays; public class InsertSort { public static void insertSort(DataWrap[] dataWraps){ System.out.println("开始排序："); int arrayLen = dataWraps.length; for (int i = 1; i < arrayLen; i++) { DataWrap tmp = dataWraps[i]; if (dataWraps[i].compareTo(dataWraps[i - 1]) < 0){ int j = i - 1; for (; j >= 0 && dataWraps[j].compareTo(tmp) > 0 ; j--) { dataWraps[j+1] = dataWraps[j]; } dataWraps[j + 1] = tmp; } System.out.println(Arrays.toString(dataWraps)); } } public static void main(String[] args) { DataWrap[] dataWraps = { new DataWrap(9,""), new DataWrap(-16,""), new DataWrap(21,""), new DataWrap(23,""), new DataWrap(-30,""), new DataWrap(-49,""), new DataWrap(21,""), new DataWrap(30,""), new DataWrap(30,"") }; System.out.println("排序之前：\n" + Arrays.toString(dataWraps)); insertSort(dataWraps); System.out.println("排序之后：\n" + Arrays.toString(dataWraps)); } }
时间复杂度： O(n * n)
空间复杂度： O(1)
稳定性： 稳定
-
折半插入排序
是对直接插入排序的简单改进。对于直接插入排序而言，当第i-1趟需要将第i个元素插入前面的0~i-1个元素的序列中时，它总是从i-1个元素开始，逐个比较每个元素，直到找到它的位置。
排序思路：
当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时，它不会直接从i-1个元素开始逐个比较每个元素。而是：
计算0~i-1索引的中间点，也就是用i索引处的元素和(0 + i - 1)/2索引处的元素进行比较，如果i索引处的元素大，就直接在(0+i-1) / 2 ~ i-1半个范围内搜索；反之，就在0 ~ (0 + i -1)/2半个范围内搜索，这就是所谓的折半
-
在半个范围内搜索时，再按第1步方法进行折半搜索。
总是不断折半，这样就可以将搜索范围缩小到1/2、1/4、1/8。从而快速确定第i个元素的插入位置
一旦确定了第i个元素的插入位置，程序将该位置以后的元素整体后移一位，然后将第i个元素放入该位置
排序效果和直接插入基本相同，不过速度更快一些。
示例代码：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] dataWraps){
System.out.println("开始排序：\n");
int arrayLen = dataWraps.length;
for (int i = 1; i < arrayLen; i++) {
DataWrap tmp = dataWraps[i];
int low = 0;
int high = i -1;
while (low <= high){
int mid = (low + high) / 2;
if (tmp.compareTo(dataWraps[mid]) > 0){
low = mid + 1;
}else {
high = mid -1;
}
}
for (int j = i; j > low; j--) {
dataWraps[j] = dataWraps[j-1];
}
dataWraps[low] = tmp;
System.out.println(Arrays.toString(dataWraps));
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,""),
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
binaryInsertSort(dataWraps);
System.out.println("排序之后：\n" + Arrays.toString(dataWraps));
}
}
时间复杂度： O(n * n)
空间复杂度： O(1)
稳定性： 稳定
- Shell排序
基本思路：
通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动。这些数据项排过一趟序后，Shell排序算法减少数据项的间隔再进行排序，依次进行下去。这些进行排序的数据项之间的间隔被称为增量，习惯上用h来表示这个增量。
例如：
假设有一个包含9项数据的序列，当h增量为4时，第1趟将保证索引为0、4、8的数据元素已经有序。第1趟完成后，算法向右移一步，对索引为1、5的数据元素进行排序。这个排序过程持续进行，直到所有的数据项都已经完成了以4为增量的排序。即，所有间隔为4的数据项之间都已经排列有序。接下来应该减少增量，直到完成以1为增量的shell排序，此时数据序列将会变为有序序列。
特点：
- 完成某个增量的排序后，相关元素达到基本有序的状态
- 通过创建交错的内部有序的数据项集合，减少直接插入排序中数据项“整体搬家”的工作量
从上面描述可知：
最终确定Shell排序算法的关键就在于确定h序列的值。常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h = 3 * h + 1
比直接插入排序更高效的原因：
- 当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长
- 当h减小时，每一趟排序需要移动的元素的个数增多，但此时数据项已经接近于它们排序后最终的位置，数据项移动的距离短。
直接插入排序是以1为增量的Shell排序
示例代码：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class ShellSort {
public static void shellSort(DataWrap[] dataWraps){
System.out.println("开始排序：");
int arrayLen = dataWraps.length;
int h = 1;
while (h <= arrayLen / 3){
h = h * 3 + 1;
}
while (h > 0){
System.out.println("=======h的值：" + h + "======");
for (int i = h; i < arrayLen; i++) {
DataWrap tmp = dataWraps[i];
if (dataWraps[i].compareTo(dataWraps[i - h]) < 0){
int j = i - h;
for (; j >= 0 && dataWraps[j].compareTo(tmp) > 0 ; j-= h) {
dataWraps[j + h] = dataWraps[j];
}
dataWraps[j + h] = tmp;
}
System.out.println(Arrays.toString(dataWraps));
}
h = (h - 1) / 3;
}
}
public static void main(String[] args) {
DataWrap[] dataWrap = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWrap));
shellSort(dataWrap);
System.out.println("排序之后：\n" + Arrays.toString(dataWrap));
}
}
时间复杂度： O(n3/2) ~ O(n7/6)
空间复杂度： O(1)
稳定性： 稳定
[归并排序法]
思路：
将两个（或以上）有序的序列合并成一个新的有序序列。
大概步骤：
先将程度为n的无序序列看成是n个长度为1的有序子序列，首先做到两两合并，得到n/2个长度为2的有序子序列，再做两两合并......，不断地重复这个过程，最终可以得到一个长度为n的有序序列。也就是说，对于长度为n的数据序列，只需经过log2n次合并。
具体步骤：
定义变量i，i从0开始，依次等于A序列中每个元素的索引
定义变量j，j从0开始，依次等于B序列中每个元素的索引
拿A序列中i索引处的元素和B序列中j索引处的元素进行比较，将较小的复制到一个临时数组
-
如果i索引处的元素小，则i++；如果j索引处的元素小，则j++
不断地重复上面四个步骤，即可将A、B两个序列中的数据元素复制到临时数组中，直到其中一个数组中的所有元素都被复制到临时数组中。最后将另一个数组中剩余的元素全部复制到临时数组中，合并即完成，再将临时数组中的数据复制回去即可。
示例代码：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(DataWrap[] dataWraps) {
sort(dataWraps,0,dataWraps.length - 1);
}
private static void sort(DataWrap[] dataWraps, int left,int right){
if (left < right){
int center = (left + right) / 2;
sort(dataWraps,left,center);
sort(dataWraps,center + 1, right);
merge(dataWraps,left,center,right);
}
}
private static void merge(DataWrap[] dataWraps, int left, int center, int right) {
DataWrap[] tmpArr = new DataWrap[dataWraps.length];
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right){
if (dataWraps[left].compareTo(dataWraps[mid]) <= 0){
tmpArr[third++] = dataWraps[left++];
}else {
tmpArr[third++] = dataWraps[mid++];
}
}
while(mid <= right){
tmpArr[third++] = dataWraps[mid++];
}
while (left <= center){
tmpArr[third++] = dataWraps[left++];
}
//将中间数组中的内容复制回原数组
while (tmp <= right){
dataWraps[tmp] = tmpArr[tmp++];
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(-16,""),
new DataWrap(21,""),
new DataWrap(23,""),
new DataWrap(-30,""),
new DataWrap(-49,""),
new DataWrap(21,""),
new DataWrap(30,""),
new DataWrap(30,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
mergeSort(dataWraps);
System.out.println("排序之后：\n" + Arrays.toString(dataWraps));
}
}
时间复杂度： O(n * log2n)
空间复杂度： 较高
稳定性： 稳定
[桶式排序法]
该排序法不再是基于比较的排序方法，排序方式非常巧妙，需要待排序序列满足如下两个特征：
- 待排序序列的所有值处于一个可枚举范围内
- 待排序序列所在的这个可枚举范围不应该太大，否则排序开销太大
假设有如下待排序序列：
5, 4, 2, 4, 1
这个待排序序列处于0, 1, 2, 3, 4, 5这个可枚举范围内，而且这个范围很小，可使用桶式排序：
具体步骤：
对这个可枚举范围构建一个buckets数组，用于记录“落入”每个桶中的元素的个数
-
按如下公式对上述buckets数组的元素进行重新计算
buckets[i] = buckets[i] + buckets[i-1] (1 <= i <= buckets.length)
示例代码：
package com.atschool;
import com.atschool.domain.DataWrap;
import java.util.Arrays;
public class BucketSort {
public static void bucketSort(DataWrap[] dataWraps, int min, int max){
System.out.println("开始排序：");
int arrayLen = dataWraps.length;
DataWrap[] tmp = new DataWrap[arrayLen];
int[] buckets = new int[max - min];
for (int i = 0; i < arrayLen; i++) {
buckets[dataWraps[i].data - min]++;
}
System.out.println(Arrays.toString(buckets));
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
System.out.println(Arrays.toString(buckets));
System.arraycopy(dataWraps,0,tmp,0,arrayLen);
//根据buckets数组中的信息将待排序序列的各元素放入相应的位置
for (int k = arrayLen - 1; k >= 0 ; k--) {
dataWraps[--buckets[tmp[k].data - min]] = tmp[k];
}
}
public static void main(String[] args) {
DataWrap[] dataWraps = {
new DataWrap(9,""),
new DataWrap(5,""),
new DataWrap(-1,""),
new DataWrap(8,""),
new DataWrap(5,""),
new DataWrap(7,""),
new DataWrap(3,""),
new DataWrap(-3,""),
new DataWrap(1,""),
new DataWrap(3,"")
};
System.out.println("排序之前：\n" + Arrays.toString(dataWraps));
bucketSort(dataWraps, -3, 10);
System.out.println("排序之后：\n" + Arrays.toString(dataWraps));
}
}
时间复杂度： 极低
空间复杂度： 较高
稳定性： 稳定
[基数排序法]
基数排序必须依赖于另外的排序方法。
总体思路：
将待排序数据里的排序关键字拆分成多个排序关键字进行排序，然后，根据子关键字对待排数据进行排序。
两种解决方案：
- 最高位优先法MSD（Most Significant Digit first）
- 最低位优先法LSD（Least Significant Digit first）
例如，对如下数据序列进行排序：
192, 221, 13, 23
该序列中，每个数据至多有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。
使用基数排序法时，计算机会优先选择最地位优先法，如下所示：
第1轮对个位关键字排序：
221, 192, 12, 23第2轮对十位关键字排序：
13, 23, 221, 192第3轮对百位关键字排序：
13, 23, 192, 221
要求：
- 对任一子关键字排序需要借助另一种排序方法
- 上述排序方法必须是稳定的
因此桶式排序算法最合适。
示例代码：
package com.atschool;
import java.util.Arrays;
public class MultiKeyRadixSort {
public static void radixSort(int[] data, int radix, int d){
System.out.println("开始排序：");
int arrayLen = data.length;
int[] tmp = new int[arrayLen];
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
Arrays.fill(buckets,0);
System.arraycopy(data, 0 ,tmp, 0, arrayLen);
for (int j = 0; j < arrayLen; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
for (int m = arrayLen - 1; m >= 0 ; m--) {
int subKey = (tmp[m] / rate) % radix;
data[--buckets[subKey]] = tmp[m];
}
System.out.println("对" + rate + "位上子关键字排序：" + Arrays.toString(data));
rate *= radix;
}
}
public static void main(String[] args) {
int[] data = {1100,192,221,12,13};
System.out.println("排序之前：\n" + Arrays.toString(data));
radixSort(data,10,4);
System.out.println("排序之后：\n" + Arrays.toString(data));
}
}
