数据结构：插入排序
1.插入排序
此排序如打扑克牌一样；每次抓牌，把扑克从前向后扒拉；找到合适的位置插入进去—所以叫插入排序；
时间复杂度：O（N^2）
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };//数据太多就不好写了
for (int i = 1; i < 10; i++) {
int n = i;
for (; n > 0; n--) {
if (arr[n] < arr[n - 1]) swap(arr[n], arr[n - 1]);
else break;
}
}
for (auto x : arr)
cout << x << endl;
return 0;
2.希尔排序
时间复杂度：O（N^1.3）
希尔排序是插入排序的优化；在完全逆序的情况下，就是将最大的数，排向最后一个数，只不过是从插入排序的一个一个比较，向后挪动；变成了一个大增量的向后挪动；减少了比较的次数；
思想：此思想属于个人思考；用于推演提出算法的人的思想历程；不一定对，但值得一看；
数组：arr[10] = { 9,8,7,6,5,4,3}; //进行升序排序；
间距：d=5；//间距d先取5，再取4，3，2，1；
d=5时，是9与4比较大小，于是乎，就得知了9与4的位置是相对的，4在9的前面；
d进行缩小，再推演：如果3与4进行比较，3在4的前面，那么3也肯定在9的前面；但是3与9不一定会通过间距直接进行比较；而是通过4与9的关系进行了间接比较；
通过不断的缩短间距d，数字之间进行相对位置的比较，从而进行正确的排序；
但是，缺陷所在就是：d的变化过大，会使两个数的相对位置无法确定，造成排序不准确；
缺陷：
由于是控制增量的变化来进行大小比较来排序；以升序为例，数值大的一端总是比数值小的一端更快的排好；若增量的变化的数值若过大，排序的结果，也不会如想象中的结果；
希尔排序是一个非常不稳定的排序——因为他是由增量控制的；
{ int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int n = sizeof(arr)/sizeof(int), gap = n;
while (gap > 1) {
gap = gap / 3 + 1; //gap=gap-1; //由于增量的控制过大，会导致结果完全不同//数据量越大，越无序；gap控制的越好的时候，希尔排序还是很能打的
//时间复杂度：大约在O（N的1.3次方的样子）；当n无限大的时候还会减小；
for (int i = 0; i < n - gap; i++) {
if (arr[i] > arr[i + gap]) {
swap(arr[i], arr[i + gap]);
}
}
}
for (auto x : arr) {
cout << x << endl;
}
return 0;}