您的位置：首页 > 脚本大全 > > 正文

python排序的三种方法（Python实现插入排序和选择排序的方法）

更多时间：2021-10-03 01:40:08 类别：脚本大全浏览量：2648

python排序的三种方法

Python实现插入排序和选择排序的方法

话不多说，让我们从最基本的排序算法开始吧

插入排序

如下图所示，插入排序的实现思路顾名思义，就是不断地在一个已经是有序的数组中，寻找合适位置并插入新元素。

python排序的三种方法（Python实现插入排序和选择排序的方法）

具体实现步骤为：

首先我们把整个数组拆分为有序区间和未排序区间，有序区间在插入排序一开始只有一个元素，就是数组的第一个元素。

接在有序区间之后的一个元素就是准备插入的元素，在图中就是标为绿色的元素，在有序区间内寻找位置并插入。

其寻找逻辑为：从后往前依次进行比较，如果待插入元素大于当前元素，则将待插入元素插入到当前元素的后一位，如果待插入元素小于当前元素，则将当前元素后移一位。不断重复该过程直至到数组的最后一位

其实现的具体代码为：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17 def insertion_sort(a):

length = len(a)

if length <=1:

return

for i in range(1,length):

j = i-1

value = a[i]

while j >=0:

if a[j]<value:

a[j+1] = value

break

else:

a[j+1] = a[j]

if j == 0:

a[j] = value

j -=1

print(a)

return a时间复杂计算为：我们需要将整个数组遍历一遍，所以这一部分为o(n)，在每一次遍历中都要执行一次插入操作，其时间复杂度为o(n)，所以总时间复杂度为o(n2)

选择排序

选择排序跟插入排序算法类似，都是将数组分为有序区间和未排序区间，区别在于插入排序是将一个新元素插入到有序区间内，而选择排序则是在未排序区间中找到最小元素，并交换到有序区间之后。

python排序的三种方法（Python实现插入排序和选择排序的方法）

实现代码为：

1

2

3

4

5

6

7

8

9

10

11

12

13

14 def selection_sort(a):

length = len(a)

if length <=1:

return

for i in range(0,length-1):

min_value = a[i]

min_index = i

j = i+1

while j<length:

if a[j] < min_value:

min_value = a[j]

min_index = j

j += 1

a[i],a[min_index] = a[min_index],a[i]

return a时间复杂度计算：数组长度为n，一共需要寻找n次最小值，每次寻找最小值都要遍历未排序区间一次，其时间复杂度为o(n)，乘以n次为o(n2)

原文链接：https://segmentfault.com/a/1190000019151804

标签：Python 选择排序插入排序

上一篇：dedecms标签怎么调用（织梦DEDECMS获取当前页面的顶级栏目名称及链接教程）

下一篇：微信小程序计数器代码（微信小程序实现计算器案例）

您可能感兴趣

python排序的三种方法（Python实现插入排序和选择排序的方法）

python排序的三种方法

热门推荐

排行榜