python面试：实现快速排序（python经典编程案例）

参考链接： Python中的快速排序Quicksort

import random

import timeit

def randomList(n):

    '''返回一个长度为n的整数列表，数据范围[0,1000) '''

    iList = []

    for i in range(n):

        iList.append(random.randrange(1000))

    return iList

def quickSort(iList):

    if len(iList) <= 1:

        return iList

    left = []

    right = []

    for i in iList[1:]:

        if i <= iList[0]:

            left.append(i)

        else:

            right.append(i)

    return quickSort(left) + [iList[0]] + quickSort(right)

if __name__ == "__main__":

    iList = randomList(20)

    print(iList)

    print(quickSort(iList))

    print(timeit.timeit("quickSort(iList)", "from __main__ import quickSort,iList", number=100))

执行结果如下： 

[570, 881, 704, 70, 871, 423, 583, 411, 856, 999, 220, 991, 877, 301, 795, 290, 95, 13, 289, 419]

[13, 70, 95, 220, 289, 290, 301, 411, 419, 423, 570, 583, 704, 795, 856, 871, 877, 881, 991, 999]

0.0019199240000000034