JAVA-快速排序

一、快速排序基本思想

我们此次实现拿数组的第一个元素做为基准值

right找到比tmp小的，left再找到比tmp大的就交换。如果交汇了就放入第一个元素，再把tmp放进来。 right必须先找left后找

把交汇处的下标给par，再分别从par两边重复之前的操作。而且这不就是二叉树吗。那么就适合用递归来处理了

二、快速排序的实现

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

    private static void quick(int[] array,int start,int end) {
        
    //当start >= end了证明只有一个元素，或者没有左右树了也就不需要排序了
        if(start >= end) {
            return;
        }
    //按照基准值对array数组的 [start,end]区间中的元素进行划分
    //并返回当前基准值下标
        int par = partitionHoare(array,start,end);

    //遍历左边
        quick(array,start,par-1);
    //遍历右边
        quick(array,par+1,end);

    }

1.Hoare法找基准值  

从逻辑上已经构造好了，就差具体的操作了：

    /**
     * Hoare法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionHoare(int[] array, int left,int right) {
        //用来保存基准值下标
        int i = left;
        //记录基准值的值
        int tmp = array[left];
        //没交汇就继续循环
        while (left < right) {
            //left < right 必须写前面，防止6 7 8 9这种情况
            //找到最右边小于基准值的值
            while (left < right && array[right] >= tmp){
                right--;
            }
            //找到左边大于基准值的值
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //交换
            swap(array,left,right);
        }
        //此时 left 和 right 交汇
        swap(array,i,left);
        
        //返回新的基准值下标
        return left;
    }

    //交换函数
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

测试代码：

public static void main(String[] args) {
        int[] array = {10,9,7,2,3,8,1};

        Sort.bubbleSort(array);

        System.out.println(Arrays.toString(array));
    }

出了刚才的Hoare法可以找基准值下面还有两种方法

2.挖坑法

先把基准值记录一下，再由right找到小于基准值的，然后left找到大于基准值的。两边来回填补。

最后tmp放入交汇处

细心的就会发现，这和Hoare法的数据顺序是不一样的。但也同样达到了效果

画图的时候里面有一些空，其实是保留了原来数据的，但是为了更好的理解就没有保留。但是在代码上原有的数据一定会被覆盖。

代码：

    /**
     * 挖坑法
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionK(int[] array, int left,int right) {
        //记录第一个坑，做为基准值
        int tmp = array[left];
        while (left < right) {
            //找到最左边比基准值小的
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //左边小的数据先放入，已经挖好了坑tmp
            array[left] = array[right];

            //找到最右边大于基准值的
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //放入右边的新坑
            array[right] = array[left];
        }
        //left 和 right 交汇，填空
        array[left] = tmp;
        return left;
    }

这是最重要的一种方法，着重掌握

3.前后指针法(了解)

做选择题的时候可能会有。做题顺序： 挖坑法 > Hoare法 > 前后指针法

​
    /**
     * 前后指针法 (做为了解)
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionPre(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }

​

快速排序如果不做优化，数据量大了以后他是很有可能会栈溢出的。

三、快速排序的优化

1.三数取中法

快排在能取到中间值时，最快。

如果数组是一个有序的，那么就会开辟很多没必要的空间。浪费时间空间

那么三树取中就是：

用left 和 right 与 mid(数组中间下标的值) ，里面选居中的一个。做为基准值，并将他和left换一下

此时3做为基准值

 那么最后基准值就在中间位置

写一个函数找到三个数之间中间的那个数的下标:

//返回的是中间值小标
    private static int midTreeNum(int[] array,int left,int right) {
        int mid = left + right / 2;

        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[right] < array[mid]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[left] < array[mid]) {
                return left;
            }else {
                return mid;
            }
        }
    }

边看图边看代码，假设array[left] < array[right]   假设array[left] >= array[right]

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

        private static void quick(int[] array,int start,int end) {
            if(start >= end) {
                return;
            }
       
            //三数取中法
            int index = midTreeNum(array,start,end);
            swap(array,index,start);

            int par = partitionK(array,start,end);

            quick(array,start,par-1);
            quick(array,par+1,end);

        }

结果：

2.递归到小的子区间时，可以考虑使用插入排序

我们知道在趋于有序的时候插入排序最快，可以达到O(n)

public static void insertSortRange(int[] array,int left ,int right) {
        for (int i = left+1; i <= right; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= left; j--) {
//                if(array[j] > tmp) {   不稳定的写法
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //防止第一次array[j]>tmp，从而j--到-1，执行不到这条语句
//                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
}

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

        private static void quick(int[] array,int start,int end) {
            if(start >= end) {
                return;
            }
            //当分出来的,数组越小。递归的次数就越多了，但是趋于有序了就可以用插入排序
            if(end - start + 1 <= 10) {
                insertSortRange(array,start,end);
                return;
            }

            //三数取中法
            int index = midTreeNum(array,start,end);
            swap(array,index,start);

            int par = partitionK(array,start,end);

            quick(array,start,par-1);
            quick(array,par+1,end);

        }

四、非递归的写法

public static void quickSortNot(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int par = partitionK(array,left,right);

        if(par > left+1) {
            stack.push(left);
            stack.push(par-1);
        }
        if(par < right-1) {
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            par = partitionK(array,left,right);

            //保证左边至少有两个元素
            if(par > left+1) {
                stack.push(left);
                stack.push(par-1);
            }
            //保证右边至少有两个元素
            if(par < right-1) {
                stack.push(par+1);
                stack.push(right);
            }
        }
}

用栈来模拟，用栈后进先出的原理来模拟实现。

快速排序最好还是用递归来实现

五、时间空间复杂度

时间复杂度:O(n*log2n)

空间复杂度:O(n)

稳定性:不稳定