快速排序

快速排序思想

快速排序采用的思想是分治思想。

快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

算法步骤：

1.分解：

A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得
A[p ..q-1] <= A[q] <= A[q+1 ..r]

2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。

3.合并。

排序

基准(pivot)的选取选取数组分区后的第一个元素
对数组a[i,...,j]进行操作：
1.首先选择一个中间元素（一般选左端或者右端）。

2.分别获取除中间元素外的左右两端的索引。

3.由左右两端逐渐向中间迭代，每迭代一步比较一下索引中的元素和中间元素，当左边出现比中间元素大的元素的时候，暂停左边的迭代，当右边迭代出比中间元素小的元素的时候，右边迭代也暂停，交换左右两边的元素。

4.重复步骤3，直到左右两边的索引相遇，然后将中间元素移动到中间，这时中间元素左边的元素都比它小，右边的元素都比它大。

5.将上面的中间元素左右两边当成两个数组，分别进行上述过程。

6.重复以上步骤直到数组不可再分。

代码如下

public class quick_sort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a={4,5,6,7,223,21,5,22,445,55,2,5,88,33,66,22,4456,3,24,56,78,222};
        quickSort(a);
        for(int i=0;i<a.length;i++){
            System.out.println(a);
        }

    }
    public static void sort(int array[],int low,int high){
        int i,j;
        int index;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        index=array[i];
        while(i<j){
            while(i<j && array[j]>=index){
                j--;
                
            }
        if(i<j){
            array[i++]=array[j];
            
        }
        while(i<j && array[i]<index){
            
        }
        if(i<j){
            array[j--]=array[i];
        }
            
        }
        array[i]=index;
        sort(array,low,i-1);
        sort(array,i+1,high);
    }
    public static void quickSort(int array[]){
        sort(array,0,array.length-1);
    }

}