快速排序与快速选择算法

快速排序算法步骤：

1. 找到分界点x，x可以为q[L],q[L+R],q[R];
2. 左边所有数Left <= x,右边所有数Right >= x;
3. 递归排序Left，递归排序Right。

以下为两种方法实现快速排序

• 方法一：填坑法

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void quickSort(int[] data, int begin, int end){
        if(begin >= end) return;
        int l = data[begin];
        int index = begin;//首先初始化一个分界点
        int i = begin,j = end;
        while(i < j){//开始填坑
            while(j > index && data[j] >= l) j--;
            if(i < j) {// 如果查找到某一个数小于l，说明需要填坑
                data[index] = data[j];
                index = j;//用于填坑的数字的下标为新的坑
            }
            while(i < index && data[i] <= l) i++;
            if(i < j) {// 如果查找到某一个数大于L，则填坑
                data[index] = data[i];
                index = i;
            }
        }
        data[index] = l;//最后总会有一个坑，将之前记录的分界点所记录的数填在这里，那么可知概述左边的数 <= l,该数右边的数 >= r。
        quickSort(data,begin,index-1);
        quickSort(data,index+1,end);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.valueOf(buffer.readLine());
        int[] data = new int[k];
        String input = buffer.readLine();
        String[] inputs = input.split(" "); 
        for(int i = 0; i < k; i++)
            data[i] = Integer.valueOf(inputs[i]);
        quickSort(data,0,k-1);
        for(int i = 0; i < k; i++)
            System.out.print(data[i]+" ");
    }
}

• 方法二，左右值交换法

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void quickSort(int[] data, int begin, int end){
        if(begin >= end) return;
        int mid = data[end];//首先选择一个分界点，该值的选择有一定的考虑，否则会陷入无限递归
        int i = begin-1, j = end+1;
        while(i < j){
            do{i++;}while(data[i] < mid);//从左往右找到一个 >= 分界点的值
            do{j--;}while(data[j] > mid);//从右往左找到一个 <= 分界点的值
            if(i < j){//如果 i >= j 说明已经全部遍历完成，否则，将左右值交换，这样就可以让左边的值 <= 分界点，右边的值 >= 分界点
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        quickSort(data,begin,i-1);//这里使用i，还是j是与上面分界点的选择相关的。如果选择错误那么在有两个数的时候会导致无限递归。同样这里使用i-1与i或者i与i+1也是需要考虑的。因为下标i表示i左侧的节点均 <= mid，并不包括i，i有可能大于mid，所以在这里需要使用i-1把第i个节点放到后面的数组里。
        quickSort(data,i,end);
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.valueOf(buffer.readLine());
        int[] data = new int[k];
        String input = buffer.readLine();
        String[] inputs = input.split(" "); 
        for(int i = 0; i < k; i++)
            data[i] = Integer.valueOf(inputs[i]);
        quickSort(data,0,k-1);
        for(int i = 0; i < k; i++)
            System.out.print(data[i]+" ");

    }
}

快速选择算法步骤：

1. 设定分界点x，x可以为q[L],q[L+R],q[R];
2. 使得左边所有数Left <= x,右边所有数Right >= x;
3. 如果 k < Left 最右边点的下标，那么递归循环Left，否则递归循环Right。

算法整体与快速排序相同只是在递归的时候加了一个条件判断

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
    public static int quickselect(int[] nums,int begin,int end,int k){
        if(begin >= end){return nums[k];}
        int x = nums[begin];
        int i = begin-1,j = end+1;
        while(i<j){
            while(nums[++i] < x);
            while(nums[--j] > x);
            if(i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        if(k<=j)  return quickselect(nums,begin,j,k);
        else return quickselect(nums,j+1,end,k);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        String t1 = buffer.readLine();
        String[] t1_ar = t1.split(" ");
        String t2 = buffer.readLine();
        String[] t2_ar = t2.split(" ");
        int n = Integer.valueOf(t1_ar[0]);
        int k = Integer.valueOf(t1_ar[1]);
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = Integer.valueOf(t2_ar[i]);
        }

        System.out.print(quickselect(nums,0,n-1,k-1));

    }
}