一、什么叫快速排序?

  通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

  二、排序步驟:

  對下列數組進行排序:(22,36,4,51,36,8,44,5,62,14,5,6,32,12)

  1.)找出一個元素作為基準(理論上可以隨便找一個)定義兩個指針begn和end.

Java代碼
  1. int x=begn;  
  2. int y=end;  
  3. int s=a[begn];

手把手圖文教程:快速排序

找第一個元素作為基準

  2.)排序實現:

  1. 以 22 位基準 ;

  2. 在begn位置開始往上找大于等于22的數字;

  3.在end處開始往下找小于等于22的數字;

  4.找到后交換位置

Java代碼
  1. while (a[x]<s){  
  2.     x++;  
  3. }  
  4. while(a[y]>s){  
  5.     y--;  
  6. }  
  7.  if(y>=x){  
  8.     int tem=a[x];  
  9.     a[x]=a[y];  
  10.     a[y]=tem;  
  11.     x++;  
  12.     y--;  
  13. }  

  第一趟執行結果:

手把手圖文教程:快速排序

第一趟執行結果

  3.)最后重復以上操作調用遞歸算法:

Java代碼
  1. if(begn<y){  
  2.     Qucli(a,begn,y);  
  3. }  
  4. if(end>x){  
  5.     Qucli(a,x,end);  
  6. }  

  三、完整程序:

Java代碼
  1. public class QuickSort {  
  2.   //快速排序  
  3.     public static void Qucli(int []a,int begn,int end){  
  4.         int x=begn;  
  5.         int y=end;  
  6.         int s=a[begn];  
  7.         while(y>=x){  
  8.             while (a[x]<s){  
  9.                 x++;  
  10.             }  
  11.             while(a[y]>s){  
  12.                 y--;  
  13.             }  
  14.         if(y>=x){  
  15.   
  16.             int tem=a[x];  
  17.             a[x]=a[y];  
  18.             a[y]=tem;  
  19.             x++;  
  20.             y--;  
  21.         }  
  22.   
  23.         if(begn<y){  
  24.             Qucli(a,begn,y);  
  25.         }  
  26.         if(end>x){  
  27.             Qucli(a,x,end);  
  28.         }  
  29.     }   
  30.     }  
  31.     public static void main(String[] args) {  
  32.         int a[]={22,36,4,51,36,8,44,5,62,14,5,6,32,12};  
  33.         Qucli(a,0,a.length-1);  
  34.         for(int ss:a){  
  35.             System.out.print(ss+"  ");  
  36.         }  
  37.     }  
  38.   
  39. }  

  結果展示:

手把手圖文教程:快速排序

除非特別注明,雞啄米文章均為原創
轉載請標明本文地址:http://www.vkzldl.live/software/682.html
2017年1月6日
作者:雞啄米 分類:軟件開發 瀏覽: 評論:1