Python|用“插入”也能简单排序

引言

在排序这一个大家庭里，它的算法成员形形色色，多种多样，有“快速排序”，“归并排序”，“插入排序”等等基本排序算法。而今天，所要侧重讲解“插入”排序算法，排序，是指将无序序列中的各个元素，依照规则进行有序排列，而插入排序便是一种排序方法，它相当于是在已有的有序排列中，从前往后扫描，然后根据相应规则，放置到相应的位置当中，就一般问题，例如，已有3个元素已经是有序排列后，想要插入第4个元素时，我们便需要从第3个元素开始往前进行扫描，把已经排序的序列往后移，为新元素的插入腾出空间，如果符合插入规则，便可直接插入。

问题描述

在给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例1：

输入：[1,3,5,6],5

输出：2

示例2：

输入：[1,3,5,6],2

输出：1

示例3：

输入：[1,3,5,6],7

输出：4

示例4：

输入：[1,3,5,6],0

输出：0

算法描述

首先通过示例我们可以知道，我们要做的便是在已经排序好了的列表当中插入一个阿拉伯数字，规则便是从小到大排序，而题目要求的是返回插入位置的下标，那么我们要做的很简单，直接通过遍历已知的列表，可以通过从小到大排序，也可往后排序，在一次次遍历当中进行比较，同时我们可以设置一个标准进行count计数，例如：当从前往后比较时，当出现比插入数字小，或者相等时我们便直接输出当前数字的位置，得到结果。

结语

通过简单的示例问题解答可以了解到简单排序算法基本原理以及思考问题的思路。

主编：欧洋

稿件来源：深度学习与文旅应用实验室（DLETA）