教你JAVA语言快速排序的原理.docx

教你JAVA语言快速排序的原理教你JAVA语言快速排序的原理快速排序（QuickSort）是常用到的效率比较高的一种排序算法，在面试过程中也经常提及。下面就详细讲解一下他的原理、给出一个Java版本的实现。快速排序思想：通过对数据元素集合Rn进行一趟排序划分出独立的两个部分。其中一个部分的关键字比另一部分的关键字小。然后再分别对两个部分的关键字进行一趟排序，直到独立的元素只有一个，此时整个元素集合有序。快速排序的过程——挖坑填数法（这是一个很形象的名称），对一个元素集合R[low...high],首先取一个数（一般是R[low]）做参照，以R[low]为基准重新排列所有的元素。所有比R[low]小的放前面，所有比R[low]大的放后面，然后以R[low]为分界，对R[low...high]划分为两个子集和，再做划分。直到low>=high。比如：对R={37,40,38,42,461,5,7,9,12}进行一趟快速排序的过程如下(注:下面描述的`内容中元素下表从0开始)：原始序列3740384246157912一：high-->low1240384246157912一：low-->high1240384246157940二：high-->low129384246157940二：low-->high1293842461573840三：high-->low129742461573840三：low-->high1297424615423840四：high-->low129754615423840四：low-->high12975461461423840一趟排序结果1297537461423840开始选取基准base=37，初始位置下表low=0，high=8，从high=8，开始如果R[8]<base,将high位置中的内容写入到R[low]中,将high位置空出来,low=low+1;从low开始探测，由于low=1，R[low]>base,所以将R[low]写入到R[high],high=high-1;检测到low<high,所以第一趟快速排序仍需继续:此时low=1，high=7，因为R[high]<base,所以将R[high]写入到到R[low]中,low=low+1;从low开始探测,low=2,R[low]>base,所以讲R[low]写入到R[high]，high=high-1;继续检测到low小于high此时low=2，high=6，同理R[high]<base,将R[high]写入到R[low]中，low=low+1;从low继续探测,low=3,high=6,R[low]>base,将R[low]写入到R[high]中，high=high-1;继续探测到low小于high此时low=3，high=5，同理R[high]<base,将R[high]写入到R[low]中，low=low+1；从low继续探测，low=4，high=5，由于R[low]>base,将R[low]写入到R[high]中，high=high-1;此时探测到low==high==4；该位置即是base所在的位置，将base写入到该位置中.然后再对子序列Rs1={12,9,7,5}和Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一个元素，或没有元素。（注:在以上表单中可以看到一趟排序中有一些重复的数据（原始数据中没有重复的数据），这是因为没有清除该位置的数据，我们在特定的时间看该内存块的数据依然是它，直到下一次将数据写入该位置位置——在此该位置的数据是一个没有意义脏数据，称之为“坑”）快速排序的Java实现：复制代码代码如下:privatestaticbooleanisEmpty(int[]n){returnn==null||n.length==0;}//////////////////////////////////////////////////////***快速排序算法思想——挖坑填数方法：**@paramn待排序的数组*/publicstaticvoidquickSort(int[]n){if(isEmpty(n))return;quickSort(n,0,n.length-1);}publicstaticvoidquickSort(int[]n,intl,inth){if(isEmpty(n))return;if(l<h){intpivot=partion(n,l,h);quickSort(n,l,pivot-1);quickSort(n,pivot+1,h);}}privatestaticintp