我正在尝试使用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函数(number=5,length=131072,使用random.shuffle进行shuffled),
传统快速排序:1.53832088 s
新建快速排序:3.588982 s
(平均!)
结果表明,后者比前者慢。那么,新的快速排序是否优化得很差,或者由于其他原因,它看起来很慢?
现在,关于优化。。。。。据我所知,在小数组中,二进制插入排序比快速排序快,但小意味着什么?16,32,64还是别的什么?
您已经看到,我将函数insertionsort和partition作为输入。我的逻辑是,通过这样做,我把这两个函数都放在本地范围内,据我所知,本地函数比全局函数快。我说得对吗?
另外,python闭包(如果可以在这里实现)而不是递归,如果这是一个更好的选择呢?
抱歉问了很多问题。最后一件事。。。。如何通过保持稳定性来进行分区?我这样想,创建一个大小为r-l+1的列表。维护三个变量,主列表上的a1表示它左边的所有元素都小于pivot,临时列表上的a2和a3,a2左边的所有元素都大于pivot,a3右边的所有元素都等于pivot(a3的第一个值是len(temp_array)-1)。然后将a3和len(temp_array)-1之间的所有元素反向复制到主数组,并将0和a2之间的所有元素以直线方式复制回来。如果这是一个很好的选择,那么通过这样的划分算法是否仍然有效?
谢谢!!!
暂无答案!
目前还没有任何答案,快来回答吧!