python常用排序算法的实现代码
作者:Mars.wang 发布时间:2022-08-21 08:50:00
标签:python,排序,算法,实现
这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升。
1.插入排序
插入排序默认当前 * 入的序列是有序的,新元素插入到应该插入的位置,使得新序列仍然有序。
def insertion_sort(old_list):
n=len(old_list)
k=0
for i in range(1,n):
temp=old_list[i]
j=i
while j>0 and temp<old_list[j-1]:
old_list[j]=old_list[j-1]
j=j-1
old_list[j]=temp
return old_list
2.冒泡排序
冒泡排序的原理是对序列进行遍历,遍历过程中如果发现相邻两个元素,左边的元素大于右边,则进行交换,一次遍历之后最大的元素被移动到对尾,然后进行第二次遍历,直到队列有序。
def bubble_sort(old_list):
n=len(old_list)
for i in range(n-1):
for j in range(n-1-i):
if old_list[j]>old_list[j+1]:
old_list[j],old_list[j+1]=old_list[j+1],old_list[j]
return old_list
3.快速排序
快速排序的实现方法是设置两个游标,一个从前往后,一个从后往前,如果左侧游标所指数据大于右侧,两数据进行交换,直到两个游标指向同一数据,则第一趟遍历结束。结束时游标所在数据,左侧都比其小,右侧都比其大。
接下来对游标前后的两个序列进行递归操作。
def quick_sort(list,low,high):
i=low
j=high
if i >= j:
return list
key=list[i]
while i < j:
while i < j and list[j]>=key:
j = j - 1
list[i]=list[j]
while i < j and list[i]<=key:
i = i + 1
list[j]=list[i]
list[i]=key
quick_sort(list,low,i-1)
quick_sort(list,j+1,high)
return list
4.选择排序
选择排序的原理是是先找到起始数组中最小的元素,将它交换到i=0;然后寻找剩下元素中最小的元素,将它交换到i=1的位置…… 直到找到第二大的元素,将它交换到n-2的位置。这时,整个数组的排序完成。
def select_sort(list):
length=len(list)
for i in range(length):
min_index=i
for j in range(i,length):
if list[j]<list[min_index]:
min_index=j
list[i],list[min_index]=list[min_index],list[i]
return list
5.归并排序
归并排序是对数组进行拆分再拆分,直到不能再拆分,然后分别对最小粒度的子数组进行合并,然后再合并稍微大一点的数组,直到最终合成一个最大的数组。分两个函数完成,一个负责拆分,一个负责排序合并。
def merge_sort(list):
if len(list)<=1:
return list
mid=int(len(list)/2)
left=merge_sort(list[:mid])
right=merge_sort(list[mid:])
return merge(left,right)
def merge(list1,list2):
list=[]
i,j=0,0
while i<len(list1) and j<len(list2):
if list1[i]<list2[j]:
list.append(list1[i])
i=i+1
elif list1[i]>=list2[j]:
list.append(list2[j])
j=j+1
list.extend(list1[i:])
list.extend(list2[j:])
return list
6.希尔排序
def shell_sort(nums):
step = len(nums)/2
while step > 0:
for i in range(step, len(nums)):
while i >= step and nums[i-step] > nums[i]:
nums[i], nums[i-step] = nums[i-step], nums[i]
i -= step
step = step/2
return nums
来源:https://www.cnblogs.com/wangbin2188/p/6520560.html
0
投稿
猜你喜欢
- islower()方法判断检查字符串的所有的字符(字母)是否为小写。语法以下是islower()方法的语法:str.islowe
- Hihi, 大家好~ 最近有不少人都提及了网页上该如何选择字体的问题。问题虽然小,但是却是前端开发中的基本,因为目前的网页,还是以文字信息
- 看了大神统计voc数据集标签框后,针对自己标注数据集,灵活应用 ,感谢!看代码吧~import reimport osimport xml.
- cupy我觉得可以理解为cuda for numpy,安装方式pip install cupy,假设import numpy as npim
- 数据采集XPath,XML路径语言的简称。XPath即为XML路径语言(XML Path Language),它是一种用来确定XML文档中某
- 使用threading.Event可以实现线程间相互通信,之前的Python:使用threading模块实现多线程编程七[使用Conditi
- 一般而言下面的就可以完成需求了。def convertToDic(data): jsonDic=json.loads(data) retur
- 一、前言Celery是一个基于python开发的分布式任务队列,而做python WEB开发最为流行的框架莫属Django,但是Django
- python有时候需要清除字符串前后空格,而字符本身的空格不需要清除掉,那就不能用正则re.sub来实现。这时用到strip()函数用法:s
- 本文实例讲述了Python编程对列表中字典元素进行排序的方法。分享给大家供大家参考,具体如下:内容目录:1. 问题起源2. 对列表中的字典元
- Log包Go语言提供的默认日志包:https://golang.org/pkg/log/基本用法log包定义了Logger类型,该类型提供了
- 文章主要讲术了一些SQL Server新的Bug,帮您认识这些被忽略的SQL Server注入技巧。1.关于Openrowset和Opend
- 关于JavaSctipt的兼容性,最懒的办法就是用jQuery的工具函数。尽量不要用那些什么ECMAScript之类的函数,因为很多浏览器都
- 接口压力测试500次,查看响应时间import jsonimport requestsimport logginglogging.basic
- 前言我们在工作中的时候,会有这种需求:用户上传一个格式固定excel表格到网站上,然后程序负债解析内容并进行处理。我最近在工作中就遇到了,所
- 1、建立socket建立socket对象需要搞清通信类型和协议家族。通信类型指明了用什么协议来传输数据。协议的例子包括IPv4、IPv6、I
- request请求头信息的键会加上HTTP_转换成大写存到request.META中因此你只需要content_range = reques
- 1 引言如果你想对图像进行校准,那么透视变换是非常有效的变换手段。透视变换的定义为将图像投影到一个新的视平面,通常也被称之为投影映射。2 公
- 概念json是一种通用的数据类型一般情况下接口返回的数据类型都是json长得像字典,形式也是k-v{ }其实json是字符串字符串不能用ke
- 如下所示:#先下载psutil库:pip install psutilimport psutilimport os,datetime,tim