算法（二）排序算法
选泡插 快归希 桶计基 堆
快排上图中空间复杂度数据错误，应该是O(log2n)。
插入，堆，归并，快排
n表示数据规模，k表示桶的个数。
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
image.png
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
1.冒泡排序（BubbleSort）
算法核心
冒泡排序是最简单的算法之一，算法的核心是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。
image
最优最差情况
冒泡排序什么情况下最快？在输入的数据已经是有序时，在什么情况下最慢，当输入的数据是反序时。
算法关键
- i 循环只负责外层循环，比较的是 j 和 j+1 对应的大小。
- i 循环是从0开始，长度是length，j 循环是从0开始 长度是 length - 1 - i
- 交换发生在内层循环
public class BubbleSort {
public static void sort(int[] arr){
int length = arr.length ;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if( arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{6,2,22,45,1,6,8,200,56,111};
sort(arr);
System.out.println(Arrays.toString(arr));
}
复杂度
- 平均复杂度: O(n2)
- 最好情况复杂度: O(n)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(1)
- 排序方式: 内排序
- 稳定性: 稳定
2.选择排序（SelectionSort）
算法核心
每次从待排序的数据元素中选出最小（或最大）的元素放在待排序序列起始的位置。
选择排序
最优最差情况
选择排序什么情况下最快？在什么情况下最慢？无论任何数据进去都是O(n2)，所以数据规模越小越好。
算法关键
- 1.需要一个minIndex 记录待排序数据中心最小（最大）数据的索引
- 2.i循环从0开始，长度 length ，j循环从 i+1 开始 长度length
- 3.交换发生在外层循环
public class SelectionSort{
public void sort(int[] arr) {
int length = arr.length ;
for (int i = 0; i < length ; i++) {
int minIndex = i;
for (int j = i + 1; j <length ; j++) {
if(arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if(minIndex == i){
continue;
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] arr = new int[]{6,2,22,45,1,6,8,200,56,111};
new SelectionSort().sort(arr);
System.out.println(Arrays.toString(arr));
}
}
复杂度
- 平均复杂度: O(n2)
- 最好情况复杂度: O(n2)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(1)
- 排序方式: 内排序
- 稳定性: 不稳定
3.插入排序 （InsertionSort）
算法核心
将数据按照一定的顺序一个一个的插入到有序表中，最终得到的序列就是已经排好序的数据。
打过扑克牌的人都知道，每摸起一张牌，通常按牌的大小进行插入排序。
插入排序
最优最差情况
和冒泡排序一样。
插入排序什么情况下最快？在输入的数据已经是有序时，在什么情况下最慢，当输入的数据是反序时。
算法关键
- i 循环只负责外层循环，比较的是 j 和 j-1 对应的大小。
- i 循环是从0开始，长度是length，j 循环是从 i + 1 开始 长度是 j - 1 不越界即（j - 1 >= 0）
- 交换发生在外层循环
public class InsertionSort {
public void sort(int[] arr) {
int length = arr.length;
for (int i = 1; i < length ; i++) {
int j = i ;
int temp = arr[j];
for ( ;j >0 && arr[j - 1] > temp;j--) {
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arrInsertion = new int[]{6,2,22,45,1,6,8,200,56,111};
new InsertionSort().sort(arrInsertion);
System.out.println("选择排序结果"+Arrays.toString(arrInsertion));
}
复杂度
- 平均复杂度: O(n2)
- 最好情况复杂度: O(n)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(1)
- 排序方式: 内排序
- 稳定性: 稳定
折半插入排序
在原来插入排序的基础上，查询顺序表比较的时候使用折半查找，可以减少比较次数，提高排序效率。
public void halfSort(int[] arr){
int length = arr.length;
for (int i = 1; i < length ; i++) {
int high = i;
int temp = arr[i];
int low = 0;
while(low <= high) {
int index = (low + high)/2;
if(temp > arr[index]) {
low = index + 1;
}else {
high = index -1;
}
}
for (int j = i ; j > low ; j--) {
arr[j] = arr[j - 1];
}
arr[low] = temp;
}
}
成对插入排序
JDK中使用的成对插入排序，主要思想还是插入排序，只不过一次拿两个元素，先用其中一个较大的元素向前遍历插入，然后在用娇小的元素继续向前遍历插入，这样较小的元素不必再走一次较大元素走过的路。比传统的插入排序要快。
2路插入排序
具体思路为：另外设置一个同存储记录的数组大小相同的数组d，将无需表中第一个记录添加进d[0]的位置上，然后从无需表中第二个记录开始，同d[0]比较，如果该值比d[0]大，则添加到其右侧，反之添加到左侧。
在这里可将d数组理解成一个环状数组。
理解为环状数组
排好序的环状数组
最终在存储原数组时，从d[7]开始一次存储。
2路插入排序相比于插入排序，只是减少了移动记录的次数，没有根本上避免比较，所以时间复杂度依然是O(n2)
4.冒泡排序，选择排序，插入排序对比
- 1.三种排序都是内排序，空间复杂度都为O(1)
- 2.三种排序最差的时间复杂度都为O(2),平均的时间复杂度都为O(2)，冒泡和插入最好的情况都是O(n)
- 3.选择排序是不稳定排序，冒泡排序和插入排序是稳定排序。
- 4.选择排序的交换次数最少 最差情况下为n-1，冒泡排序和插入排序元素交换次数不管怎么优化都是一个固定值。比选择排序要多很多。
- 5.冒泡排序的数据交换要比插入排序移动复杂，冒泡排序需要三个赋值操作，插入排序只需要一个。
- 6.插入排序在数据查找上可优化的地方很多，折半插入、2路插入、成对插入。而冒泡优化空间并不大。
4.希尔排序（ShellSort）
希尔排序。又叫缩小增量排序。也是插入排序中的一种，但是希尔排序相对于插入算法，在效率上有很大的提升。
它与插入排序不同之处在于，他会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设置好间隔序列，也可以动态定义间隔序列。
算法核心
- 1.计算步长间隔值gap
- 2.将数组划分成这些子数组
- 3.对这些子数组分别按照插入排序思想进行排序
-
4.重复此过程，直到间隔为1，进行普通的插入排序
希尔排序
最优最差情况
希尔排序什么情况下最快？数据本身有序的情况下最快O(n) 在什么情况下最慢？序列中的值（尤其是相邻的值）互为倍数的情况。
虽然插入排序是稳定的，但是希尔排序在插入的时候是跳跃性插入的，有可能破坏稳定性。
希尔提出了增量序列 h1 ，h2 ，……，ht ，只要h1=1，任何增量序列都是可行的，使用希尔增量排序的时间复杂度为O(n^2)。
Hibbard提出了一个增量序列：2k-1，使用Hibbard增量排序的时间复杂度为O(n1.5)。
算法关键
- 1.总共使用了三次循环（也可以使用四次循环，逻辑更清晰，效果完全一样）
- 内部两次循环和插入排序的代码完全一样。只是内部插入排序是增量拆分后的多个逻辑段交替执行的
- 外部循环是为了控制gap，gap每次增量如果控制成2k-1 可以优化最差情况时间复杂度到O(n1.5)
插入排序会，希尔排序代码就简单多了，在外层嵌套了一个循环控制增量。
// 控制增量
for (int gap = size / 2 ; gap > 0 ; gap /= 2 ) {}
实现代码
public class ShellSort {
public void sort(int[] arr){
int size = arr.length ;
// 控制增量
for (int gap = size / 2 ; gap > 0 ; gap /= 2 ) {
// 注意：这里和动图演示的不一样，动图是分组执行，这里操作是多个分组交替执行
//（如果使用分组执行需要四次循环）
for (int i = gap; i < size; i++) {
int j = i ;
int temp =arr[j];
while(j>=gap && arr[j - gap] > temp){
arr[j] = arr[j - gap];
j-=gap;
}
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arrInsertion = new int[]{6,2,22,45,1,6,8,200,56,111};
new ShellSort().sort(arrInsertion);
System.out.println("希尔排序的结果"+Arrays.toString(arrInsertion));
}
复杂度
- 平均复杂度: O(nlog2n)
- 最好情况复杂度: O(n)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(1)
- 排序方式: 内排序
- 稳定性: 不稳定 --虽然插入排序是稳定的，但是希尔排序在插入的时候是跳跃性插入的，有可能破坏稳定性
5.快速排序（QuickSort）
快排是利用分治思想。
算法核心
选择一个基准pivot，piovt位置可以随机选择，一般选择第一个元素。选择完成后，将小于pivot的元素放在pivot左边，大于pivot的元素放在右边。接下来对pivot左右两侧的子序列分别递归进行快速排序。
image
最优最差情况
快速排序什么情况下最快？每次划分所选择的中间数恰好将当前序列等分，经过log2n趟划分，便可以得到长度为1的子表，这样整个算法的时间复杂度为O(nlog2n).
在什么情况下最慢？每次划分所选择的中间数恰好是当前序列中最大或最小的元素，那么每次划分所得的子表中一个为空表，另一子表的长度为原表长度-1 这样，长度为n的数据表需要经过n趟划分，使得时间复杂度为O(n2)。
另外，尽管快排只需要一个元素的辅助空间，但快排需要一个栈空间来实现递归。最好情况栈深为log2(n+1)， 最坏情况栈深为n 这样，快速排序空间复杂度为O(log2n)。
优化版本-双轴快速排序
找两个基准数 pivot 将数据移动 分为less区域，middle区域，more区域 less和middle起始位置在序列头部，more区域其实位置在序列尾部，整体的移动是向中间移动。交换到less区域，less索引向后移动，交换到more区域 more索引向前移动 。
JDK的快速排序采用的双轴快排。
算法关键
- 1.一共使用三次循环，可以合并成两次循环，也可以只使用一次循环 这里为了便于理解使用三次循环。
- 2.一共使用两次递归，也可以优化成使用一次（增加一个while循环）。
public class QuickSort {
public int partition(int[] arr,int left,int right){
int temp = arr[left];
int low = left;
while (left < right) {
//此处两个while可以合并成一个
while ( left < right && arr[right] >= temp) {
right--;
}
while (left < right && arr[left] <= temp) {
left++;
}
if(left < right) {
int current = arr[left];
arr[left] = arr[right];
arr[right] = current;
}
}
arr[low] = arr[left];
arr[left] = temp;
return left;
}
public void sort(int[] arr,int left,int right) {
if(left < right) {
int partition = partition(arr,left,right);
sort(arr,0,partition -1);
sort(arr,partition + 1,right);
}
}
public static void main(String[] args) {
int[] arrInsertion = new int[]{66666666,2,3322,43445,31,8,6,8,22200,564,111};
new QuickSort().sort(arrInsertion,0,arrInsertion.length - 1);
System.out.println("快速排序的结果"+ Arrays.toString(arrInsertion));
}
}
如果只使用一次循环，可以修改代码为
public int partition(int[] arr,int left,int right){
int pivot= left;
int index = pivot + 1;
for(int i = index;i <= right;i++) {
if(arr[i]<arr[pivot]) {
swap(arr,i,index);
index++;
}
}
swap(arr,pivot,index - 1);
return index - 1;
}
如果改成一次递归(不重要)， 其实这种编译器会自动优化，相比不优化时间几乎没有减少
public void sort(int[] arr,int left,int right) {
while(left < right) {
int partition = partition(arr,left,right);
sort(arr,left,partition - 1);
left = partition + 1;
}
}
另外交换操作可以使用异或，假如 a = 3 ，b =4 那么a、b交换可以
a = a ^ b;
b = a ^ b;
a = a ^ b;
再多说两个 求模运算 % 假设a =5 n = 4 那么a%n = 1 可以用&运算符替换 这样效率要比用%求余要高。
但是有一个要求，n必须为2的幂
a & (n -1) = 1
乘除2n 操作 可以替换为 假设a =5
a >> 1 等于 a /2
a >>> 1 等于无符号a/2
a << 5 等于 a * 2的5次方
右移位运算符>>，若操作的值为正，则在高位插入0；若值为负，则在高位插入1。
右移补零操作符>>>，无论正负，都在高位插入0。
此方法完美，推荐使用
复杂度
- 平均复杂度: O(nlog2n)
- 最好情况复杂度: O(nlog2n)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(log2n)
- 排序方式: 内排序
- 稳定性: 不稳定
快速的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
6.堆排序（HeapSort）
什么是堆？
- 一棵完全二叉树
-
任意父节点的值大于子结点（大顶堆）或任意父节点的值小于子结点（小顶堆）
image.png
-
堆排序是指利用堆的数据结构设计的一种排序算法。
算法核心
- 初始化堆 将初始顺序表转换为最大堆
- 将堆中根结点和最右子结点交换，并且移除最右子节点。
- 重新调整剩余顺序表数据为最大堆，递归执行。
最优最差情况
略
算法关键
- 初始化将顺序表转最大堆，找到最后一个需要headpify的节点 last表示最右叶子节点 即heapify = （last -1)/ 2 ,依次heapify()操作从heapify节点至根结点。
- heapify 操作中如果发生了交换，需要递归操作交换后的子节点，保证下层仍然构成大顶堆。
- 3.交换时，只将顺序表生成的最大堆头部数据和尾部数据交换。
- 最后在sort时，只需要循环交换大顶堆首尾并heapify并即可。
public class HeapSort implements Sort {
@Override
public void sort(int[] arr) {
int length = arr.length;
buildMaxHeap(arr);
for (int i = length - 1 ; i > 0 ; i--) {
swap(arr,0,i);
heapify(arr,0,i);
}
}
public void heapify(int arr[], int i, int n) {
int large = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[large] < arr[left]) {
large = left;
}
if (right < n && arr[large] < arr[right]) {
large = right;
}
if (large != i) {
swap(arr, i, large);
heapify(arr, large, n);
}
}
public void buildMaxHeap(int[] arr) {
int length = arr.length;
int last = length - 1;
int lastHeapify = (last - 1) / 2;
for (int i = lastHeapify; i >= 0; i--) {
heapify(arr, i, length);
}
}
public 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];
}
public static void main(String[] args) {
int[] arr = new int[]{3, 5, 6, 10, 11, 12, 13};
new HeapSort().sort(arr);
System.out.println(Arrays.toString(arr));
}
}
复杂度
- 平均复杂度: O(nlog2n)
- 最好情况复杂度: O(nlog2n)
- 最坏情况复杂度: O(nlog2n)
- 空间复杂度: O(1)
- 排序方式: 内排序
- 稳定性: 不稳定
7.归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法时采用分治法的一个非常典型的应用。将已有子序列合并，得到完全有序的序列，即先每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并。归并算法效率非常稳定。无论任何数据时间复杂度都是O(nlog2n).
算法核心
- 1.把长度为n的输入序列分成两个长度为n/2 的子序列。
- 2.对这两个子序列分别采用归并排序。
-
3.将两个子序列合并成一个最终的排序序列。
归并排序
最优最差情况
归并排序什么情况下最快？什么情况下最慢？无论任何数据进去都是O(nlog2n),效率非常稳定。适合数据量比较大的排序。稳定的代价是需要额外的空间。空间复杂度为O(n).
算法关键
- 整体排序需要两个方法 merge 和 mergeSort merge控制合并，mergeSort控制拆分。
- 2.递归在mergeSort方法中进行。merge合并方法只复杂把两个数组合并。
- 3.合并时要考虑四种情况。左数组越界，右数组越界，左小于右和左不小于右。
- 4.整体只需要在合并时产生的新数组进行一次循环。
- 5.递归时，merge(mergeSort(left),mergeSort(right)) ,合并控制外层递归，拆分控制内层递归。
- 6.length < 2 控制递归退出。
public class MergeSort implements Sort{
@Override
public void sort(int[] arr) {
mergeSort(arr);
}
public int[] mergeSort(int[] arr) {
int length = arr.length;
if(length < 2) {
return arr;
}
int mid = length / 2 ;
//取左不取右 此处每次复制出一个新的数组，空间不是最优。可以使用原数组下标检索。空间复杂度就变为O(n)
int[] left = Arrays.copyOfRange(arr,0,mid);
int[] right = Arrays.copyOfRange(arr,mid,length);
return merge(mergeSort(left),mergeSort(right));
}
public int[] merge(int[] left,int[] right){
int[] result = new int[left.length + right .length];
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i < result.length; i++) {
if(leftIndex >= left.length) {
result[i] = right[rightIndex++];
}else if(rightIndex >= right.length){
result[i] = left[leftIndex++];
}else if(left[leftIndex] > right[rightIndex]){
result[i] = right[rightIndex++];
}
else {
result[i] = left[leftIndex++];
}
}
return result;
}
public static void main(String[] args) {
int[] arrMerge = new int[]{66666666,2,3322,43445,31,8,6,8,22200,564,111};
System.out.println("归并排序后结果："+Arrays.toString(new MergeSort().mergeSort(arrMerge)));
}
复杂度
- 平均复杂度: O(nlog2n)
- 最好情况复杂度: O(nlog2n)
- 最坏情况复杂度: O(nlog2n)
- 空间复杂度: O(n)
- 排序方式: 内排序
- 稳定性: 稳定
快速排序、归并排序、堆排序区别以及如何选择
时间复杂度：平均都是O(nlog2n)，堆、归并和快排最优也是O(nlog2n),唯独快排最差是O(n2)，但是数据随机性可以消除这一影响。
空间复杂度：堆排是O(1)，快排是递归次数O(log2n),归并是额外空间+递归次数 简化为O(n)
稳定性：快排和堆排序不稳定，归并稳定
堆排序适合做优先队列 或者找出k个数中前n大的数（属于选择排序的一种，按顺序选出）
快排在数据量在百万级以下下的时候比归并和堆排序都要快。但是越来越大时，会超过归并排序和堆排序。总的来说 堆排序要慢于归并。
在数据量很小的情况下，插入排序速度会优于快排，并且插入排序优化空间比较大。
8.计数排序
计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序的过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素的最终位置。
是桶思想中的一种。
算法核心
- 1.根据代拍序列中最大元素和最小元素确定范围，已经count数组的初始容量。
- 2.遍历待排序序列，将每一个元素出现次数记录到count数组。
- 3.对额外数组进行计算，得到每一个元素的排序后的位置。
- 4.将待排序序列按照count数组的位置输出到结果数组上。
image
最优最差情况
计数排序什么情况下最快？最大值和最小值差值小 什么情况下最慢？ 最大值和最小值差值大
适用于序列中的量非常大，但是数组取值范围比较小。
算法关键
- 1.count数组的大小为max - min + 1 ，原序列中具体元素 对应count中下标关系：index = 原序列中的元素值 - min
- count[i] = count[i]+count[i-1] 将count数组累加，得到的新count数组中，对应下标index的值value，就是原序列该元素最后出现的位置，如果需要保证稳定性。对应index - 1 就是元素出现的起始位置。如果使用index -1 那么要考虑count数组0的位置，因为0不能再-1。
- 拿到count数组后，遍历原序列，根据count数组的位置 插入结果序列。
public class CountSort {
public int[] countSort(int[] arr){
// 找到最大值最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max,arr[i]);
min = Math.min(min,arr[i]);
}
return destArr(arr,initCountArr(arr,max,min),min);
}
public int[] initCountArr(int[] arr,int max,int min){
// count数组 长度为: max - min + 1
int[] count = new int[max - min + 1];
// 得到arr每一个数字出现次数的数组count
for (int i = 0; i < arr.length; i++) {
// arr元素对应的count数组下标为 arr[i] - min
count[arr[i] - min]++;
}
// 将count数组 i 和 i - 1 累加 这样count数组的每一个下标对应的值，就是该下标数字出现的最后位置
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i-1];
}
return count;
}
public int[] destArr(int[] arr,int[] count,int min){
int[] result = new int[arr.length];
//考虑到算法的稳定性 count数组对应下标的前一位是arr数组中对应数字的起始位置 所以用前一位的起始，如果有相同的就往后面排
//这里要考虑到count数组第0位的往前找下标越界的情况，所以第0位单独处理。
for (int i = 0,j = 0; i <arr.length; i++) {
if(arr[i] - min == 0) {
result[j] = arr[i];
j++;
}else {
result[count[arr[i] - min - 1]] = arr[i];
count[arr[i] - min - 1]++;
}
}
return result;
}
public static void main(String[] args) {
int[] arrInsertion = new int[]{66,2,2,41,45,31,66,6,8,21,15,30};
System.out.println("计数排序的结果"+ Arrays.toString(new CountSort().countSort(arrInsertion)));
}
复杂度
- 平均复杂度: O(n+k)
- 最好情况复杂度: O(n+k)
- 最坏情况复杂度: O(n+k)
- 空间复杂度: O(n+k)
- 排序方式: 内排序
- 稳定性: 稳定
9.桶排序
按阈值拆分桶。每个桶用分别排序
缺点：桶用什么数据结构去存储。如果按数组 由于可能存在分配不均匀。 每个数组的长度都要等于原序列长度。也可以使用arrayList 按需扩容。但是这样排序的时间会浪费在扩容上。如果使用链表，会在排序的时候很耗时。
不太重要 理解思想
算法核心
- 1.设置一个定量得数组当作桶。
- 2.遍历输入数据，并把每个数据放到对应的桶里去。
- 3.对每个不是空的桶进行排序。
- 4.从不是空的桶里把排好的数据拼接起来。
image.png
最优最差情况
桶排序什么情况下最快？当数据正好一对一完全分配到桶中，只需一次遍历就可以排好序列。时间复杂度O(n). 什么情况下最慢？当数据每次只分到一个桶中，时间复杂度为O(n2)
算法关键
具体过程不描述。就是简单的分桶操作，具体桶的内部是否需要再分桶或者是使用什么排序算法，根据具体业务场景。
复杂度
- 平均复杂度: O(n + k)
- 最好情况复杂度: O(n)
- 最坏情况复杂度: O(n2)
- 空间复杂度: O(n+k) 但实际上空间做到最好的话，就只能用链表，时间上就做不到最好。
- 排序方式: 内排序
- 稳定性: 稳定
10.基数排序
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序是一种多关键字排序。
算法核心
LSD：低位优先：多次循环的计数排序，可做数字排序（数字的最大长度较短效率高），相等长度的字符串排序。
- 1.确定序列中值的最大位数，用于确定需要几轮排序。
- 2.内部使用计数排序，对应count使用 0-9的范围。
MSD：高位优先：用递归来做。可做字符串排序。
- 1.首先判断待排序序列中最大位数，来判断需要求余的长度。
- 2.第一轮遍历序列中是否满足最大位数，不满足放入0桶，满足放入高位对应的桶。
- 3.对非0桶内的序列分别进行排序，可以继续分桶或者使用其他排序算法。
- 4.非0桶排好后将结果序列与0桶中的序列递归调用排序方法（进行下一位的排序）。直至0桶内为0或1
image
算法关键
MSD代码未列出。
public class RadixSort {
@Override
public void sort(String[] arr) {
}
/** LSD低位优先，适合做长度相等字符串排序 */
public String[] radixLSDSort(String[] arr) {
if(arr.length < 2) {
return arr;
}
int maxLength = arr[0].length();
for (int i = 0; i < maxLength; i++) {
//count数组初始化 26字母 + 1空位
int[] count = new int[27];
for (int j = 0; j < arr.length; j++) {
int index = arr[j].length() - i - 1;
int temp = arr[j].charAt(index);
// 这里只考虑小写，小写字母a开始 ascii = 97 count第0位存放空
count[temp - 96]++;
}
//count数组递增
for (int j = 1; j < count.length; j++) {
count[j] += count[j - 1];
}
//原数组输出
String[] result = new String[arr.length];
for (int j = 0; j < arr.length; j++) {
int index = arr[j].length() - i - 1;
int temp = arr[j].charAt(index);
int value = count[temp - 96 - 1]++;
result[value] = arr[j];
}
arr = result;
}
return arr;
}
/** LSD低位优先，数字排序，长短都可以 */
public int[] radixLSDSort(int[] arr){
//找到最大长度
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max,arr[i]);
}
int maxLength = 0;
while (max > 0){
max /= 10;
maxLength++;
}
for (int i = 0; i < maxLength; i++) {
//初始化count数组
int[] count = new int[11];
for (int j = 0; j < arr.length; j++) {
int value = (int) (arr[j] % Math.pow(10,i + 1) / Math.pow(10,i));
count[value + 1]++;
}
//count数组递增
for (int j = 1; j < count.length; j++) {
count[j] += count[j - 1];
}
//原数组输出
int[] result = new int[arr.length];
for (int j = 0; j < arr.length; j++) {
int value = (int) (arr[j] % Math.pow(10,i + 1) / Math.pow(10,i));
result[count[value]++] = arr[j];
}
arr = result;
}
return arr;
}
public static void main(String[] args) {
String[] stringArr = new String[]{"aaa", "aab", "aba","abc", "dab", "cad", "efe", "fff", "ggg", "hhh", "iii", "aaa"};
int[] arrRadixArr = new int[]{0,66666666, 2, 3322, 43445, 31, 8, 6, 8, 22200, 564, 111};
System.out.println(Arrays.toString(new RadixSort().radixLSDSort(stringArr)));
System.out.println(Arrays.toString(new RadixSort().radixLSDSort(arrRadixArr)));
}
复杂度
- 平均复杂度: O(n * k)
- 最好情况复杂度: O(n * k)
- 最坏情况复杂度: O(n * k)
- 空间复杂度: O(n + k)
- 排序方式: 内排序
- 稳定性: 稳定
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
