python 常见的排序算法实现汇总
作者:东何 发布时间:2023-09-17 13:47:24
排序分为两类,比较类排序和非比较类排序,比较类排序通过比较来决定元素间的相对次序,其时间复杂度不能突破O(nlogn);非比较类排序可以突破基于比较排序的时间下界,缺点就是一般只能用于整型相关的数据类型,需要辅助的额外空间。
要求能够手写时间复杂度位O(nlogn)的排序算法:快速排序、归并排序、堆排序
1.冒泡排序
思想:相邻的两个数字进行比较,大的向下沉,最后一个元素是最大的。列表右边先有序。
时间复杂度$O(n^2)$,原地排序,稳定的
def bubble_sort(li:list):
for i in range(len(li)-1):
for j in range(i + 1, len(li)):
if li[i] > li[j]:
li[i], li[j] = li[j], li[i]
2.选择排序
思想:首先找到最小元素,放到排序序列的起始位置,然后再从剩余元素中继续寻找最小元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。列表左边先有序。
时间复杂度$O(n^2)$,原地排序,不稳定
def select_sort(nums: list):
for i in range(len(nums) - 1):
min_index = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[i]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
3.插入排序
思想:构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。列表左边先有序。
时间复杂度$O(n^2)$,原地排序,稳定
def insert_sort(nums: list):
for i in range(len(nums)):
current = nums[i]
pre_index = i - 1
while pre_index >= 0 and nums[pre_index] > current:
nums[pre_index + 1] = nums[pre_index]
pre_index -= 1
nums[pre_index + 1] = current
4.希尔排序
思想:插入排序的改进版,又称缩小增量排序,将待排序的列表按下标的一定增量分组,每组分别进行直接插入排序,增量逐渐减小,直到为1,排序完成
时间复杂度$O(n^{1.5})$,原地排序,不稳定
def shell_sort(nums: list):
gap = len(nums) >> 1
while gap > 0:
for i in range(gap, len(nums)):
current = nums[i]
pre_index = i - gap
while pre_index >= 0 and nums[pre_index] > current:
nums[pre_index + gap] = nums[pre_index]
pre_index -= gap
nums[pre_index + gap] = current
gap >>= 1
5.快速排序
思想:递归,列表中取出第一个元素,作为标准,把比第一个元素小的都放在左侧,把比第一个元素大的都放在右侧,递归完成时就是排序结束的时候
时间复杂度$O(nlogn)$,空间复杂度$O(logn)$,不稳定
def quick_sort(li:list):
if li == []:
return []
first = li[0]
# 推导式实现
left = quick_sort([l for l in li[1:] if l < first])
right = quick_sort([r for r in li[1:] if r >= first])
return left + [first] + right
6.归并排序
思想:分治算法,拆分成子序列,使用归并排序,将排序好的子序列合并成一个最终的排序序列。关键在于怎么合并:设定两个指针,最初位置分别为两个已经排序序列的起始位置,比较两个指针所指向的元素,选择相对小的元素放到合并空间,并将该指针移到下一位置,直到某一指针超出序列尾,将另一序列所剩下的所有元素直接复制到合并序列尾。
时间复杂度$O(nlogn)$,空间复杂度O(n),不稳定
二路归并
def merge_sort(nums: list):
if len(nums) <= 1:
return nums
mid = len(nums) >> 1
left = merge_sort(nums[:mid]) # 拆分子问题
right = merge_sort(nums[mid:])
def merge(left, right): # 如何归并
res = []
l, r = 0, 0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
res += left[l:]
res += right[r:]
return res
return merge(left, right)
7.堆排序
思想:根节点最大,大顶堆,对应升序,根节点最小,小顶堆。
构建大根堆,完全二叉树结构,初始无序
最大堆调整,进行堆排序。将堆顶元素与最后一个元素交换,此时后面有序
时间复杂度$O(nlogn)$,原地排序,稳定
def heap_sort(nums: list):
def heapify(parent_index, length, nums):
temp = nums[parent_index] # 根节点的值
chile_index = 2 * parent_index + 1 # 左节点,再加一为右节点
while chile_index < length:
if chile_index + 1 < length and nums[chile_index + 1] > nums[chile_index]:
chile_index = chile_index + 1
if temp > nums[chile_index]:
break
nums[parent_index] = nums[chile_index] # 使得根节点最大
parent_index = chile_index
chile_index = 2 * parent_index + 1
nums[parent_index] = temp
for i in range((len(nums) - 2) >> 1, -1, -1):
heapify(i, len(nums), nums) # 1.建立大根堆
for j in range(len(nums) - 1, 0, -1):
nums[j], nums[0] = nums[0], nums[j]
heapify(0, j, nums) # 2.堆排序,为升序
if __name__ == '__main__':
nums = [89, 3, 3, 2, 5, 45, 33, 67] # [2, 3, 3, 5, 33, 45, 67, 89]
heap_sort(nums)
print(nums)
来源:https://www.cnblogs.com/donghe123/p/13528332.html?utm_source=tuicool&utm_medium=referral
猜你喜欢
- 给定图像集如下,所有类别的图片均在一个文件夹内:给定与图片名相匹配的表格,声明每张图片对应的类别(共有20个类别):那么,如何根据表格中所给
- 一、使用python3做webervice接口测试的第三方库选择suds-jurko库,可以直接pip命令直接下载,也可以在pypi官网下载
- 对于想深入理解 Python 的朋友,很有必要认真看看。喜欢本文点赞支持,欢迎收藏学习。1. eval函数函数的作用:计算指定表达式的值。也
- 人在学校,身不由己。总有一些奇奇怪怪的学习任务,需要我们刷够一定的时长去完成,但这很多都是不太令人感兴趣的文字或是视频,而这些课都有共同的特
- 前言在使用mongo数据库时,简单的查询基本上可以满足大多数的业务场景,但是试想一下,如果要统计某一荐在指定的数据中出现了多少次该怎么查询呢
- java开发者在定义类中的方法时,不会关心方法的定义相对于调用语句的位置。但是python中需要注意:函数必须先定义、后调用(函数调用函数例
- SQLserver 2000中出现“指定的服务并未以已安装的服务存在" 解决方案一、将计算机名改成大写。二、将sql server
- 本文实例为大家分享了Python曲线拟合的最小二乘法,供大家参考,具体内容如下模块导入import numpy as npimport ga
- 一、使用+号添加列表元素一般情况下两个列表合并起来也是一种添加元素的方法,只要使用+号直接进行运算就可以了,下面是演示代码。name1 =
- 引子:今天在蓝点看了Yang的博客《CSS样式表中继承关系的空格与不空格》,思考了一下,本来想写《CSS样式的复合定义与复合调用及简单的模块
- OpenCV 是一个流行的开源计算机视觉库,可用于不同的编程语言,例如 Python、C++ 和 JavaScript。它提供了一套丰富的工
- python记录程序运行时间的三种方法 &nb
- 遍历字典: keys() 、values() 、items()1. xxx.keys() : 返回字典的所有的key 返回一个序列,序列中保
- 浅谈tensorflow语义分割api的使用(deeplab训练cityscapes)安装教程:cityscapes训练:遇到的坑:1. 环
- 本文实例讲述了Python使用pylab库实现画线功能的方法。分享给大家供大家参考,具体如下:pylab 提供了比较强大的画图功能,但是函数
- 近段时间由于修改一个ASP程序(有SQL注入漏洞),在网上找了很多相关的一些防范办法,都不近人意,所以我将现在网上的一些方法综合改良了一下,
- 前言本文实现一个 Python 脚本,用来批量卸载模拟器或者实体机上面的 App 以及清除 LogCat 缓存。开发 Android 的朋友
- def report_hook(count, block_size, total_size):... &n
- 流程:模拟登录→获取Html页面→正则解析所有符合条件的行→逐一将符合条件的行的所有列存入到CSVData[]临时变量中→写入到CSV文件中
- 平行坐标图,一种数据可视化的方式。以多个垂直平行的坐标轴表示多个维度,以维度上的刻度表示在该属性上对应值,相连而得的一个折线表示一个样本,以