首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|快速排序

Python|快速排序

作者头像
福贵
发布2020-02-17 14:43:51
4010
发布2020-02-17 14:43:51
举报
文章被收录于专栏:菜鸟致敬菜鸟致敬

说明

  • 排序的定义

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

  • 术语说明

稳定 :如果a原本在b前面,而a=b,排序之后a仍然在b的前面;

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

内排序 :所有排序操作都在内存中完成;

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

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

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

n: 数据规模

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

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个随机生成的数据进行排序,然后比较两者消耗的时间。

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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-01-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Python与MySQL 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档