Python技术栈

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 345|回复: 10

[学习资料] 排序算法的python实现

[复制链接]

12

主题

15

帖子

70

积分

注册会员

Rank: 2

积分
70
发表于 2020-1-8 14:44:48 | 显示全部楼层 |阅读模式
本文所有的排序方法都在列表上进行操作,首先定义交换任意两项位置的函数swap
[Python] 纯文本查看 复制代码
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,因此,选择排序在各种情况下的复杂度为平方阶,运行结果如下


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

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

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

[Python] 纯文本查看 复制代码
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

阅读原文看其他排序内容:https://developer.aliyun.com/article/673948?utm_content=g_1000098496


Python 总 群
回复

使用道具 举报

0

主题

11

帖子

32

积分

新手上路

Rank: 1

积分
32
发表于 2020-1-8 14:46:26 | 显示全部楼层
求志同道合者一块学习python。只求交流。 互相督促。
Python 总 群
回复

使用道具 举报

0

主题

6

帖子

22

积分

新手上路

Rank: 1

积分
22
发表于 2020-1-8 16:09:41 | 显示全部楼层
好帖必须得顶起
Python 总 群
回复

使用道具 举报

0

主题

7

帖子

24

积分

新手上路

Rank: 1

积分
24
发表于 2020-1-8 16:14:16 | 显示全部楼层
好帖必须得顶起
Python 总 群
回复

使用道具 举报

0

主题

4

帖子

18

积分

新手上路

Rank: 1

积分
18
发表于 2020-1-8 16:34:30 | 显示全部楼层
前排,哇咔咔
Python 总 群
回复

使用道具 举报

0

主题

8

帖子

26

积分

新手上路

Rank: 1

积分
26
发表于 2020-1-8 17:19:38 | 显示全部楼层
Python与Java学习哪种语言好?
Python 总 群
回复

使用道具 举报

0

主题

7

帖子

24

积分

新手上路

Rank: 1

积分
24
发表于 2020-1-8 17:39:17 | 显示全部楼层
回个帖子,下班咯~
Python 总 群
回复

使用道具 举报

0

主题

9

帖子

28

积分

新手上路

Rank: 1

积分
28
发表于 2020-1-8 18:11:47 | 显示全部楼层
你们程序的python需求工作多吗?好找工作吗?
Python 总 群
回复

使用道具 举报

0

主题

6

帖子

22

积分

新手上路

Rank: 1

积分
22
发表于 2020-1-8 18:47:51 | 显示全部楼层
请给我推荐一款专为新手用的Python开发工具,谢谢!
Python 总 群
回复

使用道具 举报

0

主题

6

帖子

22

积分

新手上路

Rank: 1

积分
22
发表于 2020-1-8 19:29:01 | 显示全部楼层
python新人求脸熟...
Python 总 群
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


QQ|Archiver|手机版|小黑屋|Python.BBS ( 鲁ICP备18046958号 )

GMT+8, 2020-1-25 23:42 , Processed in 0.218753 second(s), 34 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表