简介
快速排序被评为20世纪十大算法之一,最早由图灵奖获得者Tony Hoare设计出来,很牛。。玩编程的老铁们应该掌握它。
基本思想
(摘抄自《大话数据结构》)
快速排序的基本思想是:
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以带到整个序列有序的目的。
Python实现
以下给出Python实现版本,结合打印信息应该就能看明白了。
# coding=utf-8
def swap(lst, left, right):
lst[left], lst[right] = lst[right], lst[left]
def parititon(lst, left, right):
key = lst[left]
while left < right:
if left < right and key <= lst[right]:
right = right - 1
swap(lst, left, right)
if left < right and lst[left] <= key:
left = left + 1
swap(lst, left, right)
print 'left: {} right: {}'.format(left, right)
print lst
return left
def Qsort(lst, left, right):
piviot = 0
if left < right:
piviot = parititon(lst, left, right)
Qsort(lst, left, piviot - 1)
Qsort(lst, piviot + 1, right)
def Quicksort(lst):
Qsort(lst, 0, len(lst) - 1)
l = [1, 20, 3, 50, 40, 70, 23, 100, 23]
Quicksort(l)
Console输出:
left: 0 right: 0
[1, 20, 3, 50, 40, 70, 23, 100, 23]
left: 2 right: 2
[1, 3, 20, 50, 40, 70, 23, 100, 23]
left: 6 right: 6
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 3 right: 3
[1, 3, 20, 23, 40, 23, 50, 100, 70]
left: 5 right: 5
[1, 3, 20, 23, 23, 40, 50, 100, 70]
left: 8 right: 8
[1, 3, 20, 23, 23, 40, 50, 70, 100]
网友评论