算法思想

算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中，直到全部记录插⼊完成。

步骤：引用来自菜鸟教程：https://www.runoob.com/data-structures/insertion-sort.html

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。
第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。
第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。

alt

代码：

#include<iostream>
using namespace std;
#include<vector>

//插入排序
//插入排序是从第二个元素进行排序的，每次排序时。当前元素都会和前面的元素进行对比。
void insertSort(vector<int>& v) {
	int temp;//临时存放当前元素
	int j;
	for (int i = 1; i < v.size(); i++) {
		temp = v[i];//存放当前元素
		//将当前元素和之前的元素进行对比
		//即检查前面所有已经排好序的元素是否大于当前元素值
		for (j = i - 1; j >= 0; j--) {
			if (v[j] > temp)
				v[j + 1] = v[j];//将大于temp的元素后移
			else
				break;
		}
		//可将上面的循环体改写为
		//for (j = i - 1; j >= 0 && a[j - 1] > temp; j--) v[j + 1] = v[j];
		v[j + 1] = temp;//将temp放入对应位置。注意：这里是j+1，因为再前面的循环条件中，j = j-1，不满足条件才会跳出循环
	}
}
int main() {
	vector<int> v = { 2,5,9,5,12,43,76,1,0,89};
	insertSort(v);
	for (vector<int> ::iterator it = v.begin(); it != v.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

希尔排序

算法思想：希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

见菜鸟教程：https://www.runoob.com/data-structures/shell-sort.html

插入排序和希尔排序

算法思想

希尔排序