优化快速排序(在python中)

Question

我正在尝试使用python编写一个基于快速排序的排序算法。在这里，我给出了两个关于快速排序的代码……

def insertion_sort(arr, l, r):
""" binary insertion sort """
....
def partition_func(arr, l, r):
....

第一个

def traditional_quicksort(arr, l, r, partition, insertionsort):
while r-l > 16:
m = partition(arr, l, r)
if (m-l) < (r-m):
traditional_quicksort(arr, l, m-1, partition, insertionsort)
l = m + 1
else:
traditional_quicksort(arr, m+1, r, partition, insertionsort)
r = m - 1
insertionsort(arr, l, r)

第二个

def new_quicksort(arr, l, r, partition, insertionsort):
m = r+1
# usually m means the point of partition
# but if r-l > 32 then m won't mean the point of partition
while (r-l) > 32:
m = partition(arr, l, r)
pre_m = m
if (pre_m - l) < (r - pre_m):
m, _ = partition(arr, pre_m+1, r), new_quicksort(arr, l, pre_m-1, partition, insertionsort)
l = pre_m + 1
else:
m, _ = partition(arr, l, pre_m-1), new_quicksort(arr, pre_m+1, r, partition, insertionsort)
r = pre_m - 1
if m > r:
# that means m is not the point of partition
# and so we should use insertion sort from index l to r
insertionsort(arr, l, r)
else:
insertionsort(arr, l, m - 1)
insertionsort(arr, m + 1, r)

实际上，我不确定"，"在python中是如何工作的，但我猜测将分区函数和快速排序函数用"，"分隔可能是传统函数的优化版本。但我电脑上的结果显示了一些不同的东西。我从programiz.com复制了分区函数，并使用python的默认Timsort作为插入排序(只是为了临时测试(。使用timeit函数(数字=5，长度=131072，使用随机混洗进行混洗(，

traditional_quicksort:1.53832088s
new_quicksort:3.5858982s
(平均！(

这表明后一种比前一种慢。那么，new_quicksort是优化得不好，还是因为其他原因看起来很慢？

Answer 1

实际上我不确定'，'在python中是如何工作的，但我猜测用'，'分隔分区函数和快速排序函数可能是传统函数的优化版本。

在编程中猜测通常没有帮助。

那么，new_quicksort是优化得很差，还是因为其他原因看起来很慢？

while (r-l) > 32:
m = partition(arr, l, r)
pre_m = m
if (pre_m - l) < (r - pre_m):
m, _ = partition(arr, pre_m+1, r), new_quicksort(arr, l, pre_m-1, partition, insertionsort)
l = pre_m + 1
else:
m, _ = partition(arr, l, pre_m-1), new_quicksort(arr, pre_m+1, r, partition, insertionsort)
r = pre_m - 1

相当于

while (r-l) > 32:
m = partition(arr, l, r)
pre_m = m
if (pre_m - l) < (r - pre_m):
m = partition(arr, pre_m+1, r)
new_quicksort(arr, l, pre_m-1, partition, insertionsort)
l = pre_m + 1
else:
m = partition(arr, l, pre_m-1)
new_quicksort(arr, pre_m+1, r, partition, insertionsort)
r = pre_m - 1

我们看到，在除第一次循环运行之外的所有循环运行中，partition(arr, l, r)调用与上一次运行中的另一次partition()调用具有相同的参数值(由于l = pre_m + 1或r = pre_m - 1(；因此CCD_ 5缓慢的主要原因很可能是不必要地重复CCD_。