简介

英文名：Straight Insertion Sort
也是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表

步骤

以下用数组2,5,8,3,6,9,1,4,7为例
从小到大排序

1.先看第一个数，将数组划分为有序和无序部分

• 首先看第一个数2，一个数必然有序，所以将2划分有序，后面都是无序
  

2.无序部分的首个插入到有序部分

• 取出无序部分的首个，在有序部分从后向前比较，插入到合适的位置
  
  

3.重复第2步直到无序部分全部插入有序

• 8也是一次比较就可以插入
  
  

• 3就需要多次比较，注意是多次比较，直接插入，不是比较一次插入一次（与冒泡不同）
  

后面步骤也很简单，不再给出

代码

• 从以上过程可得，这个算法是遍历一次所有数，分别插入，但第一个数一定有序，不用排，因此n个数需要n-1次遍历
• 即i直接从1开始
• 每一次插入的比较都是从前一个数开始，所以我们可以直接将第二个循环的参数j设为i-1
  
• 每一次插入我们首先拿出要插入的数
  
• 然后比较，如果大于取出数，就将这个数后移，j-1
• 
  - 接着比较
  
• 此时再次比较，出现小于3的数，所以跳出循环，3就可以插入数组了，下标是j+1

• 另一种跳出循环的方式就是排到最前面仍然没有出现比取出数小的数，此时直接跳出循环，以1为例

- 下一步按照规律2后移，j-1,此时j=-1,也要跳出循环，1放到下标j+1的位置，也就是第一个，和上一种一致

• 综上所述，我们需要限定条件j>=0和temp<a[j],最后a[j+1]=temp

• 优化：当要插入数已经大于前一个数时，不用取出再放入

#include<bits/stdc++.h>

using namespace std;

void InsertSort(int a[],int l)
{
    int temp;
    int j;
    for(int i=1;i<l;i++)
    {
        if(a[i]<a[i-1])
        {
            temp=a[i];
            for(j=i-1;j>=0&&temp<a[j];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;

        }
        for(int k=0;k<l;k++)
            cout<<a[k]<<" ";
        cout<<endl;

    }
}


int main()
{
    int a[10]={2,5,8,3,6,9,1,4,7};
    int b[10]={1,2,3,4,5,6,7,8,9};
    int len=9;
    InsertSort(a,len);
    return 0;
}

特性

1.时间复杂度

最好情况就是全部有序，此时只需遍历一次，最好的时间复杂度为$O(n)$
最坏情况全部反序，内层每次遍历已排序部分，最坏时间复杂度为$O(n^2)$

综上，因此直接插入排序的平均时间复杂度为$O(n^2)$

2.空间复杂度

辅助空间是常量
平均的空间复杂度为：$O(1)$

3.算法稳定性

相同元素的前后顺序是否改变

插入到比它大的数前面，所以直接插入排序是稳定的

小测试

• 在上面代码中，打印的数组是这样的
  

• 你能否改变代码，使有序数组在后面，即从后向前遍历？
  

新算法，老套路，要不要下次玩个新花样？(≖ᴗ≖)✧