前言
无论是今后的面试还是笔试，排名都在数据结构和算法中占有重要的地位，所以我决定好好写数据结构这个主题，进一步研究。 今天和大家一起学习交换类排行榜——冒泡和快速排行榜的详细信息！
排行榜上最考察的是冒泡和快速排序，当然执行上的冒泡要比快速排序简单得多。 理解可以说是最简单的排序算法，早排很多面试笔试都要求手撕，所以重要性不言而喻！ 当然，关于排序算法，我一开始接触学习的时候，只是萌萌哒地了解了一下，大概知道，背模板，快排队手写，刷题。 后来我意识到我是个笨蛋。java中有Arrays.sort ) )这个api，为什么我可以直接调用愚蠢的手写？ 明明重新排列多个条件重新改写comparator界面就OK了，为什么还要愚蠢的手写？ 从此，走上了没有手写的早排的不归路。
后来，渐渐地，这个序列思想很少被使用，被我的成功所遗忘。 现在，请重新被我捡起来，深入了解，不要让那位大人物有一天再牵着我的手丢脸。 把学习过程分享给大家。
冒泡排序
介绍
冒泡排序也称为起泡排序。 他是基于交换的序列的典型，也是早排思想的基础。 关于泡沫排序名字的由来，百度百科是这样说的：这个算法名字的由来是，元素越小，通过交换就会慢慢地“漂浮”在数列的最上面。 为了让碳酸饮料中的二氧化碳气泡最终浮在最上面，名字是“冒泡排序”。
当然，泡沫排序是一种稳定的排序算法，时间复杂度为o(n^2^ )。 基本的想法是从前到后调整大要素(或从后到前调整小要素)。
分析
具体思想是(后面调整大要素) :从第一个元素往后跑，判断每个位置是否比后面的元素大。 如果大于后面的元素，则更换两个大小，然后向后移动。 如果不是，就这样往后走。 这样的话，进行一个回合后，保证最大的数量被更换到最后的位置。 那么，第二次也同样从开始向后判断前进，如果现在位置比后面的位置大，就换他后面的数量。 但是，请注意一点。 这次不需要判断到最后。 判断到倒数第二个位置就行了。 (因为首先确定了最大的是倒数第一个，所以这次的目的是确定倒数第二个。 )同样地，在第一个要素将整个要素有序化之前，之后的操作也是如此。 举个例子，例如用2、8、9、3、7、6、12、4这种排列的泡沫排序来说。 有多次(7)重新排列，每次必须执行多次(8-k )。 最初的排序如下所示。
多次排序的结果如下所示。
动态执行的顺序如下。
代码
具体实现的时候，要弄清楚是从小到大，还是从小到大，另外也要注意次数，注意越界。 气泡排序的键码如下所示。私人建筑委员会(int [ ] a ) {
//todo auto -生成方法
for (英寸=长度- 1； i=0； I---- )
{
for(intj=0； ji； j )日本
{
if(a[j]>a[j+1]) { int team=a[j]; a[j]=a[j+1]; a[j+1]=team; } } } }快速排序
介绍
快速排序是对冒泡排序的一种改进，采用递归分治的方法进行求解。而快排相比冒泡是一种不稳定排序,时间复杂度最坏是O(n^2^),平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)。
分析
对于快排来说，基本思想是这样的
快排需要将序列变成两个部分，就是序列左边全部小于一个数，序列右面全部大于一个数，然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。
其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。但是通常我们取最左边的那个数。当然，为了实现这个目标，实现方式可能不一样，但是我这里采取的是大众常规的方式和方法。！
这里的一个难题就是如何处理将比第一个数K小的全部放左面，把比K大的全部放右面！如果没有什么技巧，直接硬性往里面塞，你肯定要一个额外存储空间先把整个先存了。然后遍历比较然后放入目标区域。当然这样太浪费空间内存了。我们为了节省计算机资源，采取这样的方法：
先用一个空间标记这个最左侧的数K。然后先从右往左high--先找到一个比这个K小的数a[high]，把这个a[high]放到a[low]位置(因为这个a[low]的初始K已经被额外空间记录过，不用担心)。这样右侧不符合要求小于K的已经调到最左侧了，我们再从左侧向右low++一直到a[low]>K.也就是找到第一个比K大的数，它在左侧不符合要求所以我们把它移动到右侧，而我们刚刚所说的a[high]已经被赋值移到左侧，所以我们把这个a[low]大于K的数值移动到右端a[high]处，这样又保证high右侧全部大于K，low左侧全部小于K。就又开始重复第一步啦一直到low>high为止(即所有左侧都小于K，右侧都大于K)。对于一个序列的2,8,3,7,6,9,4,12来说，它的执行过程图解大致是这样的：1 . 首先2是最小的，采用递归分治时候左侧相当于为空，只需要把右侧再进行排序。
2 .对于右侧序列来说，先用K储存a[low]=8我们先从右侧找到第一个小与8的数字4。
3 .我们将它放到low位置替换，然后从low位置向右找到第一个大于k=8的再同样放到右侧。我们找到9，把9赋值给high位置。
4 .重复上面步骤直到high
5 .就这样重复下去，直到整个序列有序即可！
代码
在书写代码的时候，要注意一些顺序，防止数组越界情况，可以写好debug一遍其实就很好理解了！当写代码遇到错误时候，不要急着就去找正确答案，能有时间自己发现错误，可以借助断点查看程序执行流程，这样对自己的收益是最大的！至于快排的代码，是这样的：
private static void quicksort(int [] a,int left,int right) { int low=left; int high=right; //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！ if(low>high)//作为判断是否截止条件 return; int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。 while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。 { while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止 { high--; } //这样就找到第一个比它小的了 a[low]=a[high];//放到low位置 while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置 { low++; } a[high]=a[low]; } a[low]=k;//赋值然后左右递归分治求之 quicksort(a, left, low-1); quicksort(a, low+1, right); }测试与总结
对于完整的代码，为
package 八大排序; import java.util.Arrays; public class 交换类排序 { public static void main(String[] args) { int a[]= {2,8,9,3,7,6,12,4}; xydcc(a); System.out.println(Arrays.toString(a)); int b[]= {2,8,9,3,7,6,12,4}; quicksort(b, 0, b.length-1); System.out.println(Arrays.toString(b)); } private static void xydcc(int[] a) { // TODO Auto-generated method stub for(int i=a.length-1;i>=0;i--) { for(int j=0;j<i;j++) { if(a[j]>a[j+1]) { int team=a[j]; a[j]=a[j+1]; a[j+1]=team; } } } } private static void quicksort(int [] a,int left,int right) { int low=left; int high=right; //下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！ if(low>high) return; int k=a[low];//取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。 while(low<high) { while(low<high&&a[high]>=k) { high--; } //这样就找到第一个比它小的了 a[low]=a[high]; while(low<high&&a[low]<=k) { low++; } a[high]=a[low]; } a[low]=k; quicksort(a, left, low-1); quicksort(a, low+1, right); } }运行结果：
好了这个交换类排序就总结到这里了。总之，冒泡是很基础和容易，但是要注意这种简单排序所属的范畴(交换类)要和插入类等做好区分；而快排板子很好记，深入理解需要点时间消化吧。一次不行再来第二次，不行再来第三次，。。。
当然，如果感觉不错或者对你有所帮助，欢迎点赞收藏转发哈！如果感觉有问题或者纰漏还请指正哈！当然，笔者长期致力于<<数据结构与算法>>这个专栏的更新和维护，欢迎大家关注一波哈！
最后，欢迎关注笔者微信公众号(bigsai)，头条号(一直码农一直爽)！