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

shiina 发布于2019-07-31 10:24 / 1056人阅读

摘要：具体实现步骤为首先我们把整个数组拆分为有序区间和未排序区间，有序区间在插入排序一开始只有一个元素，就是数组的第一个元素。

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

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

插入排序

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

具体实现步骤为：

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

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

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

其实现的具体代码为：

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]
时间复杂计算为：我们需要将整个数组遍历一遍，所以这一部分为O(n)，在每一次遍历中都要执行一次插入操作，其时间复杂度为O(n)，所以总时间复杂度为O(n2)
选择排序
选择排序跟插入排序算法类似，都是将数组分为有序区间和未排序区间，区别在于插入排序是将一个新元素插入到有序区间内，而选择排序则是在未排序区间中找到最小元素，并交换到有序区间之后。

实现代码为：
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
时间复杂度计算：数组长度为n，一共需要寻找n次最小值，每次寻找最小值都要遍历未排序区间一次，其时间复杂度为O(n)，乘以n次为O(n2)

GPU云服务器云服务器用php实现插入排序实现插入排序选择排序python 堆排序用python

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43779.html

【算法日积月累】1-选择排序

摘要：选择排序算法实现实现选择排序，记录最小元素的索引，最后才交换位置说明交换两个数组中的元素，在中有更简单的写法，这是的语法糖，其它语言中是没有的。和语言中比较器的实现前面我们说到了，我们为了突出排序算法的思想，将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 评论0 收藏0
Github标星2w+，热榜第一，如何用Python实现所有算法

摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...

zxhaaa 2019-07-31 10:23 评论0 收藏0
基本排序算法的Python实现

摘要：本篇主要实现九八大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序计数排序。希尔排序是非稳定排序算法。归并排序算法依赖归并操作。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。本篇主要实现九(八）大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序,计数排序。希望大家回顾知识的时候也能从我的这...

zhangqh 2019-07-25 10:42 评论0 收藏0
python-八大算法

摘要：排序算法总结排序算法平均时间复杂度冒泡排序选择排序插入排序希尔排序快速排序归并排序堆排序基数排序一冒泡排序基本思想两个数比较大小，较大的数下沉，较小的数冒起来。排序算法总结排序算法平均时间复杂度冒泡排序O(n2) 选择排序O(n2) 插入排序O(n2) 希尔排序O(n1.5) 快速排序O(N*logN) 归并排序O(N*logN) 堆排序O(N*logN) 基数排序O(d(n+...

aboutU 2019-07-30 16:20 评论0 收藏0
前端面试必备——十大经典排序算法

摘要：冒泡排序冒泡排序也是一种简单直观的排序算法。但希尔排序是非稳定排序算法。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。冒泡排序冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就...

RebeccaZhong 2019-08-20 18:24 评论0 收藏0