用Python实现插入排序和选择排序

栏目: Python · 发布时间: 5年前

内容简介:这篇是我关于用Python实现50个经典算法代码的第一篇文章,主要目的是在自己手写一遍算法之后,在文章中对算法的细节进行总结来加以巩固。话不多说,让我们从最基本的排序算法开始吧如下图所示,插入排序的实现思路顾名思义,就是

这篇是我关于用 Python 实现50个经典算法代码的第一篇文章,主要目的是在自己手写一遍算法之后,在文章中对算法的细节进行总结来加以巩固。

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

插入排序

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

用Python实现插入排序和选择排序

具体实现步骤为:

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

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

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

其实现的具体代码为:

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实现插入排序和选择排序

实现代码为:

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)


以上所述就是小编给大家介绍的《用Python实现插入排序和选择排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Introduction to Computer Science Using Python

Introduction to Computer Science Using Python

Dierbach, Charles / 2012-12 / $ 133.62

Introduction to Computer Science Using Python: A Computational Problem-Solving Focus introduces students to programming and computational problem-solving via a back-to-basics, step-by-step, objects-la......一起来看看 《Introduction to Computer Science Using Python》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器