关于Python八大排序实现方法(冒泡排序、快速排序等)
作者:Python 发布时间:2022-03-23 09:08:38
标签:python,冒泡,排序,实现
1.基数排序
基数排序的基本思想是先将数字按照个位数上数字的大小进行排序,排序之后再将已经排过序的数字再按照十位数上数字的大小进行排序,依次推类
# 统计这个列表中数字最大的数字有几位
def radix_sort_nums(nums):
max = nums[0]
for i in nums:
if max < i:
max = i
times = 0
while max > 0:
max = int(max/10)
times += 1
return times
# 每个数字各个位置的数字大小,比如(123,1)则是3,(123,2)则是2
def get_num(num,n):
return (int(num/(10**(n-1)))) % 10
# 主程序
def radix_sort(nums):
count = 10*[None]# 定义的数组,用于存放当前位数的元素个数
bucket = len(nums)*[None]# 用于暂时存放排序结果
# 分别从个位/十位/百位开始循环
for pos in range(1, radix_sort_nums(nums)+1):
# 每次排序完都要清空各个位数存放的数据统计
for i in range(10):
count[i] = 0
for i in range(len(nums)):
# 获得0到9每个位数的个数
j = get_num(nums[i], pos)
count[j] = count[j]+1
# 获得相对应位数的边界值
for i in range(1, 10):
count[i] = count[i] + count[i-1]
for i in range(len(nums)-1, -1, -1):
# 求出相应位数的数字
j = get_num(nums[i], pos)
#将元素按相应位数的上数字的大小排序
bucket[count[j]-1] = nums[i]
#让相应位数上数字相等的元素不会放在同一位置而被替代
count[j] = count[j]-1
# 将暂时存储在bucket的元素数据返回到nums中
for i in range(0, len(nums)):
nums[i] = bucket[i]
return nums
print(radix_sort([45, 32, 8, 33, 12, 22, 19, 97]))
2.归并排序
归并排序其实是将原数列分为很多个小数列将其排序,在小数列排序完之后,再将各个小数列进行排序,最后得到一个全部有序的数列
# 归并排序
# 这个函数主要目的是为了实现合并并排序
def mergearray(nums, first, mid, last, temp):
# i, j分别是第一个组数的第一个位置,第二组数的第一个位置
i, j, k = first, mid+1, 0
# 当俩边数组都存在数的时候,依次比较对应位置的大小
while i <= mid and j <= last:
if nums[i] <= nums[j]:
temp[k] = nums[i]
i = i+1
k = k+1
else:
temp[k] = nums[j]
j = j+1
k = k+1
# 第一组数还有多的数的情况
while i <= mid:
temp[k] = nums[i]
i = i+1
k = k+1
# 第二组数还有多的情况
while (j <= last):
temp[k] = nums[j]
j = j+1
k = k+1
# 将排列过的数组赋予nums(开始的时候只是部分有序,随着递归最后变成全部有序)
for i in range(k):
nums[first+i] = temp[i]
# 分组,利用递归
def merge_sort(nums,first,last,temp):
if first < last:
mid = int((first + last) / 2)
# 分出第一组数
merge_sort(nums, first, mid, temp)
# 分出第二组数
merge_sort(nums, mid+1, last, temp)
# 合并并排序
mergearray(nums, first, mid, last, temp)
def merge_sort_array(nums):
# 创建一个和想要排序数列相同数量的空列表
temp = len(nums)*[None]
# 利用递归进行排序
merge_sort(nums, 0, len(nums)-1, temp)
print(merge_sort_array([45, 32, 8, 33, 12, 22, 19, 97]))
3.堆排序
堆排序利用了二叉树的结构,使子节点的值一直小于根节点
def big_endian(arr, start, end):
root = start
child = root * 2 + 1 # 左孩子
while child <= end:
# 孩子比最后一个节点还大,也就意味着最后一个叶子节点了,就得跳出去一次循环,已经调整完毕
if child + 1 <= end and arr[child] < arr[child + 1]:
# 为了始终让其跟子元素的较大值比较,如果右边大就左换右,左边大的话就默认
child += 1
if arr[root] < arr[child]:
# 父节点小于子节点直接交换位置,同时坐标也得换,这样下次循环可以准确判断:是否为最底层,
# 是不是调整完毕
arr[root], arr[child] = arr[child], arr[root]
root = child
child = root * 2 + 1
else:
break
def heap_sort(nums): # 无序区大根堆排序
first = len(nums) // 2 - 1
for start in range(first, -1, -1):
# 从下到上,从左到右对每个节点进行调整,循环得到非叶子节点
big_endian(nums, start, len(nums) - 1) # 去调整所有的节点
for end in range(len(nums) - 1, 0, -1):
nums[0], nums[end] = nums[end], nums[0] # 顶部尾部互换位置
big_endian(nums, 0, end - 1) # 重新调整子节点的顺序,从顶开始调整
return nums
print(heap_sort([3, 1, 4, 9, 6, 7, 5, 8, 2, 10]))
4.简单选择排序
简单选择排序的方法则是将所选值与剩下值中比他小的值进行比较
比如选取第一个值,往后找到比他小的值就与其对调,对调后的值再接下去进行比较,直至找到最小的值,随后再第二个值……直至循环到倒数第二个值.
def select_sort(nums):
# 遍历所有的值
for i in range(len(nums)):
# 当前位置初始值
min = nums[i]
# 与比他后面的值进行比较,小则互换
for j in range(i+1, len(nums)):
if nums[j] < min:
nums[j], min = min, nums[j]
# 将值返回数列
nums[i] = min
return nums
print(select_sort([45, 32, 8, 33, 12, 22, 19, 97]))
5.直接插入排序
首先遍历所有元素,随后从第一个数开始将数列从后往前遍历,如果后面的数小于前面的数,则互换位置,依次推类,直到遍历完成
# 直接插入排序
def insert_sort(nums):
for i in range(len(nums)-1):
for j in range(i, -1, -1):
if nums[j] > nums[j+1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(insert_sort([45, 32, 8, 33, 12, 22, 19, 97]))
6.希尔排序
希尔排序其实就相当于对直接插入排序的升级版,每次都选取一半的长度,随后利用直接插入法进行排序,从而更快的获得结果
def insert_shell(nums):
# 初始化l值,此处利用序列长度的一半为其赋值
l = int(len(nums)/2)
# 第一层循环:依次改变l值对列表进行分组
while l >= 1:
# 下面:利用直接插入排序的思想对分组数据进行排序
for i in range(len(nums) - 1):
for j in range(i, -1, -1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# while循环条件折半
l = int(l/2)
return nums
7.快速排序
快速排序首先得选取一个基准值,这个代码用第一个数作为基准值,将比基准值小的值放到左边,比基准值大的值放到右边,随后再将左边后右边按照上述方法进行排序,直到完全正确为止
# 实现快速排序方法的函数
def quick_sort_num(nums,start,end):
if start < end:
# 定义基准值为第一个数
i, j, pivot = start, end, nums[start]
while i < j:
# 将基准数右边的数中比基准数小的放到左边
while i < j and nums[j] >= pivot:
j = j-1
if i < j:
nums[i] = nums[j]
i = i+1
# 将基准数左边的数中比基准数大的数放到右边
while i < j and nums[i] < pivot:
i = i+1
if i < j:
nums[j] = nums[i]
j = j-1
nums[i] = pivot
# 分别将基准数左边的数列和右边的数列进行递归
quick_sort_num(nums, start, i-1)
quick_sort_num(nums, i+1, end)
return nums
# 快速排序主体函数
def quick_sort(nums):
start = 0
end = len(nums)-1
nums = quick_sort_num(nums, start, end)
return nums
print(quick_sort([45, 32, 8, 33, 12, 22, 19, 97]))
8.冒泡排序
冒泡排序是最简单的排序,依次将左右俩个元素进行比较,每次比较完最后的一个数必定是最大的,依次推类,直到全部元素都比较玩
def bubble_sort(nums):
# 交换的轮数
for i in range(len(nums) - 1):
# 每一轮交换
for j in range(len(nums) - i - 1):
# 比较值,并根据大小进行互换
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
9.时间测试
我们先创建一个列表,列表中有10000条数据,随后用相同的数据进行测试
import random
lis = []
for i in range(10000):
i = random.randint(0,500)
lis.append(i)
print(lis)
创出来的数据就不进行展示了。。
随后我们进行测试:
冒泡排序法:11.535502672195435
直接插入排序法:12.057243585586548
希尔排序法:86.3020749092102(大概是我的方法不大好吧,我差点以为他排不出来了)
基数排序法:0.051932334899902344(老大哥就是牛皮)
归并排序法:0.08577108383178711(233)
快速排序:0.04795527458190918
堆排序:0.09175491333007812
根据自己的测试,基数排序,归并排序,快速排序,和堆排序速度很快,感觉随着代码量的增长时间增长很慢,其余的几个则不尽如人意了
来源:https://blog.csdn.net/sinat_38682860/article/details/128882135
0
投稿
猜你喜欢
- 写在前面 最近和几个小伙伴们在写字节跳动第五届青训营后端组的大作业。虽然昨天已经提交了项目,但有很多地方值得总结一下,比如这一篇,
- 相对或者绝对import 更多的复杂部分已经从python2.5以来实现:导入一个模块可以指定使用绝对或者包相对的导入。这个计划将移动到使绝
- 本文实例讲述了Python实现查找系统盘中需要找的字符。分享给大家供大家参考。具体如下:'''Created on
- 每个进行过较大型的ASP-Web应用程序设计的开发人员大概都有如下的经历:ASP代码与页面HTML混淆难分,业务逻辑与显示方式绞合,使得代码
- 在这里我想有必要再较系统说一下ADO的各种对象的方法、属性。毕竟ADO不仅应用在ASP中,VB,VC都可以用到。在这十天中我想主要提到的对象
- 目的现有两幅栅格图像,一个是某地区道路栅格图,一个是某地区土地利用类型图,需要将道路叠加到土地利用类型图中,即叠加后,重合的像元值以道路图为
- 当来自应用程序的第一个连接控制锁而第二个连接需要相冲突的锁类型时,将发生阻塞。其结果是强制第二个连接等待,而在第一个连接上阻塞。不管是来自同
- 利用线程生成缩略图;读取当前路径下的png文件,在当前路径下生成6464,128128和32*32的缩略图。""&quo
- 本文实例为大家分享了python SMTP发送带附件电子邮件的具体代码,供大家参考,具体内容如下可采用email模块发送电子邮件附件。发送一
- 情况一:坐标上的内容是文字时如上图这样一个横向的柱状图,y坐标轴的内容太长后会导致显示不全。因为数据是由后端传过来的,有些会很长有些会比较短
- 本文实例讲述了python同时给两个收件人发送邮件的方法。分享给大家供大家参考。具体分析如下:该范例通过python内置的smtplib包发
- 引用PyMongo>>> import pymongo创建连接Connection>>> import
- 一、VScode下载官网Download Visual Studio Code - Mac, Linux, Windows点击64 bit会
- 最近做了一个微信小程序的项目,关于后端给我传递日期的时候,我拿到的是一串数字如:createDate: 1552117531000 ,这是一
- up.htm'::::::: 此程序属扬子原创 ::::::::::::::::::':::::: 在sql2000,200
- 本文实例讲述了Python求两个文本文件以行为单位的交集、并集与差集的方法。分享给大家供大家参考。具体实现方法如下:s1 = set(ope
- 机器学习之随机森林,供大家参考,具体内容如下1、Bootstraping(自助法)  
- 如下所示:import urllib.requestimport urllib.parseurl = 'https://weibo.
- 关于oracle 优化的内容很多,概念庞杂,不过可以总结出一个大纲性的东西作为需要考虑的方向,然后再逐步细化。oracle优化按重要性需要考
- 一、函数的变量作用域和可见性1.全局变量在main函数执行之前初始化,全局可见2.局部变量在函数内部或者if、for等语句块有效,使用之后外