【数据结构与算法】：交换排序之快速排序（手绘图解+LeetCode原题）

import java.util.Arrays;

/**
 * @author .29.
 * @create 2022-09-09 21:37
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {85,12,59,36,62,44,43,94,7,35,52};//案例
        String str1 = Arrays.toString(arr);
        Qsort(arr,0,arr.length - 1);        //进行快速排序
        String str2 = Arrays.toString(arr);            //转换为字符串方便输出展示

        System.out.println(str1);                      //原序列输出
        System.out.println(str2);                      //快速排序后
    }

    public static void Qsort(int[] arr,int left,int right){
        if(left < right){
            int Low;                             //左边界
            int High;                            //右边界
            int Pivote;                          //基准
            Pivote = Median3(arr,left,right);    //获取基准

            Low = left;                          //需排序首元素的前一位（后续指针会优先向后移动）
            High = right - 1;                    //需排序尾元素的后一位（后续指针会优先向前移动）
            while(true){
                //指针优先向后移动，指向需排序首元素，若元素小于基准，继续后移
                while(arr[++Low] < Pivote);       
                //指针优先向前移动，指向需排序尾元素，若元素大于基准，继续前移
                while((Low<High) && arr[--High] > Pivote);
                
                if(Low < High) swap(arr,Low,High);//指针未错位，停止扫描后，元素交换位置
                else break;                       //指针错位，结束循环
            }

            if(Low < right)
            swap(arr,right-1,Low);              //将基准与错位后的Low指向元素交换位置

            Qsort(arr,left,Low-1);          //递归地对划分好的左序列用同样方法快速排序
            Qsort(arr,Low+1,right);          //递归地对划分好的右序列用同样方法快速排序
        }
        }

    //用来交换元素的方法（函数）
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static int Median3(int[] arr,int left,int right){
        int center = left + ((right-left) >> 1);      //相当于（left+right）/2
        if(arr[left] > arr[center])         //如果首元素小于中间元素
            swap(arr,left,center);           //交换位置

        if(arr[left] > arr[right])          //如果首元素小于尾元素
            swap(arr,left,right);            //交换位置

        if(arr[center] > arr[right])        //如果中间元素小于尾元素
            swap(arr,center,right);          //交换位置
        
        //经过上述操作，此时arr[left] <= arr[center] <= arr[right]
        //将基准放置在倒数倒数第一个元素（不放在最后是因为末尾的arr[right]大于基准
        swap(arr,center,right - 1);
        //现在首元素小于基准，尾元素大于基准，只需要考虑left+1到right-2的情况（right-1是基准）
        return arr[right-1];//返回被选为基准的元素
    }

输入整数数组 arr ，找出其中最小的 k 个数。
例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Qselect(arr,0,arr.length-1,k);//利用快排思想，将最小的k个数放在序列前列
        int[] Oput = new int[k];      //开辟一个大小为K的空间
        for(int i = 0;i < k; ++i){    //循环地将最小的k个数放入空间
            Oput[i] = arr[i];
        }
        return Oput;                 
    }

    //快速选择的递归函数（方法）
    public void Qselect(int[] arr,int L,int R,int k){
        if(L >= R)                           
        return;

        int p = getPivote(arr,L,R);      //获取基准元素下标
        int num = p-L+1;                 //左侧小于基准的子序列的元素个数
        //（基准划分的 左子序列元素 <= 基准 < 右子序列元素）
            if(num == k ){               //若左子序列元素个数等于预期的数量k
                return;                  //直接返回的就是最小的k个数
            }else if(num > k){           //若左子序列元素个数超过预期的数量k
                Qselect(arr,L,p-1,k);    //递归地用快速排序继续划分序列
            }else{                       //若左子序列元素个数低于预期的数量k
            //递归地用快速排序划分基准右侧的序列，除去已划分好的个数num，预期数量改为k-num
                Qselect(arr,p+1,R,k-num);
            }
    }

    //随机选取基准，并用于快排的函数（方法）
    public int getPivote(int[] arr,int L,int R){
        int pivote = (int)(Math.random()*(R-L+1)+L);//序列中任取元素为基准
        swap(arr,pivote,R);                         //基准与尾元素交换
        return Qsort(arr,L,R);                      //完成一次快排划分，返回基准
    }

    //快速排序的函数（只考虑左子序列的情况）
    //此方法建议画图辅佐理解
    public int Qsort(int[] arr,int L,int R){
        int Low = L-1;                      //小于区域的边界
        int High = R;                       //尾元素，即基准元素下标
        for(int l = L;l < High; l++){       //从左向右扫描
            if(arr[l] <= arr[High]){        //如果扫过元素小于基准元素，即符合要求
                Low++;                      //小于区域边界向右移动
                swap(arr,Low,l);            //交换区域边界元素与扫过的元素
 //说明：当边界内元素小于基准，相当于与自身交换，当边界内元素大于基准，相当于将小于基准的元素换进来
            }
        }
        swap(arr,R,Low+1);                 //将基准与小于区域的下一位交换位置，表示完成一次划分
            return Low+1;                  //返回记住下标。
    }

    //用于交换元素位置的函数（方法）
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}