参考文献:
快速排序算法
快速排序(图解详细流程)
数组中的第K个最大元素

1. 排序流程

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:

  1. 首先设定一个分界值,通过该分界值将数组分成左右两部分。

  2. 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。

  3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

  4. 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

2. 排序步骤

设要排序的数组 A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序(partition)。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

1)设置两个变量 i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给 key,即 key=A[0]

3)从 j 开始向前搜索,即由后开始向前搜索 (j–),找到第一个小于 key 的值 A[j];

4)从 i 开始向后搜索,即由前开始向后搜索 (i++),找到第一个大于 key 的 A[i],将 A[i] 和 A[j] 的值交换;

5)重复第 3、4 步,直到 ij; (3,4步中,没找到符合条件的值,即 3 中 A[j] 不小于 key, 4 中 A[i] 不大于 key 的时候改变 j、i 的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候 i, j 指针位置不变。另外,ij 这一过程一定正好是 i++ 或 j-- 完成的时候,此时令循环结束)。

3. 排序演示

假设一开始序列 {xi} 是:5,3,7,6,4,1,0,2,9,10,8。

此时,ref=5,i=1,j=11,从后往前找,第一个比 5 小的数是 X8=2,因此序列为:2,3,7,6,4,1,0,5,9,10,8。

此时 i=1,j=8,从前往后找,第一个比 5 大的数是 X3=7,因此序列为:2,3,5,6,4,1,0,7,9,10,8。

此时,i=3,j=8,从第 8 位往前找,第一个比 5 小的数是 X7=0,因此:2,3,0,6,4,1,5,7,9,10,8。

此时,i=3,j=7,从第 3 位往后找,第一个比 5 大的数是 X4=6,因此:2,3,0,5,4,1,6,7,9,10,8。

此时,i=4,j=7,从第 7 位往前找,第一个比 5 小的数是 X6=1,因此:2,3,0,1,4,5,6,7,9,10,8。

此时,i=4,j=6,从第 4 位往后找,直到第 6 位才有比 5 大的数,这时,i=j=6,ref 成为一条分界线,它之前的数都比它小,之后的数都比它大,对于前后两部分数,可以采用同样的方法来排序。

4. 实现

public class Solution {
    public static int[] qsort(int arr[], int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i - 1 > start) arr = qsort(arr, start, i - 1);
        if (j + 1 < end) arr = qsort(arr, j + 1, end);
        return (arr);
    }

    public static void main(String[] args) {
        int arr[] = new int[]{3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321};
        int len = arr.length - 1;
        arr = qsort(arr, 0, len);
        for (int i : arr) {
            System.out.print(i + "\t");

        }
    }
}

5. Partition 的另一种实现

private int partition(int[] nums, int l, int r) {
    int x = nums[l];
    int k = l - 1; // k 一直指向 <=x 的最后一个下标
    for (int i = l; i <= r; i++) {
        if (nums[i] <= x) {
            swap(nums, ++k, i);
        }
    }
    swap(nums, k, l);
    return k;
}

6. 快速选择

参考 数组中的第K个最大元素

一个无序数组,快速选择第 k 大的数。 时间复杂度为 O(N),证明:我也不会。。

import java.util.Random;

class Solution {

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] nums, int l, int r, int index) {
        int q = randomPartition(nums, l, r);
        if (q == index) {
            return nums[q];
        }
        return q < index ? quickSelect(nums, q + 1, r, index) : quickSelect(nums, l, q - 1, index);
    }

    public int randomPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, i, l);
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int x = nums[l];
        int k = l - 1;
        for (int i = l; i <= r; i++) {
            if (nums[i] <= x) {
                swap(nums, ++k, i);
            }
        }
        swap(nums, k, l);
        return k;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}