前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏这篇博客会解析3个进阶的排序算法堆排序、快速排序、归并排序这3种排序的效率是要优于上篇博客中解析的4个基础排序算法的都是很有实用价值的很多标准库中的排序算法都是基于这几个算法来实现的Java中的Arrays.sort()方法就是快速排序的改进版本Collections.sort()方法就是归并排序中的改进版本这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1堆排序注学习堆排序需要的前提是掌握堆相关的知识要掌握向下调整、建堆操作的原理并且会写代码这些知识在数据结构专栏的堆博客中都有详细的解析想复习下的铁汁可以看下链接如下堆博客链接要对数组进行升序排序利用堆就可以这样做对数组的元素进行建堆操作循环的删除堆顶元素删除的时候不是直接删除而是和最后一个元素交换顺序这样当前堆的最大值就来到了数组的最后一个位置heapSize- -堆的元素个数减去1数组的长度仍然不变换到堆顶的那个元素从[0]位置开始向下调整调整后仍然满足堆的性质接着重复第2步和第3步的过程直到heapSize的值减小为1画图来模拟下这个过程下图中是一个大堆交换堆顶元素9和堆的最后一个元素2heapSize–再对堆顶元素进行向下调整如下图用红色框圈住的就是已经排好序的元素不用再管了数组最后一个元素就是2交换堆顶元素8和元素2的位置交换后再进行向下调整以此类推最后heapSize等于1的时候交换堆顶元素和堆的最后一个元素交换上来后这时候堆中已经没有元素了堆顶元素也就不需要向下调整就排好序了堆排序方法需要先写个shiftDown和createHeap方法下面只会简单的解析下代码感觉这部分比较抽象的铁汁推荐先看上篇堆博客复习一下里面有这两个方法的超详细解析代码逻辑如下shiftDown方法传入3个参数数组arr堆的长度size注意是堆的长度不是堆的最大下标要进行向下调整的元素的下标index当前要进行向下调整的元素就是父结点parent用child parent 1计算出左子结点的下标这里我们要建的是大堆就找到parent左右子结点中的最大值跟arr[parent]比较如果arr[parent]更小就交换父结点和子结点的位置交换parent和child的位置后新的parent就变成了原来的child计算出新的child继续重复这一步骤直到arr[parent] arr[child]或者parent已经没有左右子结点了也就是parent变成了叶子结点也就是child size了publicstaticvoidshiftDown(int[]arr,intsize,intindex){intparentindex;intchild2*parent1;while(childsize){if(child1sizearr[child]arr[child1]){childchild1;}if(arr[parent]arr[child]){break;}else{inttmparr[parent];arr[parent]arr[child];arr[child]tmp;parentchild;child2*parent1;}}}在createHeap方法中先找到二叉树中的最后一个非叶子结点在数组中从后往前对这些结点进行向下调整就能得到一个堆publicstaticvoidcreateHeap(int[]arr){intlastLeafarr.length-1;intlastParent(lastLeaf-1)/2;for(intilastParent;i0;i--){shiftDown(arr,arr.length-1,i);}}在heapSort方法中先调用createHeap方法去构建出一个堆初始时[0,bound]就是未排序区间bound的值为arr.length - 1写个for循环每次排序后bound的值减1直到bound的值减为0就排好序了shiftDown的第二参数传入的是堆的长度而bound表示的是下标下标是比长度要小1的这里删除堆顶元素后直接传入bound刚好就相当于堆的长度减去1最后一轮只需要交换位置已经不需要向下调整了传入bound值为0进入shiftDown方法中就不会进入while循环publicstaticvoidheapSort(int[]arr){createHeap(arr);for(intboundarr.length-1;bound0;bound--){inttemparr[0];arr[0]arr[bound];arr[bound]temp;shiftDown(arr,bound,0);}}如果数组需要升序排序就使用大堆需要降序排序就使用小堆因为每次都是把堆顶的极值放到最后作为已排序的区间计算下堆排序的时间复杂度堆顶元素和堆的最后一个元素交换新的堆顶元素再向下调整每次调整时间复杂度为O(logN)总共交换了N次元素时间复杂度就是O(NlogN)建堆操作的时间复杂度是O(N)合起来就是NlogN N因为计算时间复杂度只看最高项所以堆排序的时间复杂度就是O(NlogN)堆排序操作都是在数组上进行的空间复杂度就是O(1)堆排序属于不稳定排序因为建堆和向下调整操作会使值相同的元素不知道被安排到哪里最终出堆的顺序是无法预测的O(NlogN)这个时间复杂度是非常优秀的像冒泡排序、插入排序、直接选择排序的时间复杂度都是O(N ^ 2)希尔排序进行了优化也只是优化到了O(N ^ 1.5)随着N的增大logN的变化是非常非常小的堆排序算是一个非常高效的算法2快速排序快速排序属于实际开发中最主要的排序算法也是面试中最常考的排序算法快速排序采用的思想是分治假如要对数组进行升序排序步骤如下给定一个待排序的数组从数组中选择一个“基准值”拿着这个数组的每个元素和基准值进行比较把数组整理成三个部分左侧比基准值小的元素中间基准值右侧比基准值大的元素递归的进行这个过程在左侧区间中再选择一个基准值把左侧区间也整理成左侧 中间 右侧三个部分右侧区间也是如此当递归到一定程度也就是区间足够小的时候有序性就可以保证了例如区间中剩下三个元素了选择基准值进行整理后发现一个在左侧一个在右侧或者区间中剩下两个元素选择基准值进行整理另一个元素在区间的左侧或者右侧当所有小的区间都有序了那整个数组元素就也有序了那具体在代码细节上如何处理有三种方法这三种方法的时间、空间复杂度是完全相同的区别只在分区过程Hoare法Hoare是发明快速排序的大佬的名字这个是最经典、使用最多的写法快速排序的朴素写法就是Hoare法挖坑法前后指针法不推荐使用理解成本比较高甚至面试中写出这个版本面试官都可能看不懂是啥意思首先解析下Hoare法如下图要把数组进行升序排序选择数组最右侧的元素作为基准值基准值就是6再搞个left引用和right引用left引用从前往后走找到第一个比基准值大的元素right引用从后往前走找到第一个比基准值小的元素如果两个引用都找到了符合要求的元素那就交换两个元素的位置如下图接着left和right继续匹配符合要求的元素如果都能匹配到符合要求的元素那就继续交换也可能两个引用会重合如下图如果两个引用位置重合就说明找完了就把重合位置的元素和后面基准值位置的元素进行交换这时候以6为基准值6的左区间的元素都小于66的右区间的元素都大于6再对基准值6的左右区间递归进行这个过程先看左区间用最右侧元素2作为基准值right是匹配不到小于2的元素的就会在元素3下方和left重合交换重合位置和基准值位置的元素这时候就满足2左区间的元素小于2右区间的元素大于2再递归的对2的左右区间的元素进行这个过程2的左区间为空就直接跳过在2的右区间中以3作为基准值left和right重合在元素5的位置交换3和5的位置这个区间就符合升序要求了对6的右区间也递归进行该过程整个数组就是有序的了对于一些特殊情况使用这种方法也是可以的就比如基准值恰好是数组中的最大值这时候left移动时就会一直移动到基准值的位置区间边界位置也没有找到比基准值大的元素接着right从基准值的位置开始准备向前移动发现left和right重合了riight就不移动了交换基准值和重合位置元素的位置相当于还是没有交换选用最左侧元素和最右侧元素作为基准值的区别如下这里我们选择用最右侧元素作为基准值就是因为在找的时候先让left从前往后找大于基准值的元素再让right从后往前找小于基准值的元素一旦left和right重合那重合位置的元素值是大于基准值的在特殊情况下会等于交换后重合元素的位置交换到了基准值的右侧是符合升序规则的那如果选用最左侧元素作为基准值就需要让right先从后往前移动匹配到比基准值小的元素再让left从前往后移动匹配比基准值大的元素这样left和right重合位置的元素是小于基准值的特殊情况也会等于交换后重合元素的位置交换到了基准值的左侧是符合升序规则的还要根据降序和升序排序判断下是让left先扫描还是让right先扫描如果是降序排序那就要left从前往后找小于基准值的元素right从后往前找大于基准值的元素都匹配到就交换位置如果选择最右侧元素作为基准值那就要确保left和right重合的位置是小于基准值元素的就让left先走这个规则搞懂了不管是升序还是降序选择最前面还是最后面的元素作为基准值都能够分析清楚代码怎么写代码逻辑如下quickSort方法搞两个重载方法一个里面传入的是数组arr用于在main方法中调用使用另一个里面传入arrleftright因为要递归对子区间进行快速排序这里比较推荐使用左闭右闭的方式来写代码也就是要排序的区间的范围是[leftright]铁汁们这里如果写成左闭右开的话就会稍微麻烦一些在quickSort三个参数的方法中先判定一下如果left小于等于right就说明当前区间为空或者只有一个元素已经有序了就直接return再写个partition方法移动left和right交换元素位置的步骤就在这个方法中方法的返回值是int返回最终交换位置后基准值的下标还要写个swap方法负责交换数组中元素的位置在partition方法中调用swap方法交换数组元素publicstaticvoidquickSort(int[]arr){quickSort(arr,0,arr.length-1);}publicstaticvoidquickSort(int[]arr,intleft,intright){if(leftright){return;}intindexpartition(arr,left,right);quickSort(arr,left,index-1);quickSort(arr,index1,right);}publicstaticintpartition(int[]arr,intleft,intright){intvaluearr[right];intlleft;intrright;while(lr){while(lrarr[l]value){l;}while(lrarr[r]value){r--;}swap(arr,l,r);}swap(arr,l,right);returnl;}publicstaticvoidswap(int[]arr,intl,intr){inttemparr[l];arr[l]arr[r];arr[r]temp;}分析下快速排序的时间复杂度快速排序的平均时间复杂度是O(NlogN)但最坏情况下时间复杂度为O(N ^ 2)当要排序的数组刚好是反序的时候就是最坏情况如下图要对数组中的元素进行升序排序选择1作为基准值left和right移动left定位到9的位置right移动到9处跟left重合9和1交换位置这时候1的左区间为空接着开始对1的右区间进行排序以9作为基准值left会一直移动到9处和right重合9的位置就不需要动9的右区间为空对9的左区间进行排序选择2作为基准值left定位到8的位置right一直往前移动直到跟left重合交换2和8的位置这时候left的左区间为空写几步就能发现规律这种情况下每次递归时区间的长度只减小了1因此整体的时间复杂度就是O(N ^ 2)这种情况下每次排序后基准值左区间或者右区间就会为空接着分析下空间复杂度可能有的铁汁会觉得代码中没有额外创建数组什么的因此空间复杂度就是O(1)但快速排序是通过递归来实现的递归中每次方法的调用都会产生出一系列的栈帧这都是占用空间的那就要分析递归的深度是多少平均情况下每次递归的区间会缩小一半空间复杂度就是O(logN)最坏情况下也就是刚好数组是反序时每次递归区间的长度只会减去1空间复杂度就是O(N)快速排序可以从三个方面来进行优化极端情况出现的原因就是取基准值取到了当前区间中的最值导致操作后区间并没有缩小很多可能有的铁汁会想到算中位数或者平均值作为基准值但是计算本身也是有开销的就可以使用三数取中法代码简单效率高对于待排序区间取出最左侧元素中间位置元素最右侧元素用这三个元素的中间值作为基准值这个中间值元素再放到区间最右侧当快速排序递归到一定程度时每个子问题已经比较小了继续递归虽然可以解决问题但可能仍然要递归很多次如果待排序区间比较小的话就可以通过插入排序来解决问题速度特别快例如要走1000KM肯定飞机快但是走1KM就是汽车快因为这么短的距离飞机在天上微调1KM效率也不高如果针对特别大的数组进行快速排序递归深度就可能很高如果发现递归深度到了一定值以后就可以使用堆排序针对分出来的每个区间直接进行堆排序一步到位C标注库中的sort方法就是这样搞的根据具体情况切换排序方法在平均情况下快速排序的效率是更高的因为堆排序需要更多次比较和移动元素但是堆排序的时间复杂度比较稳定快速排序是通过递归来实现的面试时为了考察代码能力可能会考如何非递归的实现快速排序非递归就是用栈来模拟递归过程递归的过程就是在倒腾待排序区间的下标创建一个Range类表示区间的范围在栈中存储Range对象元素出栈子区间入栈就可以模拟递归过程publicstaticvoidquickSortByLoop(int[]arr){StackRangestacknewStack();stack.push(newRange(0,arr.length-1));while(!stack.isEmpty()){Rangerangestack.pop();if(range.leftrange.right){continue;}intindexpartition(arr,range.left,range.right);stack.push(newRange(range.left,index-1));stack.push(newRange(index1,range.right));}}publicclassRange{publicintleft;publicintright;publicRange(intleft,intright){this.leftleft;this.rightright;}}3归并排序在前面的链表博客中解析过这样一个题目就是给出两个有序链表将两者合并成一个有序链表归并排序也是这样只是把两个有序的数组合并成了一个有序的数组归并排序使用了分治思想把待排序的数组分成两份称为A和B此时A和B大概率是无序的就继续拆分把A拆分为C和D把B拆分为E和F以此类推当拆出的两个数组长度为1时这两个数组就是有序数组了就可以直接合并得到了长度为2的有序数组简单来说就是在分治过程中把长度为N的数组拆分为N个长度为1的数组把这些长度为1的数组两两合并就得到了N / 2个长度为2的数组把这些长度为2的数组两两合并就得到了N / 4个长度为4的数组把这些长度为4的数组两两合并就得到了N / 8个长度为8的数组当子数组的长度为1时就开始合并代码逻辑如下mergeSort方法搞两个版本一个参数是arr用于main方法中直接调用另一个参数是arrleftright表示要进行归并排序的区间在有三个参数的mergeSort方法中把当前区间分成两份再对左右区间继续递归的进行排序左右区间排序完成后调用merge方法来合并两个有序区间merge就是将两个有序数组合并为一个有序数组传入四个参数arrleftmidright当然这个mid也可以不传根据传入的left和right计算一下即可再创建一个数组result用于将两个数组进行合并merge方法中搞两个引用cur1和cur2分别指向两个有序数组第一个元素的位置初始时cur1就等于leftcur2就等于mid 1接着对比arr[cur1]和arr[cur2]的大小将较小的存储到result中接着cur1或者cur2写在while循环中当两个有序数组引用走到末尾就结束while循环结束while循环后两个已排序数组一定会有一个数组的引用没有走到末尾这个数组后面的元素值比较大直接把这些元素加到result数组的末尾result数组这时候就已经完成两个有序数组的合并了还要再赋值给arr数组publicstaticvoidmergeSort(int[]arr){mergeSort(arr,0,arr.length-1);}publicstaticvoidmergeSort(int[]arr,intleft,intright){if(leftright){return;}intmid(leftright)/2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);merge(arr,left,mid,right);}publicstaticvoidmerge(int[]arr,intleft,intmid,intright){int[]resultnewint[right-left1];intresultSize0;intcur1left;intcur2mid1;while(cur1midcur2right){if(arr[cur1]arr[cur2]){result[resultSize]arr[cur1];resultSize;cur1;}else{result[resultSize]arr[cur2];resultSize;cur2;}}while(cur1mid){result[resultSize]arr[cur1];resultSize;cur1;}while(cur2right){result[resultSize]arr[cur2];resultSize;cur2;}for(inti0;iresult.length;i){arr[lefti]result[i];}}接着分析下时间复杂度归并排序就不存在什么最坏情况了每次都是把区间分成两份递归的次数是和logN相关的时间复杂度就是O(NlogN)发挥是比快速排序稳定的因为在合并区间时创建一个result数组所以时间复杂度就是O(N)归并排序属于是稳定排序因为不涉及大范围的元素交换在合并时如果arr[cur1]和arr[cur2]的值相同就把arr[cur1]的值先加入到result中if(arr[cur1]arr[cur2]){result[resultSize]arr[cur1];resultSize;cur1;}非递归版本的归并排序就不需要使用栈来模拟递归过程了本质上就是把长度为1的空间进行两两合并长度为2的空间进行两两合并以此类推就可以直接用两层for循环来实现代码逻辑如下外层循环中的size表示要合并的数组的大小size的初始值是1接着每次size都乘以2也就是先合并长度为1的数组再去合并长度为2的数组以此类推内存循环就是完成合并操作i的初始值是0要合并的区间就是[ii size - 1]和[i sizei 2 * size - 1]每次i的值加上size * 2left或者right的值是有可能超过arr.length - 1的超过的话就直接值等于arr.length - 1即可后面传入到merge方法中是可以正确的排序的publicstaticvoidmergeSortByLoop(int[]arr){for(intsize1;sizearr.length;size*2){for(inti0;iarr.length;isize*2){intlefti;intmidisize-1;intrighti2*size-1;if(leftarr.length-1){leftarr.length-1;}if(rightarr.length-1){rightarr.length-1;}merge(arr,left,mid,right);}}}归并排序有两大优点归并排序是可以针对链表进行高效排序的堆排序/快速排序只能针对数组不能针对链表进行排序因为堆排序中的向上和向下调整是非常依赖数组下标的快速排序中right和left引用移动匹配符合要求的值在单链表中是不支持从右往左扫描的归并排序对于海量数据也是能够处理的例如有1000GB的数据需要排序没办法都加载到内存中进行排序就可以先取出两个1GB文件合并成一个2GB的文件再存到硬盘中同时就可以把之前两个1GB的文件删掉以此类推外部排序效率是很低的最后合并两个500G的时候每次只能读取一小块来合并要读取很多次结语这三种排序总结如下堆排序先建堆再循环的删除堆顶元素也就堆顶元素和堆的最后一个元素交换位置堆的长度减去1时间复杂度O(NlogN)空间复杂度O(1)稳定性不稳定建堆和向下调整的过程中值相同的元素的先后顺序无法预测快速排序选定基准值分为左区间基准值右区间三个部分当递归到区间足够下的时候数组整体就有序了时间复杂度平均为O(NlogN)最坏为O(N ^ 2)空间复杂度平均为O(logN)最坏为O(N)稳定性不稳定partition方法远距离交换元素位置时可能会打乱值相同元素的先后顺序归并排序一直拆分数组直到子树组的长度为1接着把子树组进行两两合并合并为有序数组时间复杂度O(NlogN)空间复杂度O(N)稳定性稳定这篇博客解析了3种进阶排序算上排序一中解析的4种基础排序一共是7种冒泡、插入、直接选择、希尔、堆、快速、归并排序无论是408还是就业面试都是高频考点所以初学的铁汁一定要搞清楚原理多写几次代码.以上就是今天的所有内容啦完结撒花