排序算法之快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 实现一个简单的计时功能
import time
def clock(func):
def clocked(*args):
t0 = time.perf_counter()
result = func(*args)
t1 = time.perf_counter()
elapsed = t1 - t0
name = func.__name__
args_str = ','.join(repr(arg) for arg in args)
print('[%0.8fs] %s(%s) ->%s' % (elapsed,name,args_str,result))
return result
return clocked

@clock
def factorial(n):
return 1 if n<2 else n*factorial(n-1)

factorial(10)
1
2
3
4
5
6
7
8
9
10
11
12
[0.00000213s] factorial(1)  ->1
[0.00332171s] factorial(2) ->2
[0.00479304s] factorial(3) ->6
[0.00680697s] factorial(4) ->24
[0.00944457s] factorial(5) ->120
[0.01236164s] factorial(6) ->720
[0.01476598s] factorial(7) ->5040
[0.01721157s] factorial(8) ->40320
[0.01966641s] factorial(9) ->362880
[0.02183039s] factorial(10) ->3628800
Out[1]:
3628800

基本版快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@clock
def quickSort(arr):
if len(arr)<2:
return arr
elif len(arr) == 2:
if arr[0]>arr[1]:
return arr[::-1]
left = []
right = []
pivotlist = []
pivot = arr[0]
for x in arr:
if x < pivot:
left.append(x)
elif x > pivot:
right.append(x)
else:
pivotlist.append(x)

left = quickSort(left)
right = quickSort(right)

return left + pivotlist + right

改进版排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 改进算法,基准值设为随机选定
@clock
def quickSortPro(arr):
if len(arr)<2:
return arr
elif len(arr) == 2:
if arr[0]>arr[1]:
return arr[::-1]
left = []
right = []
pivotlist = []
pivot = random.choice(arr)
for x in arr:
if x < pivot:
left.append(x)
elif x > pivot:
right.append(x)
else:
pivotlist.append(x)

left = quickSort(left)
right = quickSort(right)

return left + pivotlist + right

两种算法对比

1
2
3
4
5
6
7
# 生成随机数组
arr = []
for x in range(100):
arr.append(random.randrange(1000))
arr_pro = arr

quickSort(arr)

基本版快速排序结果

1
[0.02774133s] quickSort([154, 544, 544, 753, 542, 854, 976, 704, 356, 239, 550, 758, 139, 189, 94, 617, 554, 507, 638, 368, 543, 244, 588, 166, 741, 310, 955, 340, 860, 395, 178, 567, 600, 325, 372, 285, 422, 539, 202, 171, 909, 322, 874, 201, 679, 924, 112, 851, 578, 335, 783, 656, 439, 456, 131, 753, 559, 13, 485, 693, 458, 293, 98, 255, 188, 264, 110, 734, 974, 142, 861, 660, 37, 250, 459, 7, 279, 795, 667, 152, 833, 59, 261, 779, 717, 335, 773, 532, 129, 280, 546, 499, 31, 629, 383, 921, 268, 736, 241, 655])  ->[7, 13, 31, 37, 59, 94, 98, 110, 112, 129, 131, 139, 142, 152, 154, 166, 171, 178, 188, 189, 201, 202, 239, 241, 244, 250, 255, 261, 264, 268, 279, 280, 285, 293, 310, 322, 325, 335, 335, 340, 356, 368, 372, 383, 395, 422, 439, 456, 458, 459, 485, 499, 507, 532, 539, 542, 543, 544, 544, 546, 550, 554, 559, 567, 578, 588, 600, 617, 629, 638, 655, 656, 660, 667, 679, 693, 704, 717, 734, 736, 741, 753, 753, 758, 773, 779, 783, 795, 833, 851, 854, 860, 861, 874, 909, 921, 924, 955, 974, 976]

改进版快速排序结果

1
quickSortPro(arr_pro)
1
[0.02270722s] quickSortPro([154, 544, 544, 753, 542, 854, 976, 704, 356, 239, 550, 758, 139, 189, 94, 617, 554, 507, 638, 368, 543, 244, 588, 166, 741, 310, 955, 340, 860, 395, 178, 567, 600, 325, 372, 285, 422, 539, 202, 171, 909, 322, 874, 201, 679, 924, 112, 851, 578, 335, 783, 656, 439, 456, 131, 753, 559, 13, 485, 693, 458, 293, 98, 255, 188, 264, 110, 734, 974, 142, 861, 660, 37, 250, 459, 7, 279, 795, 667, 152, 833, 59, 261, 779, 717, 335, 773, 532, 129, 280, 546, 499, 31, 629, 383, 921, 268, 736, 241, 655])  ->[7, 13, 31, 37, 59, 94, 98, 110, 112, 129, 131, 139, 142, 152, 154, 166, 171, 178, 188, 189, 201, 202, 239, 241, 244, 250, 255, 261, 264, 268, 279, 280, 285, 293, 310, 322, 325, 335, 335, 340, 356, 368, 372, 383, 395, 422, 439, 456, 458, 459, 485, 499, 507, 532, 539, 542, 543, 544, 544, 546, 550, 554, 559, 567, 578, 588, 600, 617, 629, 638, 655, 656, 660, 667, 679, 693, 704, 717, 734, 736, 741, 753, 753, 758, 773, 779, 783, 795, 833, 851, 854, 860, 861, 874, 909, 921, 924, 955, 974, 976]

结论

1
2
3
4
# 固定选择,快排  0.02075231s
# 随机选择,快排 0.02785867s
# 随机选择基准值并不能保证算法速度的提高
# 随机选择,可以保证快速排序不会出现极端情况,因此,它的性能趋于中间,稳定状态

本文标题:排序算法之快速排序

文章作者:定。

发布时间:2017年6月22日 - 21时06分

本文字数:4,295字

原始链接:http://cocofe.cn/2017/06/22/排序算法之快速排序/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。