十大经典排序算法
文章目录
- 十大排序算法汇总
- 比较和非比较的区别
- 一些基本的术语
- 排序算法复杂度及稳定性
- 一、冒泡排序
- 二、快速排序
- 三、简单插入排序
- 四、希尔排序
- 五、简单选择排序
- 六、堆排序
- 七、二路归并排序
- 八、计数排序
- 九、桶排序
- 十、基数排序
**
十大排序算法汇总
**
比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
一些基本的术语
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能出现在b的后面；
内排序：所有的排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度：一个算法执行所消耗的时间；
空间复杂度：运行完一个程序所需内存的大小。
排序算法复杂度及稳定性
一、冒泡排序
算法简介
1.从左向右依次对比相邻元素，将较大值交换到右边；
2.每一轮循环可将最大值交换到最左边
3.重复1.2两个步骤，直至完成整个数组。
动图演示
代码实现
/**
* 冒泡算法的实现
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if(array.length==0) {
return array;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if(array[j+1]<array[j]) {
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
return array;
}
应用场景
一般在学习的时候作为理解排序原理的时候使用，在实际应用中不会使用
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
二、快速排序
算法简介
1.选择一个元素赋值给中间元素temp，默认选择左边第一个元素，这样左边第一个元素的位置就空出来了；
2. 先从最右边的元素开始依次跟temp比较大小，大于等于temp元素的原地不动，遇到小于temp元素的则终止循环，把该元素赋值到左侧空出来的位置，同时左侧索引值自增，这是该元素原来的位置就空出；
3. 然后左侧元素开始依次跟temp比较大小，小于等于temp元素的原地不动，遇到大雨temp元素的则终止循环，把该元素赋值到右侧空出来的位置，同时右侧索引值自减；
4. 依次循环2,3步，直至左侧索引等于右侧索引，则完成一轮循环，把哨兵赋值到该索引的位置。
5. 在分别递归地对temp左右两侧的子数组进行1234步，直至递归子数组只有一个元素则排序完成
动图演示
代码实现
package leetcode;
/**
* 快速排序算法
* @author acer
*
*/
public class Quick_sort {
public void quicksort(int[] n, int left, int right) {
int dp;
if (left < right) {
dp = partition(n, left, right);
quicksort(n, left, dp - 1);
quicksort(n, dp + 1, right);
}
}
public int partition(int[] n, int left, int right) {
int pivot = n[left];//选择第一个为参考点
while (left < right) {
while (left < right && n[right] >= pivot)//让参考点与最右边的相比较，小于不动，大于右面减一
right--;
if (left < right)//让小于参考点的数，进入空出来的位置，
n[left++] = n[right];
while (left < right && n[left] <= pivot)//让参考点与左边的相比较，小于左面加一，大于不动
left++;
if (left < right)//让大于参考点的数，进入空出来的位置
n[right--] = n[left];
}
n[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,47};
Quick_sort sort=new Quick_sort();
sort.quicksort(a, 0, a.length-1);
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
}
}
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
三、简单插入排序
算法简介
1.左边第一个元素可作为有序子数组；
2.从第二个元素开始，依次向前比较，大于该元素的则向右移一位，直到比该元素小的元素，插入其后；
3.依次向后推进，直至整个数组成为有序数组
动图演示
代码实现
package leetcode;
public class Insert_sort {
public static void main(String[] args) {
int[] array= {3,3,345,2,753,4765,734658,567};
int[] arrayNew=Insert_sort.insert_sort(array);
for (int i = 0; i < arrayNew.length; i++) {
System.out.print(arrayNew[i]+" ");
}
}
public static int[] insert_sort(int[] array) {
if(array.length==0) {
return array;
}
int current;
for (int i = 0; i < array.length-1; i++) {
current=array[i+1];
int preIndex=i;
while(preIndex>=0&¤t<array[preIndex]) {
array[preIndex+1]=array[preIndex];
preIndex--;
}
array[preIndex+1]=current;
}
return array;
}
}
应用场景
如果大部分数据距离它正确的位置很近或者近乎有序？例如银行的业务完成的时间
如果是这样的话，插入排序是更好的选择。
算法分析
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
四、希尔排序
算法简介
1.首先选择一个步长值gap，以步长值为间隔把数组分为gap个子数组gap=length/2
2.对每个子数组进行插入排序；
3.逐步减小步长 gap = gap/2,重复对数组进行1，2 步骤；
4.当步长值减为1时，相当于对数组进行一次直接插入排序。
图片演示
代码实现
package leetcode;
public class Shell_sort {
public static void main(String[] args) {
int[] array= {3,3,345,2,753,4765,734658,567,7};
int[] arrayNew=Shell_sort.shell_sort(array);
for (int i = 0; i < arrayNew.length; i++) {
System.out.print(arrayNew[i]+" ");
}
}
public static int[] shell_sort(int[] array) {
if(array.length==0) {
return array;
}
int length=array.length;
int temp,gap=length/2;
while(gap>0) {
for (int i = gap; i < length; i++) {
temp=array[i];
int preIndex=i-gap;
while(preIndex>=0&&array[preIndex]>temp) {
array[preIndex+gap]=array[preIndex];
preIndex-=gap;
}
array[preIndex+gap]=temp;
}
gap/=2;
}
return array;
}
}
算法的优点
相对于直接插入排序，希尔排序要高效很多，因为当gap 值较大时，对子数组进行插入排序时要移动的元素很少，元素移动的距离很大，这样效率很高；在gap逐渐减小过程中，数组中元素已逐渐接近排序的状态，所以需要移动的元素逐渐减少；当gap为1时，相当于进行一次直接插入排序，但是各元素已接近排序状态，需要移动的元素很少且移动的距离都很小。
算法分析
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
五、简单选择排序
算法简介
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
动图演示
代码实现
package leetcode;
/**
* 选择排序
* @author acer
*
*/
public class Selection_sort {
public static void main(String[] args) {
int[] array= {3,3,345,2,753,4765,734658,567,7};
int[] arrayNew=Selection_sort.selection_sort(array);
for (int i = 0; i < arrayNew.length; i++) {
System.out.print(arrayNew[i]+" ");
}
}
public static int[] selection_sort(int[] array) {
if(array.length==0) {
return array;
}
for(int i=0;i<array.length;i++) {
int minIndex=i;
for(int j=i;j<array.length;j++) {
if(array[j]<array[minIndex])//找到最小的数
minIndex=j;//将最小数的索引保存
}
int temp=array[minIndex];
array[minIndex]=array[i];
array[i]=temp;
}
return array;
}
}
应用场景
当数据量较小的时候适用
算法分析
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
六、堆排序
算法简介
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
图片演示
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。
此时，我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
代码实现
package leetcode;
import java.util.Arrays;
/**
* 堆排序
* @author acer
*
*/
public class HeapSort {
public static void main(String[] args) {
int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
// 接下来就是排序的主体逻辑
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array) {
// 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整
// 也就是说，是按照自下而上，每一层都是自右向左来进行调整的
// 注意，这里元素的索引是从0开始的
// 另一件需要注意的事情，这里的建堆，是用堆调整的方式来做的
// 堆调整的逻辑在建堆和后续排序过程中复用的
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换
// 说是交换，其实质就是把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
}
/**
*
* @description 这里，是整个堆排序最关键的地方，正是因为把这个方法抽取出来，才更好理解了堆排序的精髓，会尽可能仔细讲解
* @author
* @param
* @return
* @time 2018年3月9日 下午2:54:38
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
// 可以参照sort中的调用逻辑，在堆建成，且完成第一次交换之后，实质上i=0；也就是说，是从根所在的最小子树开始调整的
// 接下来的讲解，都是按照i的初始值为0来讲述的
// 这一段很好理解，如果i=0；则k=1；k+1=2
// 实质上，就是根节点和其左右子节点记性比较，让k指向这个不超过三个节点的子树中最大的值
// 这里，必须要说下为什么k值是跳跃性的。
// 首先，举个例子，如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了，
// 也就是说，是以本节点的左子节点为根的那棵小的子树
// 而如果a[0}<a[2]呢，那就调整a[0]和a[2]的位置，然后继续调整以a[2]为根节点的那棵子树，而且肯定是从左子树开始调整的
// 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，直到每一颗小子树都满足大根堆的规律为止
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) {
k++;
}
// 如果发现子节点更大，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 下面就是非常关键的一步了
// 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
// 所以，循环对子节点所在的树继续进行判断
i = k;
// 如果不用交换，那么，就直接终止循环了
} else {
break;
}
}
}
/**
* 交换元素
*
* @param arr
* @param a
* 元素的下标
* @param b
* 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
应用场景
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
七、二路归并排序
算法简介
分：
1.一直分两组，分别对两个数组进行排序(根据上层对下层在一组的数据通过临时数组排序，再将有序数组挪回上层数组中)。
2. 循环第一步，直到划分出来的“小组”只包含一个元素，只有一个元素的数组默认为已经排好序。
合：（合并时，站在上层合并下层（使组内有序））
1.将两个有序的数组合并到一个大的数组中。
2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。最后把小组合成一个组。
图片演示
代码实现
public class MergeSort {
/**
* 归并排序
* @param arr
* @param left
* @param right
*/
public static void mergeSort(int[] arr, int left, int right) {
if(null == arr) {
return;
}
if(left < right) {
//找中间位置进行划分
int mid = (left+right)/2;
//对左子序列进行递归归并排序
mergeSort(arr, left, mid);
//对右子序列进行递归归并排序
mergeSort(arr, mid+1, right);
//“合”。 进行归并
merge(arr, left, mid, right);
}
}
/**
* 进行归并
* @param arr
* @param left
* @param mid
* @param right
*/
private static void merge(int[] arr, int left, int mid, int right) {
int[] tempArr = new int[arr.length];
int leftStart = left;
int rightStart = mid+1;
int tempIndex = left;
while(leftStart <= mid && rightStart <= right) {
if(arr[leftStart] < arr[rightStart]) {
tempArr[tempIndex++] = arr[leftStart++];
} else {
tempArr[tempIndex++] = arr[rightStart++];
}
}
while(leftStart <= mid) {
tempArr[tempIndex++] = arr[leftStart++];
}
while(rightStart <= right) {
tempArr[tempIndex++] = arr[rightStart++];
}
while(left <= right) {
arr[left] = tempArr[left++];
}
}
private static void showArr(int[] arr) {
for(int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 6, 1, 3, 8, 5, 9};
/*
* 归并排序
* 对上下限值分别为0和arr.length-1的记录序列arr进行归并排序
*/
mergeSort(arr, 0, arr.length-1);
showArr(arr);
}
}
应用场景
内存空间不足的时候使用归并排序，能够使用并行计算的时候使用归并排序。
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
八、计数排序
算法简介
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动图演示
代码实现
public class CountSort {
private static int[] countsort(int[] arr) {
int max=arr[0];
int min=arr[0];
//step1:得到最大值和最小值，确定构建的数组长度
for (int i = 0; i < arr.length; i++) {
if(arr[i]>max) {
max=arr[i];
}
if(arr[i]<min) {
min=arr[i];
}
}
//step2:构建一个数组，用来存放每一个数对应出现的次数
int d=max-min;
int [] countArray=new int [d+1];
//统计次数
for (int i = 0; i < arr.length; i++) {
countArray[arr[i]-min]++;
}
System.out.println("统计不同元素出现的次数："+Arrays.toString( countArray));
//step3:对此时的数组做变形,统计数组从第二个元素开始，每一个元素等于它本身都加上前面所有元素之和。
for(int i=1;i<countArray.length;i++) {
countArray[i]+=countArray[i-1];
}
System.out.println("变形后的数组："+Arrays.toString( countArray));
//step4:倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组,确保稳定性
int[] sortedArray = new int[arr.length];
for(int i=arr.length-1;i>=0;i--) {
sortedArray[countArray[arr[i]-min]-1]=arr[i];
countArray[arr[i]-min]--;
}
return sortedArray;
}
public static void main(String[] args) {
int arr[]={93,95,98,98,94,92,96,91};
int[] sortedArray=countsort(arr);
System.out.println("结果输出："+Arrays.toString(sortedArray));
}
}
应用场景
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0100]，[1000019999] 这样的数据。
算法分析
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
九、桶排序
算法简介
桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。
假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个”桶”。
在排序时，逐个遍历数组a，将数组a的值，作为”桶数组r”的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。
图片演示
bucketSort(a, n, max)是作用是对数组a进行桶排序，n是数组a的长度，max是数组中最大元素所属的范围[0,max)。
假设a={8,2,3,4,3,6,6,3,9}, max=10。此时，将数组a的所有数据都放到需要为0-9的桶中。如下图：
代码实现
package leetcode;
/**
* 桶排序
* @author acer
*
*/
public class BucketSort {
/*
* 桶排序
*
* 参数说明：
* a -- 待排序数组
* max -- 数组a中最大值的范围
*/
public static void bucketSort(int[] a, int max) {
int[] buckets;
if (a==null || max<1)
return ;
// 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
buckets = new int[max];
// 1. 计数
for(int i = 0; i < a.length; i++)
buckets[a[i]]++;
// 2. 排序
for (int i = 0, j = 0; i < max; i++) {
while( (buckets[i]--) >0 ) {
a[j++] = i;
}
}
buckets = null;
}
public static void main(String[] args) {
int i;
int a[] = {8,2,3,4,3,6,6,3,9};
System.out.printf("before sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
bucketSort(a, 10); // 桶排序
System.out.printf("after sort:");
for (i=0; i<a.length; i++)
System.out.printf("%d ", a[i]);
System.out.printf("\n");
}
}
算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
十、基数排序
算法简介
相比其它排序，主要是利用比较和交换，而基数排序则是利用分配和收集两种基本操作。基数 排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。
实现：将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的两种方式：
高位优先，又称为最有效键(MSD),它的比较方向是由右至左；
低位优先，又称为最无效键(LSD),它的比较方向是由左至右；
动图演示
代码实现
package leetcode;
import java.util.Arrays;
/**
* 基数排序演示
*
*
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 高位优先法
*
* @param arr 待排序列，必须为自然数
*/
private static void radixSort(int[] arr) {
//待排序列最大值
int max = arr[0];
int exp;//指数
//计算最大值
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
}
//从个位开始，对数组进行排序
for (exp = 1; max / exp > 0; exp *= 10) {
//存储待排元素的临时数组
int[] temp = new int[arr.length];
//分桶个数
int[] buckets = new int[10];
//将数据出现的次数存储在buckets中
for (int value : arr) {
//(value / exp) % 10 :value的最底位(个位)
buckets[(value / exp) % 10]++;
}
//更改buckets[i]，
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
//将数据存储到临时数组temp中
for (int i = arr.length - 1; i >= 0; i--) {
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
//将有序元素temp赋给arr
System.arraycopy(temp, 0, arr, 0, arr.length);
}
}
}
算法分析
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
MSD 从高位开始进行排序 LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
一些基本情况
数据有什么特征
有没有可能包含有大量重复的元素
如果有这种可能的话，三路快排是更好地选择
是否数据的取值范围非常有限，比如对学生的成绩排序。
如果是这样的话，计数排序是更好的选择
对排序有什么额外的要求
是否需要稳定排序
如果是的话，归并排序是更好的选择，快排就不怎么好了
数据的存储状况是怎么样的
快排是依赖于数组的随机存储
如果是使用链表存储的
如果是的话，归并排序是更好的选择，
数据的存储状况是怎么样的
数据的大小是否可以装在在内存里
数据量很大或者内存很小，不足以装载在内存里，需要使用外排序算法。
本文转自 https://blog.csdn.net/qq_34411783/article/details/97611152，如有侵权，请联系删除。
哦
🌚🌚🌚