数据结构：插入排序

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;}