你的位置:首页 > Java教程

[Java教程]QuickSort 快速排序 基于伪代码实现


本文原创,转载请注明地址 http://www.cnblogs.com/baokang/p/4737492.html

伪代码

 1 quicksort(A, lo, hi) 2  if lo < hi 3   p = partition(A, lo, hi) 4   quicksort(A, lo, p - 1) 5   quicksort(A, p + 1, hi) 6  7 partition(A, lo, hi) 8   pivot = A[hi] 9   i = lo //place for swapping10   for j = lo to hi - 111     if A[j] <= pivot12       swap A[i] with A[j]13       i = i + 114   swap A[i] with A[hi]15   return i

 

Java实现

 

 1   public void quickSort(int[] a,int lo, int hi){ 2     if(lo<hi){ 3       int p=partition(a, lo, hi); 4       quickSort(a,lo,p-1); 5       quickSort(a, p+1, hi); 6     } 7   } 8   public int partition(int[] a,int lo, int hi){ 9     int i,j,privot;10     privot=a[hi];11     i=lo;12     for(j=lo;j<=hi-1;j++){13       if(a[j]<privot){14         swap(a, i, j);15         i++;16       }17     }18     swap(a,i,hi);19     return i;20   }21   public void swap(int[] a,int lo,int hi){22     int s=a[lo];23     a[lo]=a[hi];24     a[hi]=s;25   }