Java教程

排序算法5 - 快速排序

本文主要是介绍排序算法5 - 快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

如果你还不了解快速排序,强烈推荐你可以先移步到我的另外一篇博客 快速排序的引入 — 荷兰国旗问题

算法思路

我们先看看快排 1.0 的算法思路:

我们每次选择最后一个元素作为我们的基准值,然后我们将小于等于基准值的放在基准值左边,大于基准值的放在基准值右边,这时基准值的位置已经排好 (因为小于等于基准值的已经都在基准值的左边,大于基准值的已经在基准值的右边)

再分别递归基准值左边部分和右边部分;因为每次递归总能使一个数变得有序,所以多次递归最终能使数组变得有序

现在看看快排 2.0 的算法思路:

快排 2.0 类似荷兰国旗问题,我们同样选择每次最后一个元素作为我们的基准值,这次我们将等于基准值的放中间,小于基准值的放左边,大于基准值的放右边,这样我们一次就可以完成一堆等于基准值的位置的排序

再分别递归基准值左边部分和右边部分;因为每次递归总能使一堆数变得有序,所以多次递归最终能使数组变得有序

总结:

无论快排 1.0 还是快排 2.0,算法时间复杂度都是 O(N²),因为我们可以举出一个最差的例子:arr = [1, 2, 3, 4, 5, 6, 7, 8, 9],全部范围中我们以最后一个元素 9 作为基准值进行划分,这一轮我们只搞定了 9 ,没有右侧区域,只有左侧区域;第二轮只搞定了 8,没有右侧区域,只有左侧区域...依次类推,每次都只搞定了一个数,每次比较次数从 n-1 到 1,为等差数列,所以时间复杂度为 O(N²)

造成这种情况的原因在于划分值打的很偏,最好的划分值为正好打在中间,使左右两侧递归的规模差不多,这时候 T(N) = 2T(N/2) + O(N) ( 这个 O(N) 就是 partition 所需的时间复杂度,在完成荷兰国旗分两类[小于等于、大于]和分三类[小于、等于、大于]时,时间复杂度都为 O(N),有困惑的小伙伴可以去看看我的这篇博客 快速排序的引入 — 荷兰国旗问题)

我们都知道这种式子得到的时间复杂度为 O(NlogN),划分值如果打偏,就会逐渐退化成 O(N²)

因为我们总是拿最后一个元素作为划分值,所以我们总能举出最差情况的例子,因此我们引出快排 3.0版本

快排 3.0 的算法思路:

我们在数组中随机选一个数作为划分值,这样好情况和坏情况出现的可能性是一样的,是等概率事件,由数学期望求概率累加得到这个算法时间复杂度为 O(NlogN) , 具体怎么求,感兴趣的小伙伴可以自己搜索一下

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 2, 1, 6, 4, 4, 7, 5};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            // 得到随机数作为划分值
            int num = arr[(int) (Math.random() * (R - L + 1))];
            int[] p = partition(arr, L, R, num);
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }

    public static int[] partition(int[] arr, int L, int R, int num) {
        int less = L;
        int more = R;
        while (L < more + 1){
            if (arr[L] < arr[R]) {
                swap(arr, less++, L++);
            }else if (arr[L] > arr[R]) {
                swap(arr, more--, L);
            }else {
                L++;
            }
        }
        return new int[]{less, more};
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

输出结果如下

快速排序输出结果

如果我们已经了解了荷兰国旗问题的解法,那快排简直就是小 case 了,如果有看不懂 partition 方法的小伙伴,可以去 快速排序的引入 — 荷兰国旗问题相关代码部分 看看对应的代码注释

最后

空间复杂度

我们已经知道快速排序的时间复杂度为 O(NlogN),那么它的空间复杂度为多少呢?快排使用了递归,在最优情况下,使用到的栈空间为 O(logN), 最坏的情况下为 O(N),而好情况和坏情况出现的可能性是一样的,是等概率事件,最后可以得到平均空间复杂度为 O(logN)(具体求法,感兴趣的小伙伴可以自己研究一下)

算法稳定性

该算法是不稳定的算法,因为元素的交换是跳跃进行的

欢迎来逛逛我的博客 mmimo技术小栈

这篇关于排序算法5 - 快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!