java程序实现;快速排序的实现

package com.wp;

public class QuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []array={1, 20,3,9,5,6,7};
        QuickSort_test(array);

        for(int e:array){
             System.out.print(" "+e);
        }
    }
    /**
    *第二种快速排序方法，挖坑填数+分治
    *保存第一个元素到x里面，第一个成为一个坑，数组从后往前找一个比x小的元素(在位置j处)填到前面的坑里，这样后面(位置j)又出来一个新坑，
    *然后再从前往后找一个比x大的元素(在位置i处)填到坑(位置j)里，位置i处成了一个新坑，这样循环直到i=j,最后将x填到中间这个坑里
    */
    public static int Partition2(int array[],int left,int right)
    {
        int i = left;
        int j = right;
        int x = array[left];

        while (i<j)
        {
            while ((i<j)&&(array[j]>x))
                j--;
            if (i<j)
            {
                array[i] = array[j];
                i++;
            }

            while ((i<j)&&(array[i]<x))
                i++;

            if (i<j)
            {
                array[j] = array[i];
                j--;
            }
        }
        //退出循环，i==j
        array[i] = x;

        return i;
    }
    public static void QuickSort_method(int[] array,int p,int r)
    {
        int q;

        if (p<r)
        {
            q = Partition2(array,p,r);
            QuickSort_method(array,p,q-1);
            QuickSort_method(array,q+1,r);
        }
    }

  public static void QuickSort_test(int[]array){

      QuickSort_method(array,0,array.length-1);
  }


}