快速排序算法

package com.mytest.algorithm;
/**
 * @author zhangc
 * @since 2018/10/25 16:35
 * 快速排序算法： 快速排序和归并排序类似，也使用了分治思想，不同的是分解的方法不同，快速排序是利用一个基准进行分组（默认是最后一个元素） 。而且快速排序是
 * 原址交换，不需要合并
 **/
public class quickSort {

    //假设我们定义左组 ，基准， 右组，快速排序就是递归的对数组拆分。
    public static int part(int[] array,int start,int end){
        int x = array[end]; //作为基准值
        int i = start-1; //作为左组的游标，左组元素加一个，则增加1 ，起始下标为第一个被循环元素下标-1
        //循环所有元素
        for(int j=start;j<end;j++){
            //如果元素小于等于基准，那么说明这个元素应该放到左组里面。
            // 如何放：交换
            if(array[j]<=x){
                i++;
                int tem = array[j];
                array[j] = array[i];
                array[i] = tem;
            }
        }
        //完成所有循环和交换后，这时 我们的i 已经是左组的最后元素的下标。。这个时候把基准值放到左右组之间，依然使用交换。
        //这个时候数组就形如  左组 < 基准 < 右组 （注意是组内的元素都比基准小，但是组内并没有排序，所以要继续递归调用该方法，
        // 直到左右组元素为1个 ，这个时候就是真正的排序了， a<基准<b ）
        int tem = array[i+1];
        array[i+1] = x;
        array[end] = tem;
        return i+1;
    }

    public static void quicksort(int[] array , int start , int end ){
        if(start<end){
            int position = part(array,start ,end );
            //注意是position-1 和 position+1 ,因为position处的元素大小肯定是出于这两组之间，不需要再排序了
            quicksort(array, start, position-1);
            quicksort(array,position+1 ,end );
        }
    }

    public static void main(String[] args) {
        int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
        quicksort(array, 0, array.length-1);
        for (int i : array){
            System.out.println(i);
        }

    }

}