Python|快速排序

说明

• 排序的定义

对一序列对象根据某个关键字进行排序。

• 术语说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 ：一个算法执行所耗费的时间。

空间复杂度 ：运行完一个程序所需内存的大小。

n: 数据规模

In-place: 占用常数内存，不占用额外内存

代码语言：javascript复制

def quickSort(todoList):
    if len(todoList) >= 2:
        flag = todoList[0]
        maxList = []
        minList = []
        midList = []
        for item in todoList:
            if item > flag:
                maxList.append(item)
            elif item == flag:
                midList.append(flag)
            else:
                minList.append(item)
        return quickSort(minList)   midList   quickSort(maxList)
    else:
        return todoList

现在对10000个随机生成的数据进行排序，然后比较两者消耗的时间。

代码语言：javascript复制

t1=time.time()
new1=quickSort(randomList)
t2=time.time()
print(t2-t1)

t3=time.time()
new2=bubbleSort(randomList)
t4=time.time()
print(t4-t3)

快速排序：

0.025931119918823242

冒泡排序：

13.729837417602539

磁盘 内存 排序

0 人点赞