python实现快速排序的两种方法

本文最后更新于:2020年3月23日 下午

代码环境:python3.6

递归实现

步骤

  • 从序列中挑出任意一个元素为pivot,此处选择序列最后一个元素,如果更改,需要相应变更以下步骤内容;
  • 设置两个指针leftright,指向序列的最左和最右两个元素;
  • left开始,找到第一个比pivot大的元素;切换到right,找到第一个比pivot小的元素;
  • leftright此时指向的元素互换;
  • 重复1-4步骤,直到left==right,将pivotleft对应的元素互换,这样以pivot分割左右两个区,左边元素都比pivot小,右边元素都比pivot大;
  • 将两个分区分别递归重复1-5步骤,直到不可再分区,递归条件就是start<end

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def partition(mylist, start, end):
# 若选其他元素作为pivot,下面的while内容需要相应更改
pivot = mylist[end]
left = start
right = end

while left < right:
while left < right and mylist[left] <= pivot:
left += 1
while left < right and mylist[right] >= pivot:
right -= 1
if left != right:
mylist[left], mylist[right] = mylist[right], mylist[left]

mylist[end], mylist[left] = mylist[left], pivot
return left


def quick_sort(mylist, start, end):
"""
mylist: 待排序的 list
start: mylist第一个元素索引
end: mylist最后一个元素索引
"""
if start < end:
mid = partition(mylist, start, end)
quick_sort(mylist, start, mid - 1)
quick_sort(mylist, mid + 1, end)


if __name__ == "__main__":
mylist = [12, 33, 199, 0, 54, 77, 11, 54, 9, 7]
quick_sort(mylist, 0, len(mylist) - 1)
print(f'快速排序后:{mylist}')

非递归实现

绝大多数用递归实现的问题,都可以用的方式来代替。

为什么?因为我们代码中一层层的方法调用,本身就是一个函数栈,每次进入一个新方法,就相当于入栈;每次有方法返回,就相当于出栈。

所以,我们可以利用栈存储每一次调用方法的参数。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Stack():
"""简单实现一个栈,本质就是个list"""
def __init__(self):
self.items = []

def is_empty(self):
return self.items == []

def push(self, item):
self.items.append(item)

def pop(self):
return self.items.pop()


# 此方法与上面例子一样,保持不变
def partition(mylist, start, end):
# 若选其他元素作为pivot,下面的while内容需要相应更改
pivot = mylist[end]
left = start
right = end

while left < right:
while left < right and mylist[left] <= pivot:
left += 1
while left < right and mylist[right] >= pivot:
right -= 1
if left != right:
mylist[left], mylist[right] = mylist[right], mylist[left]

mylist[end], mylist[left] = mylist[left], pivot
return left


def quick_sort(mylist):
stack = Stack()
start = 0
end = len(mylist) - 1

if start < end:
stack.push((start, end))
while not stack.is_empty():
start, end = stack.pop()
mid = partition(mylist, start, end)
if start < mid - 1:
stack.push((start, mid - 1))
if mid + 1 < end:
stack.push((mid + 1, end))