提到数据结构与算法，无法避免的一点就包含排序，熟练的掌握各种排序算法则是一个程序员必备的素质之一，除此之外，排序算法也是当下各大技术公司比较喜欢问的技术点，所以，就这一点JavaBuild整理了常见的8种排序算法，希望可以给诸位一点点的参考，有什么错误问题或者更好的解法，欢迎大家在评论区留言，小编一定不遗余力的学习与改正。
常见的8种排序算法性能对比
| 排序算法的分类 | 排序算法 | 最好时间 | 最坏时间 | 平均时间 | 辅助空间 | 稳定性 | 备注 |
| 交换排序 | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | n小时较好 |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | 不稳定 | n大时较好 | |
| 插入排序 | 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 大部分元素已经有序 |
| 希尔排序 | O(n) | O(nlogn) | O(n^k)(1<k<2) | O(1) | 不稳定 | K为所选分组 | |
| 选择排序 | 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | n小时较好 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1） | 不稳定 | n大时较好 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | n大时较好 | |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 | 元素大小差别大时较好 |
- 定义
在开始撸代码之前，对于以下几个概念还是要做一个简单的解释的哈，方便理解。
时间复杂度：简单理解的话就是对一个数据规模为n的数据排序所需要的操作次数
空间复杂度：简单理解就是执行排序算法时所需要的存储空间。其中O(1)：空间复杂度不随n大小而改变时，是一个常量级别的空间复杂度；O(n):算法的空间复杂度与n成线性比例时的表示；O(logn):一个算法的空间复杂度与以2为底的对数成正比的时候的一种表示，2x = n,那么x就等于log2n;
稳定性：所谓的稳定性就是排序前后，2个相等的元素的相对位置没有发生改变，那么这种排序算法就是稳定的，如: 排序前为A1，A2；排序后则还是A1，A2（A1=A2）。
- 算法
一、冒泡排序（交换排序）
所谓冒泡排序，通俗理解就是通过不断的将相邻的元素进行两两比较和交换，使得关键字较小的记录像水中气泡一样，不断上浮到最左侧；关键字较大的记录像石头一样不断下沉到最右侧，每一次就有一个最大的关键字下沉到最右侧，经过n趟相同操作，使得整个序列有序。代码如下：
import java.util.Arrays; /** * 常用排序算法之冒泡排序： * 算法描述：冒泡排序，不用比喻成泡泡上浮，个人觉得直接上定义，浅显易懂，就是对于一个拥有N个元素的无序序列 * 进行至少N-1次的排序(最后一个元素，单个元素直接是有序的，故不需要再排)，每次排序的过程都是相邻的两个元素进行比较， * 替换操作，因此，每一次至少会比较出一个最大值， * 而这个最大值就会落在序列的一头，然后对剩下的序列进行同样的操作，直到排序完成。 * 最好时间复杂度：O(n^2),整个序列已经排好队，一次遍历搞定 * 最坏的时间复杂度：O(n^2), * 平均的时间复杂度：O(n^2), * 空间复杂度：O(1); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：稳定 * * //将ArrayList中元素转为int数组中元素 * //int[] arr = list.stream().mapToInt(Integer::intValue).toArray(); * * 备注：n较小时排序排序效率较好。 */ public class BubbleSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); bubbleSort(arr); System.out.println(Arrays.toString(arr)); } //冒泡排序(实现算法就这么多代码) public static void bubbleSort(int[] arr){ //控制一共需要多少轮比较 for (int i = 0; i < arr.length-1; i++) { //每次比较完，放在最后的元素已经是上轮比较的最大值了，故不需要再作比较 for (int j = 0; j < arr.length-1-i; j++) { if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } }
二、快速排序（交换排序）
所谓快速排序，其实就是冒泡排序的升级版，二者都属于交换排序的范畴，不同的是，快排采用了分治思想，选出一个参照数之后，从头部和尾部分别开始与参照数比较，小于参照数的放在左侧，大于参照数的放在右侧，这样就类似二分的将一个序列分成了更小的两个序列，然后依次对参照数左侧和右侧的序列再进行递归快排，直到所有记录都有序为止。代码如下：
import java.util.Arrays; /** * 常用排序算法之快速排序： * 算法描述：快速排序，所谓快速排序，其实就是冒泡排序的升级版，二者都属于交换排序的范畴， * 不同的是，快速排序采用了二分思想，选出一个参照数之后，从头部和尾部开始分别与标准数 * 这样，每遍历一次就会将相对参照数小和大的数，分别分散到了参照数的两侧，后面递归左侧和 * 右侧，分别进行如上排序，直到全部有序。 * 最好时间复杂度：O(nlog(n)); * 最坏的时间复杂度：O(n^2), * 平均的时间复杂度：O(nlog(n)), * 空间复杂度：O(log(n)); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：不稳定 * 备注：n大时比较好 */ public class QuickSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } //快速排序 public static void quickSort(int[] arr,int start,int end){ if(start < end){ int min = arr[start]; int low = start; int high = end; while(low < high){ while (low < high && min<=arr[high]){ high--; } //当不满足的high座标对应的数，肯定比min小，故将其赋值到low位置（min左侧） arr[low] = arr[high]; while(low < high && min >= arr[low]){ low++; } arr[high] = arr[low]; } arr[low] = min; //排序min左侧的序列 quickSort(arr,start,low); //排序min右侧的序列 quickSort(arr,low+1,end); } } }
三、直接插入排序（插入排序）
所谓直接插入排序，就是给定一组记录，初始假设第一个记录自成一个有序序列，其余的序列为无序序列，接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直到最后一个记录插入到有序序列中为止。代码如下：
/** * 常用排序算法之插入排序： * 算法描述：插入排序，把待排序的记录，按照其关键字的大小，逐个插入到一个已经排好序的有序序列中， * 直到所有的记录插完为止，得到一个全新的有序数列。 * 最好时间复杂度：O(n); * 最坏的时间复杂度：O(n^2), * 平均的时间复杂度：O(n^2), * 空间复杂度：O(1); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：稳定 * 备注：大部分元素已经有序时效果最好 * @author qingshan * @time 2020/9/19 - 15:42 */ public class InsertSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); insertSort(arr); System.out.println(Arrays.toString(arr)); } //插入排序 public static void insertSort(int[] arr) { //假设第一个记录是有序的，从第二个记录开始插入 for (int i = 1; i < arr.length; i++) { if(arr[i] < arr[i-1]){ int temp = arr[i]; int j; //当前位置向前比较，找到合适的位置插入 for(j = i-1;j>=0&&temp<arr[j];j--){ arr[j+1]=arr[j]; } arr[j+1]=temp; } } } }
四、希尔排序（插入排序）
所谓希尔排序，就是插入排序的升级版，也叫缩小增量排序，先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对每个子序列进行直接插入排序，这样使得每个子序列都有序，最后再将所有的元素进行一次插入排序。代码如下：
import java.util.Arrays; /** * 常用排序算法之希尔排序： * 算法描述：希尔排序，其实也是插入排序的升级版，也叫缩小增量排序，先将待排序的元素分成多个子序列 * 这每个子序列排序起来速度会快很多，每个子序列都进行插入排序，这样使得每个子序列都有序 * 最后再将所有的元素进行一次插入排序 * 最好时间复杂度：O(n); * 最坏的时间复杂度：O(n^s,s=1.3),所以约等于O(nlog(n)); * 平均的时间复杂度：O(nlog(n)), * 空间复杂度：O(1); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：不稳定 * 备注：s为所选的分组 * @author qingshan * @time 2020/9/19 - 15:42 */ public class ShellSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); shellSort(arr); System.out.println(Arrays.toString(arr)); } //插入排序 public static void shellSort(int[] arr) { //遍历所有的步长 for (int d = arr.length/2; d > 0; d/=2) { //每个步长的插入排序； for(int i = d;i<arr.length;i++){ for(int j = i-d;j>=0;j-=d){ if(arr[j]>arr[j+d]){ int temp = arr[j]; arr[j] = arr[j+d]; arr[j+d] = temp; } } } } } }
五、简单选择排序（选择排序）
所谓简单选择排序，事先将数组分为已排序和未排序区域，每次从未排序的元素中通过交换将其放到已排序的去区域尾部。
步骤：1，进行数组长度-1轮比较
2，每轮比较找到未排序区域的最小值下标
3，如果最小值下标为非排序区域第一个元素，进行交换后，此时，未排序区域第一个元素则变成了已排序区域的最后一个元素。
4，进行下一轮比较的时候，找到未排序区域的最小值，然后放到已排序区域的最末尾处，直到整个序列有序。
代码如下：
import java.util.Arrays; /** * 常用排序算法之选择排序： * 算法描述：选择排序，将序列分为已排序和未排序，每次从未排序的序列中找到最小的元素 * 最好时间复杂度：O(n^2); * 最坏的时间复杂度：O(n^2), * 平均的时间复杂度：O(n^2), * 空间复杂度：O(1); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：不稳定 * 备注：n小时较好 * @author qingshan * @time 2020/9/19 - 15:42 */ public class SelectSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); selectSort(arr); System.out.println(Arrays.toString(arr)); } //选择排序 public static void selectSort(int[] arr) { //遍历所有的数 for (int i = 0; i < arr.length; i++) { //初始化最小元素的下标 int minIndex = i; for (int j = i+1; j < arr.length; j++) { if(arr[minIndex]>arr[j]){ //记录最小值下标 minIndex = j; } } if(minIndex!=i){ int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } }
六、堆排序（选择排序）
堆：一种特殊的树形结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根节点的值大于（或者小于）两个子节点的值，同时，根节点的两个子树也分别十一个堆。
所谓堆排序，其实就是一种树形选择排序，堆排序中有大顶堆和小顶堆两种，其中大顶堆（升序ASC适用），每个父节点的值都比子节点要大，这样每次排序后都从根节点取出最大值放到队列尾部，将剩下的部分再次构建成大顶堆，再取出，直到所有元素都有序。小顶堆：原理类似，只不过每次找出的是最小数，适合降序（DESC）排列，代码如下：
import java.util.Arrays; /** * 常用排序算法之堆排序： * 算法描述：堆排序，堆排序，主要分为小顶堆和大顶堆，所谓的大顶堆（升序（ASC）适用）就是每个父节点都比子节点要大，这样 * 每次排序后都取出最大的值放到了队列尾部，直到所有的元素有序。 * 小顶堆：原理与大顶堆类似，只不过每次找出的是最小的值，所以适应于降序（DESC）排列 * 最好时间复杂度：O(nlog(n)); * 最坏的时间复杂度：O(nlog(n)), * 平均的时间复杂度：O(nlog(n)), * 空间复杂度：O(1); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：不稳定 * 备注：n大的时候较好 */ public class HeapSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); heapSort(arr); System.out.println(Arrays.toString(arr)); } //使用大顶堆进行堆排序 public static void heapSort(int[] arr) { int start = (arr.length-2)/2; for (int i = start;i>=0; i--) { maxHeap(arr,arr.length,i); } for (int i = arr.length-1;i>=0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; maxHeap(arr,i,0); } } /** * 构造一个大顶堆 * @param arr * @param size 要构造成大顶堆的元素有多少个 * @param index 从哪个位置开始构造大顶堆，一般为最后一个节点的父节点开始 */ public static void maxHeap(int[] arr,int size,int index){ int leftNode = 2*index+1; int rightNode = 2*index+2; int max = index; if(leftNode<size&&arr[leftNode]>arr[index]){ max = leftNode; } if(rightNode<size&&arr[rightNode]>arr[index]){ max = rightNode; } if(max!=index){ int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; //处理一下由于交换位置导致的破坏原来的堆结构， maxHeap(arr,size,max); } } }
七、归并排序
所谓归并排序，就是利用递归和分治的思想将数据划分为越来越小的半子表，然后再对半子表进行排序，最后再用递归的方法将排好序的半子表合并成越来越大的有序列表。代码如下：
import java.util.Arrays; /** * 常用排序算法之归并排序： * 算法描述：归并排序利用递归于分治思想将数据划分成为越来越小的半子表，再对半子表排序 * 最后再用递归方法将排好序的半子表合并为越来越大的有序列表。 * 最好时间复杂度：O(nlog(n)); * 最坏的时间复杂度：O(nlog(n)), * 平均的时间复杂度：O(nlog(n)), * 空间复杂度：O(n); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：稳定 * 备注：n大的时候较好 */ public class MergeSort { public static void main(String[] args) { int[] arr = {3,2,6,1,8,4}; System.out.println(Arrays.toString(arr)); mergeSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr,int low,int high){ if(low<high){ int middle = low+(high-low)/2; mergeSort(arr,low,middle); mergeSort(arr,middle+1,high); merge(arr,low,high,middle); } } //归并排序，将一个数组以middle为分界线，看成两个数组，然后进行递归归并操作 public static void merge(int[] arr,int low,int high,int middle) { //先创建一个临时数组用来存储归并的元素 int[] temp = new int[high-low+1]; //记录第一个数组的遍历 int i = low; //记录第二个数组的遍历 int j = middle+1; //用于记录上面那个临时数组记录的下标（temp） int index = 0; while(i<=middle&&j<=high){ if(arr[i]<=arr[j]){ temp[index] = arr[i]; i++; }else{ temp[index] = arr[j]; j++; } index++; } //处理其中一个数组的多余的数据 while(i<=middle){ temp[index] = arr[i]; i++; index++; } while(j<=high){ temp[index] = arr[j]; j++; index++; } //把临时数组中的数据放回源数组 for(int k = 0;k<temp.length;k++){ arr[k+low]=temp[k]; } } }
八、基数排序
所谓基数排序，就是通过最大值的位数，然后按照每一位的数，放到对应的0-9的数组中，然后按照大小顺序从数组中取数，直到所有位数排完，就是有序了，利用了空间换时间。代码如下：
import java.util.Arrays; /** * 常用排序算法之基数排序： * 算法描述：就是通过最大值的位数，然后按照每一位的数，放到0-9的数组中，然后按照顺序从数组中 * 取数，直到所有位数排完，就是有序了。利用空间换时间 * 第二种解决方法：就是在第一层数组中，使用队列来存取临时取出来的数据，根据队列先进先出 * 的性质取数，直到有序。 * 最好时间复杂度：O(d(n+j)); * 最坏的时间复杂度：O(d(n+j)), * 平均的时间复杂度：O(d(n+j)), * 空间复杂度：O(n+j); * * 稳定性：所谓稳定性就是在一个序列中多个相同的元素，排序前和排序后的相对次序相同，如A（1），A（2） * 在排序后仍然是A（1），A（2） * * 稳定性：不稳定 * 备注：n个元素中大小差距比较大的效果好 * @author qingshan * @time 2020/9/19 - 15:42 */ public class RadixSort { public static void main(String[] args) { int[] arr = {32,2,67,109,821,423}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr){ //存数组中最大的数字 int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { if(arr[i]>max){ max = arr[i]; } } //判断最大数字是几位数 int maxLength = (max+"").length(); //用于临时存储数据的数组 int[][] temp = new int[10][arr.length]; //用于记录在temp中相应的数组中存放的数字的数量 int[] counts = new int[10]; //根据最大长度的数决定要比较的次数 for (int i = 0,n=1; i < maxLength; i++,n*=10) { for (int j = 0; j < arr.length; j++) { //计算余数 int ys = arr[j] / n % 10; //把当前遍历的数据放入指定的数组中 temp[ys][counts[ys]] = arr[j]; //记录添加到每个数组中的数量 counts[ys]++; } //记录取得元素需要放的位置 int index = 0; //把数字取出来 for(int k = 0;k<counts.length;k++){ //记录数量的数组中当前余数记录的数量不为0； if(counts[k]!=0){ for(int l=0;l<counts[k];l++){ //取出元素 arr[index] = temp[k][l]; index++; } //把数量置为0 counts[k] = 0; } } } } }
