高级排序算法之快速排序

　　前言
　　今天继续算法学习，本次学习的是高级排序之快速排序。本文代码部分存在调用公共方法，可在文章：简单排序算法之冒泡、插入和选择排序Java实现版，高级排序之归并排序、希尔排序。中查找相关方法，另外，本文也提供测试时使用的完整代码，对其他算法不感兴趣，可在文末找到完整源代码。快速排序
　　快速排序的本质就是把一个数组划分为两个子数组，然后递归地调用自身为每一个数组进行快速排序来实现的。这里就涉及一个问题：如何划分？
　　在快速排序中，为了划分数组，提出了枢纽这个词，它代表待排序序列中的一个数据项。快速排序利用枢纽将数组划分成两部分，一部分（枢纽左侧）是所有小于该枢纽表示的数据项，另一部分（枢纽右侧）则都大于该枢纽表示的数据项（注意，此时左右两侧的数据项是无序的），枢纽放置在左右两侧的中间，此时该枢纽已经处在排序的正确位置上了（枢纽是快速排序所排序的对象，实现排序的关键点就是调整枢纽的位置）。通过递归的这样划分，最终出现左侧只有一个数据项（该数据项既是左侧子数组又是枢纽），则结束左侧递归，开始划分右侧数组以此类推。这里又产生了一个问题，如何选择枢纽？
　　选择枢纽的算法：最简单的选择枢纽算法就是每次递归都选择数组的最后一个数据项做为枢纽（或者选择最左侧的数据项作枢纽）。
　　上图演示了以子数组最右侧数据项做枢纽的排序过程代码演示（枢纽始终使用子数组的最右侧数据项）privatestaticintpartitionIt（intleft，intright，intpivot，int〔〕array）｛intleftPtrleft1；intrightPwhile（true）｛查找左侧子数组大于枢纽的位置while（compare（array〔leftPtr〕，pivot）0）｛｝查询右侧子数组小于枢纽的位置while（rightPtr0compare（array〔rightPtr〕，pivot）0）｛｝if（leftPtrrightPtr）｛｝交换需要调整位置的两个数据项swap（leftPtr，rightPtr，array）；｝将枢纽挪到两侧中间swap（leftPtr，right，array）；returnleftP｝privatestaticvoidrecQuickSort（intleft，intright，int〔〕array）｛if（rightleft0）｛｝选择的枢纽intpivotarray〔right〕；intpartitionpartitionIt（left，right，pivot，array）；recQuickSort（left，partition1，array）；recQuickSort（partition1，right，array）；｝publicstaticvoidquickSort（int〔〕array）｛compareCount0；swapCount0；longstartnewDate（）。getTime（）；recQuickSort（0，array。length1，array）；longendnewDate（）。getTime（）；printResult（快速排序，交换次数，start，end）；｝运行结果
　　冒泡排序比较次数：49995000，交换次数：25153125，耗时：173毫秒
　　选择排序比较次数：49995000，交换次数：9987，耗时：65毫秒
　　插入排序比较次数：25075792，复制次数：25075793，耗时：42毫秒
　　归并排序比较次数：120459，复制次数：267232，耗时：3毫秒
　　希尔排序比较次数：233896，复制次数：238266，耗时：5毫秒
　　对随机序列排序：快速排序比较次数：165181，交换次数：31700，耗时：3毫秒
　　对逆序序列排序：快速排序比较次数：49825881，交换次数：9976，耗时：54毫秒
　　从运行结果中，可以看到对于随机序列，快速排序算法执行速度是非常快的，和归并排序相同，但给逆序序列排序时，效果则非常差，几乎和选择排序一样的效率了。那这是为什么呢？
　　根本原因，就在于枢纽的选择上，快速排序期望枢纽能够将数组拆分成两个长度几乎相同的子数组，这样能最优的平衡比较次数和交换次数。对于随机序列，简单的选择最右侧数据项做为枢纽不至于频繁出现左右子数组极度不平衡的情况，而对于逆序序列，则几乎每次划分都是极度不平衡的两个子数组，最终导致较大侧的子数组要被划分更多次。优化枢纽选择算法
　　快速排序的最优划分结果是划分的两个数组长度相等，为了达到这个目的，我们每次都要在划分前，先找到子数组的中间数据项吗？显然，不能这么做的，因为很可能你找中值的时间远远大于你排序的时间了。所以，我们只能选择一个实现既不是过于复杂，又比选择最右侧数据项做为枢纽的算法更具普适性。
　　上图所示取枢纽的方法叫三数据项取中，即从数组中选择第一个、最后一个以及中间的数据项，从这三个数据项中取出大小在中间的项做为枢纽，在选择过程中，我们实际上也对这三个数据项做了排序，那顺便把分别大于、小于枢纽的那两个数据项也放到正确的位置（即左侧小于枢纽，右侧大于枢纽）。
　　该方法每次划分都需要至少有三个数据项，所以当子数组项数不大于3个的时候，就可以结束递归划分了，此时的排序可以通过其他排序算法实现，如使用手动排序（待排序的数据项不大于3个，所以手动排序完全可以轻松搞定），也可以使用插入排序（如果使用插入排序，我们甚至可以当数据项不大于10（这个10没有具体意义，你也可以20、30）的时候就可以用插入排序来收尾了）。下面我们用该方法来选择枢纽（用插入排序来收尾），对代码进行修改。代码演示privatestaticintmedianOf3（intleft，intright，int〔〕array）｛intcenter（leftright）2；if（array〔left〕array〔center〕）｛swap（left，center，array）；｝if（array〔left〕array〔right〕）｛swap（left，right，array）；｝if（array〔center〕array〔right〕）｛swap（center，right，array）；｝swap（center，right1，array）；returnarray〔right1〕；｝privatestaticvoidinsertSort（intleft，intright，int〔〕array）｛for（intileft1；i）｛inttemparray〔i〕；右移数字，实现cur下标的左侧都是有序的while（cur0compare（temp，array〔cur1〕）0）｛copy（cur1，cur，array）；｝如果curi则说明数据项已经在正确的位置了，不需要进行交换if（cur！i）｛不满足temp0）｛｝if（leftPtrrightPtr）｛｝交换需要调整位置的两个数据项swap（leftPtr，rightPtr，array）；｝将枢纽挪到两侧中间swap（leftPtr，right1，array）；returnleftP｝privatestaticvoidrecQuickSort（intleft，intright，int〔〕array）｛intsizerightleft1；if（size10）｛insertSort（left，right，array）；｝else｛intmedianmedianOf3（left，right，array）；intpartitionpartitionIt（left，right，median，array）；recQuickSort（left，partition1，array）；recQuickSort（partition1，right，array）；｝｝publicstaticvoidquickSort（int〔〕array）｛compareCount0；swapCount0；longstartnewDate（）。getTime（）；recQuickSort（0，array。length1，array）；longendnewDate（）。getTime（）；printResult（快速排序，交换次数，start，end）；｝运行结果
　　冒泡排序比较次数：49995000，交换次数：25138570，耗时：170毫秒
　　选择排序比较次数：49995000，交换次数：9990，耗时：65毫秒
　　插入排序比较次数：25069178，复制次数：25069176，耗时：34毫秒
　　归并排序比较次数：120483，复制次数：267232，耗时：2毫秒
　　希尔排序比较次数：231598，复制次数：235991，耗时：6毫秒
　　对随机序列排序：快速排序比较次数：154857，交换次数：44570，耗时：3毫秒
　　对逆序序列排序：快速排序比较次数：188034，交换次数：20067，耗时：1毫秒
　　从执行结果可以看出，优化过枢纽选择算法后，无论是随机序列排序还是逆序序列排序，排序速度都非常快。
　　至此，本文结束完整代码packageteam。ngup。importjava。util。Aimportjava。util。Dimportjava。util。concurrent。ThreadLocalRauthorzwwdate20228410：35publicclassSortStudy｛staticfinalintARRAYSIZE10000；staticintcompareCount0；staticintswapCount0；生成随机数数组returnpublicstaticint〔〕buildRandomArray（）｛int〔〕arraynewint〔ARRAYSIZE〕；for（inti0；iARRAYSIZE；i）｛intrandomWithThreadLocalRandomThreadLocalRandom。current（）。nextInt（0，1000000）；array〔i〕randomWithThreadLocalR｝｝a和b位置的数据交换paramaparambparamarraypublicstaticvoidswap（inta，intb，int〔〕array）｛swapCinttemparray〔a〕；array〔a〕array〔b〕；array〔b〕｝复制位置abparamaparambparamarrayprivatestaticvoidcopy（inta，intb，int〔〕array）｛swapCarray〔b〕array〔a〕；｝复制数值a位置bparamaparambparamarrayprivatestaticvoidcopyData（inta，intb，int〔〕array）｛swapCarray〔b〕a；｝dataa大于datab返回1，否则返回1paramdataaparamdatabreturnpublicstaticintcompare（intdataa，intdatab）｛compareCif（dataadatab）｛return1；｝return1；｝输出排序结果paramname排序方法名paramoperName交换复制paramstart开始时间paramend结束时间privatestaticvoidprintResult（Stringname，StringoperName，longstart，longend）｛System。out。print（name比较次数：compareCount，operName：swapCount，耗时：（endstart）毫秒）；｝冒泡排序publicstaticvoidmaopao（int〔〕array）｛compareCount0；swapCount0；待排序序列长度，intlengtharray。longstartnewDate（）。getTime（）；while（length0）｛for（inta0；alength1；a）｛if（compare（array〔a〕，array〔a1〕）0）｛交换位置swap（a，a1，array）；｝｝一次从头到尾的遍历，找出了最右端的值（最大值），这将缩短第二次遍历的序列长度｝longendnewDate（）。getTime（）；输出排序结果printResult（冒泡排序，交换次数，start，end）；｝选择排序publicstaticvoidxuanze（int〔〕array）｛compareCount0；swapCount0；intlength0；longstartnewDate（）。getTime（）；while（length！array。length1）｛最小值位置intminPosition1；最小值intminarray〔length〕；for（intilength1；iarray。i）｛if（compare（array〔i〕，min）0）｛minarray〔i〕；minP｝｝存在比当前值还要小的值，则进行位置对换，否则无需对调位置if（minPosition！1）｛交换位置swap（length，minPosition，array）；｝｝longendnewDate（）。getTime（）；printResult（选择排序，交换次数，start，end）；｝插入排序publicstaticvoidcharu（int〔〕array）｛swapCount0；compareCount0；第一次排序无需比较，所以直接从1开始longstartnewDate（）。getTime（）；for（inti1；iarray。i）｛inttemparray〔i〕；右移数字，实现cur下标的左侧都是有序的while（cur0compare（temp，array〔cur1〕）0）｛copy（cur1，cur，array）；｝如果curi则说明数据项已经在正确的位置了，不需要进行交换if（cur！i）｛不满足temp0）｛for（outerh1compare（array〔innerh〕，temp）0）｛copy（innerh，inner，array）；｝copyData（temp，inner，array）；｝h（h1）3；｝longendnewDate（）。getTime（）；printResult（希尔排序，复制次数，start，end）；｝快速排序privatestaticintmedianOf3（intleft，intright，int〔〕array）｛intcenter（leftright）2；if（compare（array〔left〕，array〔center〕）0）｛swap（left，center，array）；｝if（compare（array〔left〕，array〔right〕）0）｛swap（left，right，array）；｝if（compare（array〔center〕，array〔right〕）0）｛swap（center，right，array）；｝swap（center，right1，array）；returnarray〔right1〕；｝privatestaticvoidinsertSort（intleft，intright，int〔〕array）｛for（intileft1；i）｛inttemparray〔i〕；右移数字，实现cur下标的左侧都是有序的while（cur0compare（temp，array〔cur1〕）0）｛copy（cur1，cur，array）；｝如果curi则说明数据项已经在正确的位置了，不需要进行交换if（cur！i）｛不满足temp0）｛｝if（leftPtrrightPtr）｛｝交换需要调整位置的两个数据项swap（leftPtr，rightPtr，array）；｝将枢纽挪到两侧中间swap（leftPtr，right1，array）；returnleftP｝privatestaticvoidrecQuickSort（intleft，intright，int〔〕array）｛intsizerightleft1；if（size10）｛insertSort（left，right，array）；｝else｛intmedianmedianOf3（left，right，array）；intpartitionpartitionIt（left，right，median，array）；recQuickSort（left，partition1，array）；recQuickSort（partition1，right，array）；｝｝publicstaticvoidquickSort（int〔〕array）｛compareCount0；swapCount0；longstartnewDate（）。getTime（）；recQuickSort（0，array。length1，array）；longendnewDate（）。getTime（）；printResult（快速排序，交换次数，start，end）；｝publicstaticvoidmain（String〔〕args）｛int〔〕arraybuildRandomArray（）；int〔〕array2Arrays。copyOf（array，ARRAYSIZE）；int〔〕array3Arrays。copyOf（array，ARRAYSIZE）；int〔〕array4Arrays。copyOf（array，ARRAYSIZE）；int〔〕array5Arrays。copyOf（array，ARRAYSIZE）；int〔〕array6Arrays。copyOf（array，ARRAYSIZE）；maopao（array）；System。out。println（）；xuanze（array2）；System。out。println（）；charu（array3）；System。out。println（）；mergeSort（array4）；System。out。println（）；xierSort（array5）；System。out。println（）；随机数据项进行快速排序System。out。print（对随机序列排序：）；quickSort（array6）；System。out。println（）；将array6逆序int〔〕array6anewint〔array6。length〕；for（intiarray6。length1，j0；i0；i）｛array6a〔j〕array6〔i〕；j；｝对逆序的数组使用快速排序System。out。print（对逆序序列排序：）；quickSort（array6a）；｝｝
　　原文格式更佳：高级排序算法之快速排序NGUP的个人技术博客