排序算法代码
❶ 一文详解三种时间复杂度为O(N)的排序算法
导读数据结构和算法这个东西，如果你不去学，可能真的这辈子都用不到，也感受不到它的好。但是一旦掌握，你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码，需要花很多心思来设计的架构，用了数据结构和算法之后，很容易就可以解决了。
排序是一个非常经典的问题，它以一定的顺序对一个数组（或一个列表）中的项进行重新排序（可以进行比较的，例如整数，浮点数，字符串等）。
有许多不同的排序算法，每个都有其自身的优点和局限性。
基于比较的排序算法:
比较数组的元素，并决定是否交换它们的位置。
BUB-冒泡排序
SEL-选择排序
INS-插入排序
MER-归并排序(递归实现)
QUI-快速排序(递归实现)
R-Q-随机快速排序(递归实现)
不基于比较的排序算法:
COU-计数排序
RAD-基数排序
我们来逐一破解这些排序算法。
本文分析冒泡排序、选择排序和插入排序。
一、冒泡排序假设数组arr长度为$N$，冒泡排序的过程为：
在arr[0～N-1]范围上：
arr[0]和arr[1]，谁大谁来到1位置；
arr[1]和arr[2]，谁大谁来到2位置；
[N-2]和arr[N-1]，谁大谁来到N-1位置；
在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置；
在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置；
…
最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置。
整个过程将最大的元素移动到最右侧，也就是最大的元素浮动到最右边，像冒泡一样。
如图所示：
如图展示了第1趟排序的过程。
自己会动的才是好图：
代码实现：
publicclassBubbleSort{publicstaticvoidmain(String[]args){int[]arr={18,15,13,17,6,20,15,9};sort(arr);}publicstaticvoidsort(int[]arr){if(arr==null||arr.length<2){return;}//想要让0~i位置上有序，i一开始在数组的最大索引位置上，每比完1次，减1for(inti=arr.length-1;i>0;i--){//0~i//0~(i-1)//0~(i-2)...//0~1for(intj=0;j<i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}System.out.println("0~"+i+"位置比较结果："+Arrays.toString(arr));}}}执行结果：
第0趟比较结果：[15,13,17,6,18,15,9,20]第1趟比较结果：[13,15,6,17,15,9,18,20]第2趟比较结果：[13,6,15,15,9,17,18,20]第3趟比较结果：[6,13,15,9,15,17,18,20]第4趟比较结果：[6,13,9,15,15,17,18,20]第5趟比较结果：[6,9,13,15,15,17,18,20]第6趟比较结果：[6,9,13,15,15,17,18,20]第7趟比较结果：[6,9,13,15,15,17,18,20]时间复杂度的计算：
比较和交换需要一个以常量为界的时间，我们称之为$c$。
BubbleSort中有两个嵌套循环。
外循环正好运行$N$次迭代。但内部循环运行变得越来越短：
当i=0，（N-1）次迭代（比较和可能交换）时。
当i=1，（N-2）次迭代时，...
当i=（N-2）时，1次迭代,
当i=（N-1），0迭代.
因此：
$$总迭代次数=（N-1）+（N-2）+...+1+0=N×（N-1）/2$$
计算总时间：$$总时间=c×N×（N-1）/2=O（N?）$$
二、选择排序给定$N$个元素和L=0的数组，选择排序过程为：
在[L...N-1]范围内找出最小项X的位置，
用第L项交换X，
将下限L增加1并重复步骤1直到L=N-2。
手绘选择排序过程：
动画演示：
代码实现：
publicclassSelectionSort{publicstaticvoidmain(String[]args){int[]arr={18,15,13,17,6,20,15,9};sort(arr);}publicstaticvoidsort(int[]arr){for(inti=0;i<arr.length-1;i++){//目的：找到最小值的位置，并将该位置的数与i位置的数交换intminIndex=i;for(intj=i+1;j<arr.length;j++){minIndex=arr[j]>arr[minIndex]?minIndex:j;}//找到最小值后，与i位置的数交换inttemp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=temp;System.out.println("第"+i+"~"+(arr.length-1)+"位置上的最小值索引为"+minIndex+",最小值为："+arr[minIndex]+"，本次排序结果："+Arrays.toString(arr));}}}运行结果：
第0~7位置上的最小值索引为4,最小值为：18，本次排序结果：[6,15,13,17,18,20,15,9]第1~7位置上的最小值索引为7,最小值为：15，本次排序结果：[6,9,13,17,18,20,15,15]第2~7位置上的最小值索引为2,最小值为：13，本次排序结果：[6,9,13,17,18,20,15,15]第3~7位置上的最小值索引为7,最小值为：17，本次排序结果：[6,9,13,15,18,20,15,17]第4~7位置上的最小值索引为6,最小值为：18，本次排序结果：[6,9,13,15,15,20,18,17]第5~7位置上的最小值索引为7,最小值为：20，本次排序结果：[6,9,13,15,15,17,18,20]第6~7位置上的最小值索引为6,最小值为：18，本次排序结果：[6,9,13,15,15,17,18,20]总结一下选择排序的过程：
arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。
arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。
arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。
…
arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。
估算：很明显，如果arr长度为N，每一步常数操作的数量，如等差数列一般，所以有：
$$总的常数操作数量=a(N?)+bN+c(a、b、c都是常数)$$
所以选择排序的时间复杂度为$O(N?)$。
三、插入排序这个算法比较好理解，想象一下平时打扑克牌，我们很自然的就会把一张牌和手里的牌挨个比较一下，并把它插入到合适的位置。
过程：
想让arr[0~0]上有序，这个范围只有一个数，当然是有序的；
想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做；
…
想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动；
最后一步，想让arr[0~N-1]上有序，arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。
如果某个算法流程的复杂程度会根据数据状况的不同而不同，那么必须要按照最差情况来估计。
很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般。
所以有：
$$总的常数操作数量=a(N?)+bN+c(a、b、c都是常数)$$
因此插入排序排序的时间复杂度为$O(N?)$。
代码实现：
publicclassInsertionSort{publicstaticvoidmain(String[]args){int[]arr={18,15,13,17,6,20,15,9};sort(arr);}publicstaticvoidsort(int[]arr){if(arr==null||arr.length<2){return;}//想让0~i位置上有序，从i位置往前看，一直到左边的数不比自己大了，停止往左看for(inti=1;i<arr.length;i++){//j=i表示从i位置开始，j--表示往前看for(intj=i;j>0;j--){if(arr[j]<arr[j-1]){inttemp=arr[j-1];arr[j-1]=arr[j];arr[j]=temp;}}System.out.println("从"+i+"位置往前看，直到左边的数不比自己大，本次结果："+Arrays.toString(arr));}}}运行结果：
从1位置往前看，直到左边的数不比自己大，本次结果：[15,18,13,17,6,20,15,9]从2位置往前看，直到左边的数不比自己大，本次结果：[13,15,18,17,6,20,15,9]从3位置往前看，直到左边的数不比自己大，本次结果：[13,15,17,18,6,20,15,9]从4位置往前看，直到左边的数不比自己大，本次结果：[6,13,15,17,18,20,15,9]从5位置往前看，直到左边的数不比自己大，本次结果：[6,13,15,17,18,20,15,9]从6位置往前看，直到左边的数不比自己大，本次结果：[6,13,15,15,17,18,20,9]从7位置往前看，直到左边的数不比自己大，本次结果：[6,9,13,15,15,17,18,20]原文：juejin.cn/post/7128721614144798750