快速排序之三路快排-实例分解

在笔者的另一篇快速排序语义化解法与改进-python描述博文中介绍了快速排序算法,但当笔者用测试用例对上述解法进行测试时发现一个很严重的问题,在使用有序或者近乎有序的数组测试时,算法的执行时间大大增加,经过分析发现:原来该算法O(nlogn)的复杂度会退化成为O(n^2),这显然是和快排这个名称不想符的,于是笔者又经过分析与查阅资料了解到了所谓三路快排,该算法应用更加广泛,甚至Java将三路快排作为系统库中默认的排序算法。

简介

三路快排要做的事情,其实就是将数组分成三部分:小于v,等于v和大于v,之后递归的对小于v和大于v部分进行排序就好了。

接下来通过一个leetcode上的实际案例演示三路快排的思路

案例

题目:有一个数组,其中的元素取值只有可能是0,1,2。为这样一个数组排序。(leetcode75)

注意:建议先别急着看笔者提供的参考代码,可以先用自己想到的方法,如一般的排序方法,暴力的枚举法等方法亲手编码,试着解决该问题(一定要亲自动手),然后在把你的解法和三路快排对比,这样才能更加深刻的理解三路快排的巧妙之处。

代码:

class Solution(object):
    def sort(self, arr):
        llength = len(arr)
        if length <= 1:
            return arr
        lefl = -1
        right = length
        i = 0
        while i != right:
            if arr[i] == 0:
                arr[i] = 1
                i += 1
                lefl += 1
                arr[lefl] = 0
            elif arr[i] == 1:
                i += 1
            elif arr[i] == 2:
                right -= 1
                arr[i], arr[right] = arr[right], arr[i]
        return arr

该解法中,我们将所有的0放到了1的左边,将所有的2放到了1的右边,最终只扫描一遍数组就完成了所有排序。

注意:

  1. 注意<V>V时的边界条件,初始化时,应保证=V部分覆盖整个数组
  2. 循环终止条件应该是=V部分和>V部分重叠,此时整个数组遍历完毕

本章小结

本章通过一个小例题展现了三路快排的基本思路,但是提供的参考代码不够优雅,应该还有改进的地方。如果你有更好的解法或者思路,欢迎在下面给我留言,我们一起讨论学习。

-- END

暂无评论~~