【算法】快排及其partition函数（Java）

快排简单来说就是选取一个基准数，然后以基准数为目标将比它小的数都移到它的左边，比它大的数都移到它的右边，这就是快排的partition，然后基于递归的思想达到完全排序的目的，然而快排的partition思想可以应用到各种面试题的巧妙解法中，达到事半功倍的效果，比如找到数组中第K大的数，用partition将时间复杂度降到O(n).具体的应用我们后续再谈，本文只给出基于partition函数的快排的Java写法。

partition函数

public static int partition(int[] arr, int start, int end) {
        int point = arr[end];
        int i = start;
        int j = end;
        while (i < j) {
            while(i < j && arr[i] <= point) ++i;
            while(i < j && arr[j] >= point) --j;
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i];
        arr[i] = arr[end];
        arr[end] = temp;
        return i;
    }

基于partition的快排

public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int p = partition(arr, start, end);
            quickSort(arr, start, p-1);
            quickSort(arr, p+1, end);
        }
    }

测试

public static void main(String[] args) {
        int[] arr= new int[]{1,4,6,5,8,23,5};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

链接

数组中出现字数超过一半的数字