西拉免费代理IP

你当前的位置:西拉免费代理IP   >   新闻中心   >   如何用 Python 实现选择排序?

如何用 Python 实现选择排序?

来源: 西拉IP   作者: 张祁无   2018年12月10日 15:04

如何用 Python 实现选择排序?

排序算法是算法中最基本的算法,本文通过python实现选择排序、冒泡排序、插入排序以及各种改进方法。

本文所有的排序方法都在列表上进行操作,首先定义交换任意两项位置的函数swap。

def swap(x,i,j):
"""
交换x的i,j位置元素
"""
temp = x[i]
x[i] = x[j]
x[j] = temp

1、选择排序

排序算法的逻辑非常简单,首先搜索整个列表,找到最小项的位置,如果该位置不是列表的第1项,就交换这两个位置的元素。然后从列表的第2个元素开始,重复上述过程,直到算法达到整个过程的最后一个位置,图形解释如下

如何用 Python 实现选择排序?

代码如下

def selectionSort(x):
i = 0   while i < len(x) - 1:
minindex = i
j = i + 1
while j < len(x) :
if x[minindex] > x[j]:
minindex = j
j+= 1
if minindex != i:
swap(x,i,minindex)
i+= 1
return x

函数包括一个嵌套的循环,对于大小为n的列表,外围的循环执行n-1次,内部循环的次数从n-1递减到1,因此,选择排序在各种情况下的复杂度为平方阶,运行结果如下

如何用 Python 实现选择排序?

2、二元选择排序法(选择排序改进)

选择排序法每轮只找最小值,效率较低,可以考虑每次同时寻找最小值和最大值,并且在某一轮如果最小值与最大值相同,说明剩下的数字都相同,可以直接结束。

此外,与选择排序不同的是,需要考虑到如果第i轮里,恰好第i个数就是最大值时,先交换minindex和i之后,最大值的下标变成了minindex,这时候应该交换minindex和n-i-1,而不是maxindex和n-i-1。代码如下

def selectionSort_1(x):
i = 0   while i <= len(x) // 2:
minindex = i
maxindex = i
j = i + 1
while j < len(x) - i  :
if x[minindex] > x[j]:
minindex = j
if x[maxindex] < x[j]:
maxindex = j
j+= 1
if x[minindex] == x[maxindex]:
return x
if minindex != i:
swap(x,i,minindex)
if maxindex != len(x) - 1 - i :
if maxindex != i:
swap(x,len(x) - 1 - i,maxindex)
else:
swap(x,len(x) - 1 - i, minindex)
i+= 1
return x

3、冒泡排序

冒泡排序从列表的开头处开始,逐个比较一对数据项,如果顺序不对就交换两项位置,直到移动到列表的末尾。这个过程的效果就是将最大的项以冒泡的方式排到算法的末尾。然后算法从列表开头到倒数第二项重复这一过程,依次类推,图形解释如下。

如何用 Python 实现选择排序?

代码如下

def BubbleSort(x):
j = len(x) - 1
while j > 0:
i = 0
while i < j:
if x[i] > x[i + 1]:
swap(x,i,i+1)
i += 1
j -= 1
return x

类似选择排序,冒泡排序也是一个嵌套的循环,如果列表是已经排好序的,冒泡排序不会执行任何的交换,在最坏的情况下,为平方阶复杂度。

4、冒泡排序法改进

在最好的情况下,冒泡排序法依然会执行每个循环但不进行任何操作,可以设定一个标记判断冒泡排序法在一次内层循环中是否进行了交换,如果没有,说明算法已经使排好序的,就可以直接返回,不过这种方法只是对最好的情况进行了改进,代码如下

def BubbleSort_1(x):
j = len(x) - 1
while j > 0 :
flag = False
i = 0
while i < j:
if x[i] > x[i + 1]:
swap(x,i,i+1)
flag = True
i += 1
if not flag:
return x
j -= 1
return x

5、双向冒泡排序法

冒泡排序法存在所谓的“乌龟问题”,假设我们需要将序列按照升序排序。序列中的较小的数字又大量存在于序列的尾部,这样会让小数字在向前移动得很缓慢,因此针对这一问题,产生了双向冒泡排序法,也称鸡尾酒排序法。

双向冒泡排序法由两个方向同时进行冒泡,首先由左向右为大元素移动方向,从右向左为小元素移动方向,然后每个元素都依次执行。在第i次移动后,前i个和后i个元素都放到了正确的位置。图形解释如下

如何用 Python 实现选择排序?

代码如下

def BidirectionalBubbleSort(x):
j = 0
while j <= len(x)//2:
flag = False
for i in range(j ,len(x) - j - 1):
if x[i]>x[i+1]:
swap(x,i,i+1)
flag=True
for i in range(len(x)- 1 - j,j,-1):
if x[i]<x[i-1]:
swap(x,i,i-1)
flag=True
if not flag:
return x
j += 1
return x

实验结果如下

如何用 Python 实现选择排序?

6、插入排序法

插入排序法类似打牌时候摸扑克牌整理顺序的过程,逻辑如下:

