基础练习之分治法_快速排序

分治法,分而治之,基本思路:分,解,和。

初探分治之快速排序。

  1. public class _DividedConquer {  
  2.   
  3.     static int[] iarr;  
  4.     public static void main(String[] args) {  
  5.         // TODO Auto-generated method stub  
  6.         iarr=new int[]{6,4,5,3,1,2};  
  7.         quick(0, iarr.length-1);  
  8.         for(int i:iarr)  
  9.         {  
  10.             System.out.print(i+” “);  
  11.         }  
  12.     }  
  13.   
  14.     static void quick(int p,int r)  
  15.     {  
  16.         if(p<r)  
  17.         {  
  18.             int q=part(p,r);  
  19.             quick( p, q-1);  
  20.             quick( q+1, r);  
  21.         }  
  22.     }  
  23.       
  24.     static int part(int p,int r)  
  25.     {  
  26.         int x=iarr[r];  
  27.         int i=p-1;  
  28.         for(int j=p;j<r;j++)  
  29.         {  
  30.             if(iarr[j]<x)  
  31.             {  
  32.                 i++;  
  33.                   
  34.                 int tmp=iarr[i];  
  35.                 iarr[i]=iarr[j];  
  36.                 iarr[j]=tmp;  
  37.             }  
  38.         }  
  39.           
  40.         int tmp=iarr[i+1];  
  41.         iarr[i+1]=iarr[r];  
  42.         iarr[r] =tmp;  
  43.           
  44.         return i+1;  
  45.     }  
  46. }  

标签