选择排序、插入排序、冒泡排序python实现

选择排序、插入排序、冒泡排序python实现

选择排序的时间复杂度为O(n^2),是不稳定的排序

冒泡排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),平均情况下为O(n^2),是稳定的排序

插入排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),,平均情况下为O(n^2),是稳定的排序

1.选择排序

def selection(lista):
	leng=len(lista);
	for i in range(0,leng):
		index=i;
		min=lista[i];
		for j in range(i,leng):
			if lista[j]<min:
				index=j;
				min=lista[index];
		tmp=lista[i];
		lista[i]=lista[index];
		lista[index]=tmp;
	return lista;


2.插入排序

def insertion(lista):

	leng=len(lista);
	for i in range(1,leng):
		tmp=lista[i];
		j=i;
		while(j>0 and lista[j-1]>tmp):
			lista[j]=lista[j-1];
			j=j-1;
		lista[j]=tmp;
	return lista;

3.冒泡排序

def bubble(lista):
	leng=len(lista);
	for i in range(0,leng):
		for j in range(1,leng-i):
			if lista[j-1]>lista[j]:
				lista[j-1],lista[j]=lista[j],lista[j-1];
	return lista;

4.冒泡排序的改进

假设在某趟排序后数组已经有序,则排序完毕。

def bubble2(lista):
	leng=len(lista);
	flag=True;
	while(flag):
		flag=False;
		for i in range(0,leng):
			for j in range(1,leng-i):
				if lista[j-1]>lista[j]:
					lista[j-1],lista[j]=lista[j],lista[j-1];
					flag=True;
	return lista;

測试排序的代码:

lista=[5,3,1,4,7,9,8,2,6];
selection(lista);      #选择排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
insertion(lista);      #插入排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
bubble(lista);        #冒泡排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
bubble2(lista);        #冒泡排序改进
print lista

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119010.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux查看MySQL版本的四种方法

    Linux查看MySQL版本的四种方法1在终端下执行mysql-V2在help中查找mysql–help|grepDistrib3在mysql里查看selectversion()4在mysql里查看status欢迎补充~转自:https://www.linuxidc.com/Linux/2016-10/136075.htm…

    2022年10月27日
  • python解析json文件

    python解析json文件认识json数据json有两种数据结构:对象和数组。对象:用大括号表示,由键值对组成,每个键值对用逗号隔开。其中key必须为字符串且是双引号,value可以是多种数据类型。数组:用中括号表示,每个元素之间用逗号隔开。json中的字符串都要用双括号表示。json数据可以嵌套表示出结构更加复杂的数据。json格式与python格式的对应Python JSONd…

  • vector二维数组初始化赋值_vector实现二维数组的赋值

    vector二维数组初始化赋值_vector实现二维数组的赋值一。二维vector初始化1.采用构造函数vector&lt;vector&lt;int&gt;&gt;vec(10,vector&lt;int&gt;(8));//10行8列,全部初始化为零2.添加元素(每次添加一行)inta[]={1,2,3,4};vector&lt;int&gt;ivec(a,a+4);//数组初始化vector,见最下面(…

  • java md5加密源码_javaMD5加密源码

    java md5加密源码_javaMD5加密源码packageutil;importjava.security.MessageDigest;importjava.security.NoSuchAlgorithmException;publicclassMD5Tool{/***该方法将指定的字符串用MD5算法加密后返回。*@params*@return*/publicstaticStringgetMD5Encoding(…

  • Spring Cloud微服务实战

    Spring Cloud微服务实战

  • 语义分割如何做标注_语义分割转实例分割

    语义分割如何做标注_语义分割转实例分割在进行Segmentation训练之前需要准备训练集和验证集,本文将要来介绍如何使用LabelMe进行标记。LabelMe是个可以绘制多边形、矩形、圆形、直线、点的一套标记工具,可用于分类、目标检测、语义分割、实例分割任务上的数据标注。1.label安装与数据标注首先安装LabelMe,我使用Anaconda进行安装。打开AnacondaPrompt执行以下指令:pipinstalllabelme接着输入labelme会出现以下UI介面,点选OpenDir选择要标记的图片资料

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号