詳解疾速排序算法中的區間劃分法及Java完成示例

詳解疾速排序算法中的區間劃分法及Java完成示例。本站提示廣大學習愛好者：（詳解疾速排序算法中的區間劃分法及Java完成示例）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解疾速排序算法中的區間劃分法及Java完成示例正文

疾速排序是C.R.A.Hoare於1962年提出的一種劃分交流排序。該辦法的根本思惟是：
1．先從數列中掏出一個數作為基准數。
2．分區進程，將比這個數年夜的數全放到它的左邊，小於或等於它的數全放到它的右邊。
3．再對閣下區間反復第二步，直到各區間只要一個數。
算法的思緒很清楚，然則假如在區間劃分進程中界限值沒有處置好，也是很輕易湧現bug的。上面給出兩種比擬清楚的思想來指點區間劃分代碼的編寫。
第一種思想即所謂的挖坑法思想，上面經由過程剖析一個實例來剖析一下挖坑法的進程：
以一個數組作為示例，取區間第一個數為基准數。

初始時，left = 0; right= 9;   X = a[left] = 72
因為曾經將a[0]中的數保留到X中，可以懂得成在數組a[0]上挖了個坑，可以將其它數據填充到這來。
從right開端向前找一個<=X的數。明顯,right=8時，相符前提，將a[8]挖出再填到上一個坑a[left]中。 如許一個坑a[0]就被弄定了，但又構成了一個新坑a[8]，這怎樣辦了？簡略，再找數字來填a[8]這個坑。此次從left開端向後找一個年夜於X的數，當left=3，相符前提，將a[3]挖出再填到上一個坑a[right] 中;
數組變成：

再反復下面的步調，終究數組將釀成以下情勢：

可以看出a[5]後面的數字都小於它，a[5]前面的數字都年夜於它。將X填入a[5]的坑中，數據變成：

是以再對a[0…4]和a[6…9]這二個子區間反復上述步調便可以了。
對挖坑填數停止總結
1．i =L; j = R; 將基准數挖出構成第一個坑a[i]。
2．j--由後向前找比它小的數，找到後挖出此數填前一個坑a[i]中。
3．i++由前向後找比它年夜的數，找到後也挖出此數填到前一個坑a[j]中。
4．再反復履行2，3二步，直到i==j，將基准數填入a[i]中。
照此分區辦法，疾速排序Java代碼以下：

public class Partition { 
 
 /** 
  * 基於base劃分，小的在左，年夜的在右， 不請求全部序列有序 
  * 
  * @param ary 
  * @param base 
  */ 
 static void sort(int[] ary, int base) { 
  int left = 0; 
  int right = ary.length - 1; 
   
  int leftpoint = left, rightpoint = right; 
   
  while (true) { 
   // 分紅閣下雙方同時停止比擬，一邊從左向右，一邊從右向左， 
   while (leftpoint < right && ary[leftpoint++] < base); //leftpoint年夜於right或ary[leftpoint]>base停滯輪回 
    
   while (rightpoint >= left && ary[rightpoint--] > base); //反之 
   System.out.println("右邊須要交流的索引:" + (leftpoint-1)); 
   System.out.println("左邊須要交流的索引:"+ (rightpoint+1)); 
   //下面拿到了不相符前提的兩個索引，即須要交流的兩個索引 
   if (leftpoint - 1 < rightpoint + 1) {//須要交流 
    swap(ary, leftpoint - 1, rightpoint + 1); 
    Util.printArray(ary); 
    leftpoint = left; 
    rightpoint = right; 
   } else { 
    break; 
   } 
  } 
 } 
  
 
 private static void swap(int[] ary, int a, int b) { 
  int temp = ary[a]; 
  ary[a] = ary[b]; 
  ary[b] = temp; 
 } 
 
 public static void main(String[] args) { 
  int[] ary = Util.generateIntArray(10); 
  System.out.println("原序列："); 
  Util.printArray(ary); 
  sort(ary, 5); 
  System.out.println("排序後："); 
  Util.printArray(ary); 
 } 
} 

成果：

原序列： 
[2, 8, 4, 3, 7, 5, 1, 9, 0, 6] 
右邊須要交流的索引:1 
左邊須要交流的索引:8 
[2, 0, 4, 3, 7, 5, 1, 9, 8, 6] 
右邊須要交流的索引:4 
左邊須要交流的索引:6 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 
右邊須要交流的索引:5 
左邊須要交流的索引:5 
排序後： 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 

區間劃分的的另外一種指點思想:
將數組的第一個元素作為區間劃分值，從第二個元素開端分區，直到構成如圖所示的成果，

然後交流l<t區間的左邊界值和t,構成以下的成果：

如斯，可以以下編寫疾速排序代碼：

public void qSort(int array[],int left,int right) 
 { 
  if(left < right){ 
 
   int key = array[left]; 
 
   int high = right; 
    
   int low = left+1; 
    
   while(true){ 
     
    while(low <= high && array[low] <= key) low++; 
 
    while(low <= high && array[high] >= key) high--; 
        
    if(low > high) 
     break; 
 
    swap(array,low,high); 
   } 
   swap(array,left,high); 
    
   printArray(array); 
 
   qSort(array,left,high-1); 
 
   qSort(array,high+1,right); 
  } 
 }