快速排序

快速排序的核心思想：

确定分界点，可以是q[l],q[(l+r)/2]或q[r],我们选用q[l]
调整区间，就是将就是把所有比分界点大的放到右边，所有比分界点小的放到左边
- 如何调整？双指针，一个从左往右走知道找到比分界点大的，一个从右往左…
- 找到后，交换，再继续走，直到两指针相遇
递归处理
- 步骤2结束后，再次递归分界点两边的区间

模板

// 参数解释：
// 1. int[] arr 需要排序的数组
// 2. int l  排序的左端点
// 3. int r	 排序的右端点
// 举例： 你要排序一个 int[] arr = {1,5,3,2,6} 数组内全部要排序，l=0，r=arr.length-1
public static void quickSort(int[] arr, int l, int r)
{
    //递归结束 条件
    if(l>=r) return;
    
    //1. 确定分界点
    int p = arr[l]; //我们取左端点
    //确定边界 +1-1是应为我们使用的do-while，开始前就会i++和j--
    int i = l-1;
    int j = r+1;
    
    //2. 调整区间
    while(i < j){
        do{
            i++;
        }while(arr[i] < p); //记得分号;
        
        do{
            j--;
        }while(arr[j] > p); 
        
        //找到两个不符合定义的点，即左边找到一个比分界点大的，右边找到一个比分界点小的
        //交换
        if(i < j){ //别忘了，很关键，两个指针还没有重合或穿过
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }          
    }
    
    //3. 递归处理
    quickSort(arr, l, j);
    quickSort(arr, j+1, r);
    //此处为了边界不出问题，我们边界点一开始取q[l],那么递归的时候就l~j 和 j+1~r
    //这样就不会出现边界问题
}

题目

AcWing的两道题

P785 快速排序套用模板即可，只需要写输入输出部分
P786 第k个数

P786 第k个数

题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第k小数。

数据范围

1≤n≤100000
1≤k≤n

输入样例：
>5 3
>2 4 1 5 3
输出样例：
>3

题目解答

//通用导入
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args)throws IOException {
        //数据输入最好用字符缓冲流	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		int n = Integer.parseInt(str[0]);
		int k = Integer.parseInt(str[1]);
		
		int[] arr = new int[n];
		String[] Line = br.readLine().split(" ");
		for(int i=0;i<n;i++)
		{
			arr[i]=Integer.parseInt(Line[i]);
		}
		quickSort(arr, 0, n-1);
		System.out.println(arr[k-1]);  //第k个数的下标是k-1哦
	}
    
    //快排模板
    public static void quickSort(int[] arr, int l, int r){
        //递归结束条件
        if(l >= r) return;
        
        //1. 确定分界点
        int p = arr[l]; //我们一般取左端点，避免边界问题
        int i = l - 1;
        int j = r + 1;  //两个指针
        
        //2. 处理区间
        while(i < j){
            do{
                i++;
            }while(arr[i] < p); //不要忘了分号;
            
            do{
                j--;
            }while(arr[j] > p);
            
            if(i < j){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        
        //3. 递归处理两边
        quickSort(arr, l, j);
        quickSort(arr, j+1, r);
        // 一定要是l~j 和 j+1 ~ r 和之前取的分界点arr[l] 保证不出边界问题
        
    }
}