在第i轮通过列表的时候(i从1到n-1),第i项应该插入到列表的前i个项中的正确位置;

在第i轮之后,前i个项应该是排好序的;

图形解释如下

如何用 Python 实现选择排序?

代码如下

def InsertionSort(x):
i = 1
while i < len(x):
j = i - 1
item = x[i]
while j >= 0 and item < x[j]:
x[j + 1] = x[j]
j -= 1
x[j + 1] = item
i += 1
return x

7、希尔排序(插入排序改进)

插入排序对于几乎已经排好序的数据操作时,效率很高,但平均来说,插入排序很低效,因为插入排序每次只能将数据移动一位,希尔排序是在此基础上对于插入排序的一种改进。

希尔算法的逻辑是,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序,具体步骤如下:

设定一个较大间隔gap,对所有间隔为gap的数据通过插入排序法进行排序;

执行完之后根据某种逻辑缩小gap(代码中采用除以3取整的办法),重复上述过程,直到gap = 0。

通过以上步骤,最终得到的列表是排好序的,并且可以证明,这种方法的平均的复杂度是O(nlogn)。代码如下

def HashSort(x):
gap = round(len(x)*2/3)
while gap > 0 :
print('gap =  ',gap )
i = gap
while i < len(x):
j = i - gap
item = x[i]
while j >= 0 and item < x[j]:
x[j + gap] = x[j]
j -= gap
x[j + gap] = item
i += 1
gap = round(gap/3)
return x

这里print每次循环中gap的值,可以直观看到gap的变化过程,实验如下

如何用 Python 实现选择排序?

阅读 477   

相关推荐

基于访客的网络(VBN)

定义 - 访客网络(VBN)是什么意思? 基于访客的网络(VBN)有助于临时移动设备用户访问高速互联网或基于互联网的以太网局域网(LAN)。VBN通常用于大学,办公室,会议室 . . .

2018年12月11日
80端口是什么

定义 - 端口80的含义是什么? 端口80是分配给常用因特网通信协议超文本传输​​协议(HTTP)的端口号。它是计算机从Web服务器发送和接收基于Web客户端的通信和 . . .

2018年12月10日
简单网络管理协议(SNMP)

定义 - 简单网络管理协议(SNMP)是什么意思? 简单网络管理协议(SNMP)是一组用于网络管理和监控的协议。许多典型的网络设备支持这些协议,例如路由器,集线器,网 . . .

2018年12月10日
程序员依然是这个时代,贫寒学子翻身的不二选择 程序员依然是这个时代,贫寒学子翻身的不二选择
程序员依然是这个时代,贫寒学子翻身的不二选择

作者岳京杭,湖南人、北邮硕士。曾北漂8年,后跑路杭州,通信从业多年、后转行互联网,先后经历三星电子、百度等公司,目前从事人工智能相关开发工作。本号以技术人的角度,探讨行业动态,职场见闻,转行路 . . .

2018年12月10日
公开薪资后,我会被解雇吗? 公开薪资后,我会被解雇吗?
公开薪资后,我会被解雇吗?

薪资一直是程序员们秘而不宣的热议话题,但是却鲜少有人敢于公开披露自己的薪资水平:有的人担心会在某个地方被某个人认出来,更多的人是担心因为分享他们的薪资而被解雇...... 不 . . .

2018年12月10日
Internet协议安全性(IPsec)

Internet协议安全性( IP sec)是一组为Internet协议提供安全性的协议。它可以使用加密技术来提供安全性。IPsec可用于以安全的方式设置虚拟专用网络(V . . .

2018年12月8日
网络中最令人困惑的4个概念解释 网络中最令人困惑的4个概念解释
网络中最令人困惑的4个概念解释

网络可能很复杂; 工作越大,你必须弄清楚如何拼凑起来的小拼图。然而,在最基本的层面上,许多看起来最复杂的网络概念实际上相当简单......当然,除非它们的实现。以下是其中一些关键概 . . .

2018年12月8日
什么是网络配置 什么是网络配置
什么是网络配置

网络配置是设置网络控制,流和操作以支持组织和/或网络所有者的网络通信的过程。这个广泛的术语包含网络硬件,软件和其他支持设备和组件上的多个配置和设置过程。 网络配置也称为网络设 . . .

2018年12月8日
什么是虚拟IP地址(VIPA)

虚拟 IP地址 (VIPA) 是分配给多个域名或服务器的IP地址,这些域名或服务器基于单个网络接口卡(NIC) 共享IP 地址 . . .

2018年12月8日
代理服务 代理服务
代理服务

代理服务 是由端点设备和请求服务的客户端之间的软件或专用计算机系统所起的中介角色。代理服务可以存在于同一台机器上,也可以存在于单独的服务器上。代理服务使客户端能够连接到不同的服务 . . .

2018年12月8日

新闻中心 代理分享 | 蜘蛛地图

全网最大的免费网页代理ip平台,提供大量免费http代理服务器免费ip代理地址

© 2016 - 2021. 西拉免费代理ip, All rights reserved. 鄂ICP备18017015号-4

在线客服