快速排序是利用分而治之的思想,算法的描叙看起来很容易让人理解,但想通过代码来高效的实现却不容易,主要是要考虑高效, 不能使用instert, 而应该使用在原地交换元素的方法来代替插入。从插入排序算法的实现就可以看出这点。

可以参考:数据结构(下) 邓俊辉教授 清华大学
快速排序

要实现选取一个基准数(key),比它大的都在它的右边,比它小的都在它的左边,
通常选取数组第一个元素为基准数,把它存到一个变量里面。
有两个指针,left指针初始指上数组头部, right指针初始指上数组尾部, 从数组前后两处开始比较,若尾部的元素比key大,则hight指针往中间跳一格(减去1),若比key小,则把right指针指上的元素存放在left指针的指向的位置
然后左边也如此,
最后左右指针到达同一位置, 把key 放到指针处,
文字过于难描述, 建议看邓俊辉教授的视频。

具体代码实现:

l = [4,5,3,2,8]


def quick_sort(lists, left, right):
    if left == right:
        return lists

    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left< right and lists[left] <= key:
            left +=1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left-1)
    quick_sort(lists, left+1, high)
    return lists

quick_sort(l, 0 , len(l)-1)

print(l)

标签: none

添加新评论