quicksort.java

来自「包括冒泡排序」· Java 代码 · 共 56 行

/**
 * 实现快速排序的算法
 * @author jok
 * @version 1.0
 * 
 */

package cn.com.csu.algorithm;

public class QuickSort {


  public static void main(String[] args) {
    int[] arr = {6,5,4,3,2,1};
    QuickSort qs = new QuickSort();
    qs.quickSort(arr,0,arr.length-1);
    for(int i=0;i<arr.length;i++) {
      System.out.print(arr[i]);
    }
  }
  
  private int partion(int[] a,int begin,int end) {
    int p = a[begin];
    int i = begin+1,j=end,temp;
    while(i<j) {
      while(i<end && a[i]<p ) {
        i++;
      }
      while(j>begin && a[j]>p) {
        j--;
      }
      if(i<j) {
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
      }
      
    }
    temp=a[begin];
    a[begin]=a[j];
    a[j]=temp;
    return j;
  }
  
  private void quickSort(int[] a,int begin,int end) {
      int s=this.partion(a,begin,end);
      if(s-begin >1) {
        quickSort(a,begin,s-1);
      }
      if(end- s >1) {
        quickSort(a,s+1, end);
      }
  }

}