有许多不同版本的快速排序,它们以不同的方式选择枢轴。
- 始终选择第一个元素或最后一个元素作为枢轴
- 选择一个随机元素作为枢轴。
我已经实现使用 the last element as the pivot
一切工作正常,但当我试图实现相同的逻辑到中间元素,它没有工作良好。
这是我的python代码:
import random
import time
start = time.time()
def quickSort(a,l,r):
if(l<r):
p = partition(a,l,r)
quickSort(a,l,p-1)
quickSort(a,p+1,r)
def partition(a,l,r):
i = l-1
p = a[(l+(r-l))//2]
for j in range(l,r):
if a[j] <= p:
i += 1
a[i],a[j] = a[j],a[i]
a[i+1],a[r] = a[r],a[i+1]
return (i+1)
N = 10
a = [random.randint(1,100) for i in range(N)]
print(a)
quickSort(a,0,N-1)
print(a)
print("It took %s milli seconds"%((time.time()-start)*100))
输出
[88, 35, 55, 68, 96, 23, 44, 77, 78, 71]
[35, 55, 23, 68, 44, 77, 88, 96, 78, 71]
It took 1.5625953674316406 milli seconds
使用Hoare分区方案更适合使用中间值作为枢轴,并且Hoare分区方案通常比问题中使用的Lomuto分区方案更快。
def qsort(a, lo, hi):
if(lo >= hi):
return
p = a[(lo + hi) // 2] # pivot, any a[] except a[hi]
i = lo - 1
j = hi + 1
while(1):
while(1): # while(a[++i] < p)
i += 1
if(a[i] >= p):
break
while(1): # while(a[--j] < p)
j -= 1
if(a[j] <= p):
break
if(i >= j):
break
a[i],a[j] = a[j],a[i]
qsort(a, lo, j)
qsort(a, j+1, hi)
如上所述,如果您仍然希望使用Lomuto分区方案,请将中间元素与最后一个元素交换,并将代码与最后一个元素一起使用。