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

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

    您可能感兴趣