快速排序——java实现

快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序的基本思想

首先在要排序的区域中选取一个基准，而后将整个区域分成两个分区，其中左分区中的元素均小于或者等于基准，右分区的元素均大于或者等于基准，而后通过递归调用快速排序的过程分别对两个分区再次进行排序，最后将两个分区产生的结果合并即可得到最后的排序序列。

但是选取基准有不同的方法，先介绍一下固定位置选取基准法

固定位置选取基准

每次都选取当前所排序区域最左边的元素作为基准。

上图啦~~

可以看到经过一次排序后，基准左边的数都比基准小，基准右边的数都比基准大！！！
然后再对基准左边区域和右边区域分布排序

递归实现

public class Quick {

    //求基准
    public static int partion(int[] array, int low, int high) {
        int tmp = 0;
        tmp = array[low]; //tmp做为基准
        while (low < high) {
 
            while (low < high && array[high] >= tmp) { //先看右边，与基准进行比较，如果大于基准则继续向左比较
                high--;
            }
            if (low >= high) {
                break;
            } else { //直到小于基准，进行交换
                array[low] = array[high];
            }

            while (low < high && array[low] <= tmp) { //再看左边，与基准进行比较，如果小于基准则继续向右比较
                low++;
            }
            if (low < high){ //直到大于基准，进行交换
                array[high] = array[low];
            }
        }
        if (low == high) {
            array[low] = tmp;
        }
        return low;
    }

    /**
     * 时间复杂度：O(nlog2n)
     * 空间复杂度：O(log2n)
     * 不稳定
     *
     * @param array
     * @param low
     * @param high
     */
    public static void quick(int[] array,int low,int high){
        int par = partion(array,low,high); //O(n)
        if (par > low + 1){ //
            quick(array,low,par-1); //log2n
        }
        if (par < high - 1){
            quick(array,par+1,high);
        }
    }

    //递归实现
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
}

非递归实现

就是用栈来实现
看图解啦…

以此类推，经过一系列出栈入栈直到栈为空，排序结束

public class Quick {

    //求基准
    public static int partion(int[] array, int low, int high) {
        int tmp = 0;
        tmp = array[low];//tmp做为基准
        while (low < high) {

            while (low < high && array[high] >= tmp) {//先看右边，与基准进行比较，如果大于基准则继续向左比较
                high--;
            }
            if (low >= high) {
                break;
            } else {//直到小于基准，进行交换
                array[low] = array[high];
            }

            while (low < high && array[low] <= tmp) {//再看左边，与基准进行比较，如果小于基准则继续向右比较
                low++;
            }
            if (low < high){//直到大于基准，进行交换
                array[high] = array[low];
            }
        }
        if (low == high) {
            array[low] = tmp;
        }
        return low;
    }
        //非递归实现
    public static void quickSort(int[] array) {
        int low = 0;
        int high = array.length-1;
        int par = partion(array,low,high);
        int size = (int)(Math.log((double) array.length)/Math.log((double)2));
        int[] stack = new int[2*size];//log2n
        int top = 0;
        if (par > low +1){
            stack[top++] = low;
            stack[top++] = par - 1;
        }
        if (par < high - 1){
            stack[top++] = par + 1;
            stack[top++] = high;
        }
        while (top > 0){
            high = stack[--top];
            low = stack[--top];
            par = partion(array,low,high);
            if (par > low +1){
                stack[top++] = low;
                stack[top++] = par - 1;
            }
            if (par < high - 1){
                stack[top++] = par + 1;
                stack[top++] = high;
            }
        }
    }
}