那么接下来，我们趁热打铁，先学习最基础的数据结构：array（数组）和vector（向量），数据结构和算法是相辅相成的，二者结合彰显算法之美，所以对于常见的数据结构的掌握是很有必要的。
插入元素
现在我们来讨论一下一个数组的基础问题，如何在数组中插入一个元素。
有人可能觉得这个问题很简单，不就是将数据直接赋值么，只要我知道他的下标和他的值，我直接赋值就可以了，但是这一个简简单单的问题也要考虑多一点东西
1、下标处理：首先，你不能保证，别人是事先知道数组长度的，输入和输出的时候，很有可能会输入错误的未知，比如负数等这种情况，对于这样的，如果正/负数绝对值大于数组长度则添加在数组末尾和首位，负数绝对值小于数组长度则用index+len(list)来处理。亦或者可以利用提示输入错误再重新输入来执行。
2、None值判断及优化：若插入位置刚好是None值，则直接替换
(PS：元素的插入需要考虑扩容问题，如果原本数组已满，则需要扩容。实际上许多API底层也是用最原始的方式去实现的，只是封装起来了就成了方便调用的API，建议可以的话尝试自己的方式去实现；顺便想下，如果把它封装起来需要优化哪些地方。)
一下就是一个用python实现封装好的Array数组的插入的一个算法
class Array(object): def __init__(self,lst): self.size = len(lst) self.lst = lst def insert(self,index,e): count = 0 if index < 0: if (-index) > self.size:# 下标处理 index = 0 else: index = index + self.size if index > self.size: index = self.size # None值判断及优化 if self.lst[index] is None: self.lst[index] = e return self.lst else: for i in range(self.size-1,index,-1): if self.lst[i] is None: count += 1 if count == 0: self.resize() for i in range(self.size-1,index-1,-1): if (self.lst[i] is not None) and (self.lst[i+1] is None): self.lst[i+1] = self.lst[i] self.lst[i] = None self.lst[index] = e return self.lst def resize(self): self.size = self.size * 2 lst2 = [None for i in range(self.size)] for i in range(len(self.lst)): lst2[i] = self.lst[i] self.lst = lst2.copy() if __name__ == '__main__': my_list = [1,2,3,4,8,None] my_array = Array(my_list) my_array.insert(1,7) print(my_array.lst) # [1, 7, 2, 3, 4, 8]
插入排序
本来想到这里就结束的，但是好像太少了，那我们来看看一个有趣的排序–>插入排序
算法介绍
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
动图演示
例子
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
从小到大的插入排序整个过程如图示：
第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。
第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。
第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
就这样依次比较到最后一个元素。
代码实现
Python
def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[i] while preIndex >= 0 and arr[preIndex] > current: arr[preIndex+1] = arr[preIndex] preIndex-=1 arr[preIndex+1] = current return arr
C++
void insertSort(int array[], int len) { if (len < 2) return; int i, j, tmp; for (i = 1; i < len; i++) { tmp = array[i]; j = i - 1; for (; j >= 0 && tmp < array[j]; j--) array[j + 1] = array[j]; array[j + 1] = tmp; output(array, len); } }
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; } return arr; }
Java
public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; } }
Go
func insertionSort(arr []int) []int { for i := range arr { preIndex := i - 1 current := arr[i] for preIndex >= 0 && arr[preIndex] > current { arr[preIndex+1] = arr[preIndex] preIndex -= 1 } arr[preIndex+1] = current } return arr }
PHP
function insertionSort($arr) { $len = count($arr); for ($i = 1; $i < $len; $i++) { $preIndex = $i - 1; $current = $arr[$i]; while($preIndex >= 0 && $arr[$preIndex] > $current) { $arr[$preIndex+1] = $arr[$preIndex]; $preIndex--; } $arr[$preIndex+1] = $current; } return $arr; }
C#
public static void InsertSort(int[] array) { for(int i = 1;i < array.length;i++) { int temp = array[i]; for(int j = i - 1;j >= 0;j--) { if(array[j] > temp) { array[j + 1] = array[j]; array[j] = temp; } else break; } } }
Swift
for i in 1..<arr.endIndex { let temp = arr[i] for j in (0..<i).reversed() { if arr[j] > temp { arr.swapAt(j, j+1) } } }
每日一句
Every noble work is at first impossible.(每一个伟大的工程最初看起来都是不可能做到的！)
