支持重复元素,理解容易,但不是原地排序方法.
代码参上
# -*- coding:utf-8 -*-
def quick_sort(list_o):
# 不可能发生的情况
if len(list_o) == 0 or list_o is None:
print("enter len 0!!it's impossile!")
return list([])
# 子列表长度为1
elif len(list_o) == 1:
return list_o
# 子列表长度为2
elif len(list_o) == 2:
if list_o[0] > list_o[1]:
list_o.reverse()
return list_o
# 子列表长度>=3
else:
# 针对很多元素重复,去重后只有2个不同元素的情况
if len(set(list_o)) == 2:
# 使用最大值最为分割
bigger = max(set(list_o))
# 针对最大值也有多个的情况
bigger_count = list_o.count(bigger)
# 将最大的元数移动到列队尾部
for i in range(bigger_count):
bigger_index = list_o.index(bigger)
should_be_index = len(list_o)-i-1
if bigger_index != should_be_index:
list_o[bigger_index], list_o[should_be_index] = list_o[should_be_index], list_o[bigger_index]
return list_o
# 针对很多元素重复,去重后只有1个不同元素的情况
elif len(set(list_o)) == 1:
return list_o
# 去重后大于等于3个不同元素的子列表
else:
# 尝试取中间的元素作为分割
split_elem_id = int(len(list_o)/2)
# 当分割元素是该子列表的最大值或者最小值时,换一个元素做分割,避免子列表无法继续分割的情况发生
while list_o[split_elem_id] == max(list_o) or list_o[split_elem_id] == min(list_o):
split_elem_id -= 1
left_list = []
right_list = []
split_elem = list_o[split_elem_id]
print("split element is %s" % split_elem)
# 进行分割
for i in list_o:
if i <= split_elem:
left_list.append(i)
else:
right_list.append(i)
print("left is {left_list},right is {right_list}".format(left_list=left_list, right_list=right_list))
# 递归排序并合并子列表
return quick_sort(left_list)+[split_elem]+quick_sort(right_list)
if __name__ == "__main__":
a = [1,3,45,65,21,12,2,2,78,54,56,23]
b = quick_sort(a)
print b
print "-----------------------------------------------"
aa = [1,11,1,1,1,1,1,1,1,1,1,11,1,1,1,1,1,1,11,11]
bb = quick_sort(aa)
print bb
print "-----------------------------------------------"
aaa = [0,0,0,0,0,0,2,2,2,2,2,1,1,1,1,1,1]
bbb = quick_sort(aaa)
print bbb
print "-----------------------------------------------"
ss = ["aa", "a", "a","aa", "aaa","b","f","e"]
ssbb = quick_sort(ss)
print(ssbb)
运行一下:
C:\Python27\python.exe D:/代码/python-DP/QuickSort.py
split element is 2
left is [1, 2, 2],right is [3, 45, 65, 21, 12, 78, 54, 56, 23]
split element is 12
left is [3, 12],right is [45, 65, 21, 78, 54, 56, 23]
split element is 65
left is [45, 65, 21, 54, 56, 23],right is [78]
split element is 54
left is [45, 21, 54, 23],right is [65, 56]
split element is 45
left is [45, 21, 23],right is [54]
split element is 23
left is [21, 23],right is [45]
[1, 2, 2, 2, 3, 12, 12, 21, 23, 23, 45, 45, 54, 54, 56, 65, 65, 78]
-----------------------------------------------
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 11, 11, 11]
-----------------------------------------------
split element is 1
left is [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],right is [2, 2, 2, 2, 2]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
-----------------------------------------------
split element is aaa
left is ['aa', 'a', 'a', 'aa', 'aaa'],right is ['b', 'f', 'e']
split element is aa
left is ['aa', 'a', 'a', 'aa'],right is ['aaa']
split element is e
left is ['b', 'e'],right is ['f']
['a', 'a', 'aa', 'aa', 'aa', 'aaa', 'aaa', 'b', 'e', 'e', 'f']
Process finished with exit code 0
