基于python的冒泡排序和选择排序

0.产生7000长度的乱序列表

import random

a_list = list(range(1,7000 + 1))
normal_list = random.sample(a_list, k=len(a_list))
normal_list[:5]

上面一段代码的运行结果如下,因为是随机打乱顺序,读者运行结果会不同:

[2780, 397, 5063, 6494, 1245]

0.1 保存此乱序列表

import pickle

with open('normal_list.pickle', 'wb') as file:
    pickle.dump(normal_list, file)

0.2 加载此乱序列表

import pickle

with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)

0.3 计时装饰器

装饰器是python的高级用法,初学者需要单独学习1天才能理解并且熟练运用。 读者如果不理解本节内容,不影响后续内容的理解。 此装饰器只是计算函数运行花费的时间,读者可以自己用其他方法实现相同效果。

from time import time

def timer(func):
    def inner(*args,**kwargs):
        start = time()
        result = func(*args,**kwargs)
        end = time()
        usedTime = 1000 * (end - start)
        print("%s function used %.2f ms" %(func.__name__,usedTime))
        return result
    return inner

1.冒泡排序

@timer
def bubble_sort(normal_list):
    length = len(normal_list)
    for i in range(length, 1, -1):
        for j in range(0, i-1):
            if normal_list[j] > normal_list[j+1]:
                normal_list[j], normal_list[j+1] = normal_list[j+1], normal_list[j]
        
with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)        
bubble_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])

上面一段代码的运行结果如下:

bubble_sort function used 7858.98 ms [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]

2.选择排序

@timer
def select_sort(normal_list):
    length = len(normal_list)
    new_list = []
    for i in range(length, 1, -1):
        max_index = 0
        max_value = normal_list[0]
        for j in range(1, i):
            if normal_list[j] > max_value:
                max_value = normal_list[j]
                max_index = j
        normal_list[i-1], normal_list[max_index] = normal_list[max_index], normal_list[i-1] 

with open('normal_list.pickle', 'rb') as file:
    normal_list = pickle.load(file)        
select_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])

上面一段代码的运行结果如下:

select_sort function used 2018.90 ms [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]

3.结论

虽然冒泡排序和选择排序的时间复杂度都是O(n^2),但是经过实践检验,在python实现2种排序算法后,选择排序花费的时间明显第冒泡排序花费的时间。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

IF函数——放松工作,享受生活!

今天跟大家分享一个简单却实用、高效的逻辑函数——IF函数。 ▼ IF函数可以简化很多我们数据处理过程中的重复性操作工作,让我们的工作效率大大提高。今天通过两个例...

33250
来自专栏CreateAMind

pytorch初体验

一部分的内容在2017年1月18日Facebook发行的PyTorch相比TensorFlow、MXNet有何优势? - 罗若天的回答 - 知乎 已有。

13310
来自专栏数说工作室

【SAS Says】基础篇:6. 开发数据(二)

如果你管着一份10000条的客户数据,有一天,老板拿着一个500人的表告诉你,这表上的500位客户的信息发生了变动,而且变动的变量很不规律,如客户102是收入发...

40830
来自专栏小樱的经验随笔

零基础学并查集算法

并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(pa...

56380
来自专栏take time, save time

你所能用到的无损压缩编码(二)

     上个月项目荷兰大佬要检查,搞的我想写的东西不断推迟,现在检查完了,我决定继续把我想写的这整个一个系列写完,上一次写的是最简单的无损编码行程编码,这一次...

37590
来自专栏华章科技

令人困惑的TensorFlow!谷歌大脑工程师帮你解决麻烦

导读:虽然对于大多数人来说 TensorFlow 的开发语言是 Python,但它并不是一个标准的 Python 库。这个神经网络框架通过构建「计算图」来运行,...

17630
来自专栏天天P图攻城狮

Android OpenGL开发实践 - GLSurfaceView对摄像头数据的再处理

文首先对GLSurfaceView相关知识进行讲解,然后介绍Android系统如何获取摄像头数据并利用GLSurfaceView渲染到屏幕上。

3.9K110
来自专栏java一日一条

Java 8:HashMap的性能提升

HashMap是一个高效通用的数据结构,它在每一个Java程序中都随处可见。先来介绍些基础知识。你可能也知道,HashMap使用key的hashCode()和e...

8720
来自专栏人工智能

如何使用tableaux进行逻辑计算

原文作者:Miguel Diaz Kusztrich

90380
来自专栏杨建荣的学习笔记

Python之Numpy初识

今天翻了下计划,要学习Numpy了,所以得调动脑细胞的积极性,看看能有什么收获。 首先得了解下什么是Numpy,从我的印象中,一般提到这个工具都会和机器学习关...

363110

扫码关注云+社区

领取腾讯云代金券