插入排序

## 插入排序
![](/media/202205/20210509184956602_1653627853.gif)
插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

**基本思想：**
- 在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
- 但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

**算法描述:**
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

[wokwi_插入排序](https://wokwi.com/projects/332787272014365266)|[wokwi_插入排序](https://wokwi.com/projects/334327049557639763)
```c
// 插入排序,InsertSort(数组名,数组长度,[排序方向,默认小到大])
// 在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序.按照此法对所有元素进行插入,直到整个序列有序
void InsertSort(int array[], int size,boolean forward = true){
	// 遍历所有数,循环次数为 数组长度-1
	for (int i = 0; i < size - 1; i++){
		// 记录有序序列的最后一个元素的下标
		int end = i;
		// 存入待插入的元素
		int tmp = array[end + 1];
		while (end >= 0){
			// 定义存储比较结果的变量
			boolean compare;
			// 根据传入的第三个参数,来确定是正向排序(小到大)还是逆向排序(大到小)
			if (forward == true){
				compare = tmp < array[end];
			}else{
				compare = tmp > array[end];
			}
			// 比较待插入数是否比比较数小,小的话再往前继续比较,大的话则证明前方的都比它小,待插入应该放置在该比较数右方
			if (compare){
				// 判定为真,把当前数往后移
				array[end + 1] = array[end];
				// 序列往前移,进行新的比较
				end--;
			}else{
				// 判定为假,数值不动,结束循环
				break;
			}
		}
		array[end + 1] = tmp;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置(break跳出循环到此).
		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此).
	}
}
```