本文共 2042 字，大约阅读时间需要 6 分钟。

思想：1、确定分界点 ：x=q[ l ] 、q[ r ] 、q[ (l+r) / 2] 、随机

           2、调整区间，让第一个区间内所有的数<=x，第二个区间内的所有数>=x 。

           3、递归处理左右两端，分别给左边右边排序

步骤：用两个指针，分别指在数组的两端，两个指针分别往中间走。 i指针指向的数小于x，则这个数最终在左边，i往后移动一位，重复以上步骤，直到i指针指向的数>=x，停下来。然后看j指针，j指针一直往中间走（同上），直到某次<=，此时两个数错位了，将两个数交换，此时两个数的指向正确了，继续重复步骤，直到相遇为止。

注意：边界问题

两个指针最开始放到左右边界两侧，外侧，然后再往进扩。

例题：利用快速排序算法将读入的 N 个数从小到大排序后输出。

import java.io.*;class Main{    static int N=100010;    static int[] a=new int[N]; //创建数组////模板    static void quickSort(int l,int r){        if(l==r) return;         int key=a[l+r>>1];  //选中间值        int i=l-1;          int j=r+1;  //两个指针往中间移动        while(i
   
    =j            do{i++;}while(a[i]
    
     key);        //while循环结束后，q[l..j]<=x, q[j+1..r]>=x           if(i
     
      > 1) + 1]//(q, l, j) (q, j + 1, r)配套x=q[l + r >> 1]
     
    
   

例题：给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数

import java.io.*;import java.util.*;public class Main{    public static void main(String[] args) throws IOException{        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));        String[] strs = reader.readLine().split(" ");        int n = Integer.parseInt(strs[0]);        int k = Integer.parseInt(strs[1]);        int[] arr = new int[n];        strs = reader.readLine().split(" ");        for(int i = 0; i < n; i++){            arr[i] = Integer.parseInt(strs[i]);        }        int res = quickSort(arr, 0 , arr.length - 1, k);        System.out.println(res);        reader.close();    }    public static int quickSort(int[] arr, int start, int end, int k){        if(start >= end) return arr[start];        int stard = arr[start];        int low = start, high = end;        while(low < high){            while(low < high && stard <= arr[high]) high--;            arr[low] = arr[high];            while(low < high && stard >= arr[low]) low++;            arr[high] = arr[low];        }        arr[low] = stard;        //统计sl的个数        int sl = high - start + 1;        if(k <= sl) return quickSort(arr, start, high, k);        return quickSort(arr, high + 1, end, k - sl);    }}

转载地址：https://blog.csdn.net/m0_56632342/article/details/122683244 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！