Quicksort能够更快地排序更大的数字？

Question

我正在搞乱Python试图练习我的排序算法并发现一些有趣的东西.

我有三个不同的数据:

• x =要排序的数字的数量
• y =数字所在的范围(所有随机生成的int)
• z =排序所需的总时间

当:
x = 100000且
y =(0,100000)时,则
z = 0.94182094911秒

当:
x = 100000且
y =(0,100),则
z = 12.4218382537秒

当:
x = 100000且
y =(0,10),则
z = 110.267447809秒

有任何想法吗？

码:

import time
import random
import sys

#-----Function definitions

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    for items in array:
        if items <= pivotVal:
            smaller.append(items)
        else:
            greater.append(items)
    return concat(quickSort(smaller), pivotVal, quickSort(greater))

def concat(before, pivot, after):
    new = []
    for items in before:
        new.append(items)
    new.append(pivot)
    for things in after:
        new.append(things)
    return new

#-----Variable definitions
list = []
iter = 0
sys.setrecursionlimit(20000)
start = time.clock() #start the clock

#-----Generate the list of numbers to sort
while(iter < 100000):
    list.append(random.randint(0,10))  #modify this to change sorting speed
    iter = iter + 1
timetogenerate = time.clock() - start #current timer - last timer snapshot

#-----Sort the list of numbers
list = quickSort(list)
timetosort = time.clock() - timetogenerate #current timer - last timer snapshot

#-----Write the list of numbers
file = open("C:\output.txt", 'w')
for items in list:
    file.write(str(items))
    file.write("\n")
file.close()
timetowrite = time.clock() - timetosort #current timer - last timer snapshot

#-----Print info
print "time to start: " + str(start)
print "time to generate: " + str(timetogenerate)
print "time to sort: " + str(timetosort)
print "time to write: " + str(timetowrite)
totaltime = timetogenerate + timetosort + start
print "total time: " + str(totaltime)

-------------------修订新代码----------------------------

def quickSort(array): #random pivot location quicksort. uses extra memory.
    smaller = []
    greater = []
    equal = []
    if len(array) <= 1:
        return array
    pivotVal = array[random.randint(0, len(array)-1)]
    array.remove(pivotVal)
    equal.append(pivotVal)
    for items in array:
        if items < pivotVal:
            smaller.append(items)
        elif items > pivotVal:
            greater.append(items)
        else:
            equal.append(items)
    return concat(quickSort(smaller), equal, quickSort(greater))

def concat(before, equal, after):
    new = []
    for items in before:
        new.append(items)
    for items in equal:
        new.append(items)
    for items in after:
        new.append(items)
    return new

Answer 1

我认为这与枢轴的选择有关.根据分区步骤的工作方式,如果您有大量重复值,则在遇到许多重复项时,您的算法可能会退化为二次行为.例如,假设您正在尝试快速分配此流:

 [0 0 0 0 0 0 0 0 0 0 0 0 0]

如果您不小心执行分区步骤,则可能会很快退化.例如,假设您选择枢轴作为第0个,留下数组

 [0 0 0 0 0 0 0 0 0 0 0 0]

分区.您的算法可能会说较小的值是数组

 [0 0 0 0 0 0 0 0 0 0 0 0]

而较大的值是数组

 []

这是导致快速排序退化为O(n ²)的情况,因为每次递归调用仅将输入的大小缩小一(即,通过拉出枢轴元素).

我注意到在您的代码中,您的分区步骤确实是这样做的:

for items in array:
    if items <= pivotVal:
        smaller.append(items)
    else:
        greater.append(items)

给定一个流是同一个元素的一大堆副本,这将把它们全部放入一个数组中进行递归排序.

当然,这似乎是一个荒谬的案例 - 这与减少数组中值的数量有何关联？ - 但是当你对许多不同的元素进行排序时,它确实会出现.特别是,在几次分区之后,您可能会将所有相等的元素组合在一起,这将带您进入这种情况.

有关如何防止这种情况发生的讨论,Bob Sedgewick和Jon Bentley谈到如何在存在重复元素的情况下修改分区步骤以便快速工作.它与Dijkstra的荷兰国旗问题有关,他们的解决方案非常聪明.

一个可行的选项是将输入分为三组 - less,equal和more.一旦你以这种方式打破了输入,你只需要对越来越少的组进行排序; 相等的组已经排序.以上链接显示了如何在原地或多或少地执行此操作,但由于您已经使用了不合适的快速排序,因此修复应该很容易.这是我的尝试:

for items in array:
    if items < pivotVal:
        smaller.append(items)
    elif items == pivotVal:
        equal.append(items)
    else:
        greater.append(items)

我从来没有在我的生活中写过一行Python,BTW,所以这可能是完全非法的语法.但我希望这个想法很明确!:-)