2.5 快速排序（Quick sort）

一. 定义

​ 快速排序（Quick sort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

具体流程

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。

2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

   概括来说为 挖坑填数 + 分治法。

参考自：https://blog.csdn.net/justidle/article/details/104203963

二. 代码实现

方法一：以第一个元素为枢轴

/**
 * desc 快速排序
 * @author GreyPigeon mail:2371849349@qq.com
 * @since 2024-01-12-21:56
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arry = {9,2,7,6,5,8,3,2,1};
        quickSort(arry,0, arry.length-1);
        System.out.println(Arrays.toString(arry));
    }
    public static void quickSort(int[] arry,int left,int right){
        //运行判断，如果左边索引大于右边是不合法的，直接return结束次方法
        if(left>right){
            return;
        }
        //定义变量保存基准数(枢轴）
        int pivot = arry[left];
        //定义变量i，指向最左边
        int i = left;
        //定义j ,指向最右边
        int j = right;
        //当i和j不相遇的时候，再循环中进行检索
        while(i!=j){
            //先由j从右往左检索比基准数小的，如果检索到比基准数小的就停下。
            //如果检索到比基准数大的或者相等的就停下
            while(arry[j]>= pivot && i<j){
                j--; //j从右往左检索

            }
            while(arry[i]<= pivot && i<j){
                i++; //i从左往右检索
            }
            //代码走到这里i停下，j也停下，然后交换i和j位置的元素
            int temp = arry[i];
            arry[i] = arry[j];
            arry[j] = temp;


        }
        //如果上面while条件不成立,就说明 i和j相遇了，就交换基准数这个元素和相遇位置的元素
        arry[left] = arry[i];
        //把基准数赋给相遇位置的元素
        arry[i] = pivot;
        //基准数在这里递归就为了左边的数比它小，右边的数比它大
        //排序基准数的左边
        quickSort(arry,left,i-1);
        //排序基准数的左边
        quickSort(arry,j+1,right);

    }
}

方法二：以中间元素为枢轴

/**
 * desc 快速排序
 * @author GreyPigeon mail:2371849349@qq.com
 * @since 2024-01-12-21:56
 **/
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};
        quickSort(arr, 0, arr.length-1);
        System.out.println("arr=" + Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中轴值
        int pivot = arr[(left + right) / 2];
        int temp = 0; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while( l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while( arr[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while(arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if( l >= r) {
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if(arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if(arr[r] == pivot) {
                l += 1;
            }
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if(right > l) {
            quickSort(arr, l, right);
        }
    }
}