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

yipeiwu_com6年前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)

选择排序

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

实现代码为:

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)

相关文章

Python3从零开始搭建一个语音对话机器人的实现

Python3从零开始搭建一个语音对话机器人的实现

01-初心缘由 最近在研究语音识别方向,看了很多的语音识别的资料和文章,了解了一下语音识别的前世今生,其中包含了很多算法的演变,目前来说最流行的语音识别算法主要是依赖于深度学习的神经网络...

Django 开发环境配置过程详解

Django 开发环境配置过程详解

开发环境 开发环境为: Win 10(64位) Python 3.7.0 Django 2.1 安装Python python的安装为比较简单,首先找到Python官...

Python决策树之基于信息增益的特征选择示例

Python决策树之基于信息增益的特征选择示例

本文实例讲述了Python决策树之基于信息增益的特征选择。分享给大家供大家参考,具体如下: 基于信息增益的特征选取是一种广泛使用在决策树(decision tree)分类算法中用到的特征...

python实现的简单猜数字游戏

本文实例讲述了python实现的简单猜数字游戏。分享给大家供大家参考。具体如下: 给定一个1-99之间的数,让用户猜数字,当用户猜错时会提示用户猜的数字是过大还是过小,知道用户猜对数字为...

对Python中type打开文件的方式介绍

这几天在看《利用Python进行数据分析》,在第六章数据加载、存储、与文件格式中遇到个小问题。 在Linux访问文件是用:!cat ch06/ex1.csv 在Windows命令行中使用...