算法导论 Python 快速排序

2020/1/25
算法代码
Python

Python 这语言本身执行效率实在堪忧···以前做题目的时候,发现同样是 2 千万次循环,同样的算法,Java 几百毫秒就解决了,Python 用了 7 秒,偶然在一篇文章看到了一个快排代码,据说是《算法导论》中的 Python 快排,当时觉得,哇塞,代码居然这么精简(虽然后来看到了更加精简的代码,我还是太菜了,还够不到大佬的后脚跟~)。

# 据说是《算法导论》中的快速排序

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)

def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1

首先是要知道快速排序的思路,从这个代码可以看出,每次排序用了一次循环,代码中的 l 就是 left, r 就是 right, 分别代表操作的列表的左下标和右下标,初始传入的下标就是 0 和 len(array)-1

partition 是分片的意思,其实在分片的时候,就是进行了一次排序了。

partition 函数中把列表最右边的值作为划分值,交换点下标为传入列表最右边 -1, 为什么是 -1, 而不是 l 呢,因为这个代码后面每一次交换位置分点的下标都会向右移,为了防止漏掉 l 下标,所以要先减一,第一次交换的时候 +1 就变成 l 下标了。当然代码也可以改成下面这种直接把 l 赋值给 i 的形式

def partition(array, l, r):
    x = array[r]
    i = l
    for j in range(l, r):
        if array[j] <= x:
            array[i], array[j] = array[j], array[i]
            i += 1
    array[i], array[r] = array[r], array[i]
    return i

for 循环是遍历下标从 l 到 r-1 的元素,由于下标为 r 的元素是我们的分片点,所以不需要进行比较,当遍历到的元素值小于划分值,就把这个元素向左边的 i 移动,这样到最后,所有小于划分值的元素都会在 i 下标位置的左边,而 i 下标位置右边的,都是大于划分值的,但是此时 i 下标的元素仍然是大于划分值的,我们要把划分的元素放到划分点,所以最后要把 i 下标的元素和划分元素(最右边那个没有被遍历到的元素)交换位置,这样就完成了分片,然后返回分片点的下标,然后回到 quick_sort 函数继续递归。

在 quick_sort 函数中的 q 是 partition 函数返回是划分点下标,所以已经不需要进行排序了,只需要对分片后的两边列表进行排序就行了,所以调用 quick_sort 函数 (quick_sort(array, l, q - 1)quick_sort(array, q + 1, r)), 继续对两边子列表进行排序,直到最后分片的两个元素排序好返回分片点下标,由于就剩下两个元素,所以排序完返回的下标肯定是这两个元素其中一个,这时传入 q-1 和另外一个下标到 quick_sort 已经无法满足if l < r了,所以该子列表排序完成,结束递归,等所有子列表都排序完,整个列表就从小到大排序好了。

当然我们也可以吧 partition 里的<=改成>=, 这样就是所有大于划分值的元素都在 i 下标位置的左边,列表将从大到小排序。

由于快速排序是原地排序,在 Python 里直接采取原列表交换元素的方式,按照 Python 语言的特性不需要进行返回,原本传入的列表就会被排序好,当然也就无法传入元组 (tuple) 了

Post Order
By Time : DESC
Article Statistics
Article: 35
Categories: 4
Tags: 18