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

思想：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]
    
     
do{j--;}while(a[j]>key);
     
//while循环结束后，q[l..j]<=x, q[j+1..r]>=x
     
   if(i
     
      
int item=a[i];
      
a[i]=a[j];
      
a[j]=item;
      
}
      
}
      
quickSort(l,j);
      
quickSort(j+1,r);//递归
      
}////
      
public static void main(String[]args) throws IOException{
      
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      
int n = Integer.parseInt(in.readLine());
      
String[]arr=in.readLine().split(" ");
      
for(int i=0; i
      
       
quickSort(0,n-1);
       
for(int i=0; i
       
        
}}//(q, l, i - 1) (q, i, r) 配套x=q[(l + r >> 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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！