快速排序的一些简单理解

前言

这几天做题的时候，做到一道排序题，用冒泡排序去做显示运行时间过长，后面用快排做的时候，通过了，下面就简单说下自己对快排的理解

快速排序的步骤：

1.把数组中的一个数当作基准数，一般会把数组中最左边的数当作基准数，然后从两边进行检索，先从右边往左检索比基准数小的，再从左边向右检索比基准数大的，如果检索到了，就停下，然后两个元素交换位置（这里从左往右检索成为i,右往左成为j）
2.交换完成，然后按照1中的步骤继续检索，直到i和j相遇，就停止检索。把基准数和相遇位置的元素交换。此时第一轮排序结束，此时数组基准数左边全部小于基准数，右边全部大于基准数
类似于这样{1，4，5，3，6，9，7，8，10}，可以看出6左边的数全部小于6，右边的数全部大于6
3.第二轮排序开始，可以把6左右的元素看成是两个数组{1，4，5，3}和{9,7,8,10},方式和第一轮一样进行排序，先排基准数左边再排基准数右边
4.接下来递归前面几步。
代码示例：

  // left表示左边索引，right表示右边索引
    public static void quickSort(int[] array,int left,int right){

        //如果左边索引大于右边索引，直接return结束方法
        if (left > right){
            return;
        }
        // 以第一个元素作为基准数
        int base = array[left];
        // 变量i,指向最左边的数
        int i = left;
        int j = right;
        // 当i=j的时候，就不能再排了
        while (i!=j){
            //先由j从右往左检索，检索到比基准数小的，就停下，也就是说，检索到比基准数大的或相等的数，就继续检索
            // i<j 保证检索不越界
            while (array[j] >= base&& i<j) {
                    j--;// j向左移动
            }
            // i从左往右检索，检索到比基准数大的就停下，也就是说，检索到的数小于或等于基准数时，检索继续
            while (array[i] <= base && i<j){
                i++; // i向右移动
            }
            // 如果代码走到这一步，表示i停下了，j也停下了。就交换i，j对应元素的位置
            int t = 0;
            t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
        // 当代码走到这一步的时候，表示推出了整个大循环，此时 i = j ，这个时候我们交换相遇的坐标对应元素与base的位置
        //这里的arry[i]与arry[j]都可以使用，因为此时相遇，下标对应的是同一个元素

        // 相遇时，交换相遇元素与基准数的位置
        //将相遇时的值赋给最左边
        array[left] = array[i];
        // 再把基准数的值赋给相遇时的元素
        array[i] = base;

        // 在这里，基准数就归位了，此时，基准数左边的都比它小，右边的都比它大
        // 接下来分别对基准数两边以同样的方法排序
        // 这里可以把左边和右边要排序的看成是原来数组的一个子数组，在进行排序，因为对一个数组排序方法前面写了，这里就递归调用
        //排左边

        quickSort(array,left,i - 1);
        // 排右边
        quickSort(array,i+1,right);




    }

快速排序的一些简单理解

原文：https://www.cnblogs.com/Whichzzz/p/14983684.html