【21天学习经典算法】插入排序（附Python完整代码）

博主一头小山猪目前已开放文章 一文学懂经典算法系列之：顺序查找（附讲解视频） 一文学懂经典算法系列之：直接插入排序（附讲解视频）

活动地址：CSDN21天学习挑战赛

插入排序的定义 输入：一组个数为 n n n的序列 ⟨ a 1 , a 2 , ⋯   , a n ⟩ \left\langle a_{1}, a_{2}, \cdots, a_{n}\right\rangle ⟨a1​,a2​,⋯,an​⟩。 输出：对输入序列的一个排列 ⟨ a 1 ′ , a 2 ′ , ⋯   , a n ′ ⟩ \left\langle a_{1}^{\prime}, a_{2}^{\prime}, \cdots, a_{n}^{\prime}\right\rangle ⟨a1′​,a2′​,⋯,an′​⟩，其中满足 a 1 ′ ⩽ a 2 ′ ⩽ ⋯ ⩽ a n ′ a_{1}^{\prime} \leqslant a_{2}^{\prime} \leqslant \cdots \leqslant a_{n}^{\prime} a1′​⩽a2′​⩽⋯⩽an′​。 排序的数也被称为关键词，虽然在概念上我们在对一个序列进行排序，但是输入是以 n n n个元素的数组的形式出现的，总而言之，也就是对一组部分无序或部分有序的数组进行排列。 插入排序的工作方式 插入排序的工作方式就像排序一手扑克牌，在开始时，我们的左手为空并且桌子上的牌面朝下，然后我们每次从桌子上拿走一张牌井将它插入手中正确的位置。为了找到一张牌的正确位置，我们从右到左（或从右至左）将它与已在手中的每张牌进行比较， 如图所示，开始时这些牌是桌子上牌堆中牌面朝下的顶部的牌，但拿在手上的牌总是排序好的。 伪代码 INSERTION ( A ) : (A): (A):

伪代码解析 对于插入排序，本文将其伪代码过程命名为INSERTION，其中的参数是一个数组 A [ 1... n ] A[1...n] A[1...n]，包含长度为 n n n的要排序的一个序列。在Python代码中， A A A中元素的数目 n n n l e n ( A ) len(A) len(A)来表示。该算法原址排序输人的数:算法在数组 A A A中重排这些数，在任何时候，最多只有其中的常数个数字存储在数组外面。在过程INSERTION-SORT结束时，输出数组 A A A包含排序好的输出序列。

对于插入排序的理解 插入排序也可以这么理解，首先我们有一组部分无序或部分有序的数组，称为数组 A A A，之后我们生成一个空数组，称为数组 B B B。我们对数组 A A A进行从左至右地取出数组内的内容放入数组 B B B中，在放入的过程当中，我们需要做一个动作，就是比较大小，比较完之后，将 “小” 的数字放在 “大” 的数字之前即可。

代码实现两种排序方式，第一种方式是采用增加一个空数组，该数组存储用户对于该数组由小到大或由大到小的排序，第一种排序方式是为了验证插入排序的正确性。第二种方式就是文中提到的插入排序，通过比较数组中数字间的大小，最终形成一组排序后的数组。

首先设一个数组 A A A

以上就是个人在插入排序中的理解，如果错误之处，还望指正。