快速排序

                    

i、j不相邻时，指向同一个下标
i、j相邻时，j 比 i 小

不管是否相邻，最后一次循环的if条件一定是 i>=j 来退出循环，即最后一次的 if(i<j) 不执行

按照 j 来划分,x = a[l + r >> 1]，分为 [ l，j ]、[ j + 1, r ]

按照 i 来划分,x = a[l + r + 1 >> 1]，分为 [ l，i - 1]、[ i, r ]

i 和 j 相互对应的，记住 j 就行

do i++; while(a[i] < x);
        会使得 a[l..i-1] <= x, a[i] >= x

do j--; while(a[j] > x);
        会使得 a[j+1..r] >= x, a[j] <= x

if(i < j) swap(q[i], q[j]);
        会使得 a[l..i] <= x, a[j..r] >= x

a[ j ] <= x 停住，a[ i ] >= x 停住，交换，a[ j ] >= x，j --

所以循环结束后，a[ l ... j ] <= x，a[ j + 1 ... r ] >= x

do while 先自增自减 ，i 从 l - 1 开始， j 从 r + 1 开始

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] a = new int[n];for (int i = 0; i < n; i ++ )a[i] = in.nextInt();quick_sort(a, 0, n - 1);for (int i = 0; i < n; i ++ )System.out.print(a[i] + "　");}static void quick_sort(int a[],int l, int r) {if(l >= r)return;int i = l - 1, j = r + 1, x = a[l + r >> 1];while(i < j) {do {i ++;}while(a[i] < x);do {j --;}while(a[j] > x);if(i < j) {int t = a[i];a[i] = a[j];a[j] = t;}}quick_sort(a,l,j);quick_sort(a,j + 1, r);}
}

第K个数

根据排序后左右两边的数字个数，选择一边进行查找 

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();int[] a = new int[n];for (int i = 0; i < n; i ++ )a[i] = in.nextInt();System.out.println(quick_sort(a, 0, n - 1, k));}static int quick_sort(int a[],int l, int r, int k) {if(l >= r)return a[l];int i = l - 1;int j = r + 1;int x = a[l + r >> 1];while(i < j) {do i ++; while(a[i] < x);do j --; while(a[j] > x);if(i < j) {int t = a[i];a[i] = a[j];a[j] = t;}}int l_cnt = j - l + 1;if(k <= l_cnt)return quick_sort(a,l,j,k);return quick_sort(a,j + 1, r,k - l_cnt);}
}