【排序算法-4】直接插入排序法

一. 基本思想：

插入排序法的基本思想就是是逐一将数组中的元素与已排好序的元素进行比较，再将该数组元素插入到合适的位置；
其实就是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

二. 例子

下面，用数组 6，1，9，5，2 的由小到大排序过程，来说明插入排序法的思想。

1. 第1号元素1与它前面的第0号元素6比较，1号元素的值小于0号元素的值，两者做交换，结果为：
   1，6，9，5，2
2. 第2号元素9与它前面的第1号元素6比较，2号的值大于1号的值，不做交换，结果为：
   1，6，9，5，2
3. 第3号元素5与它前面的元素1，6，9比较，3号元素的值介于1，6之间，放在其中间， 结果为：
   1，5，6，9，2
4. 第4号元素2与它前面的元素1，5，6，9比较，4号元素的值介于1，5之间，放在其中间，结果为：
   1，2，5，6，9

完成排序。

三. 分析：

名称	时间复杂度/最好情况	时间复杂度/最坏情况	时间复杂度/平均情况	空间复杂度	稳定性
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

时间复杂度

1. 最好情况
   当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度
2. 最坏情况
   当输入数组为倒序时，复杂度为O(n^2)
3. 平均情况
   最坏及平均情况都需要比较（n-1）+(n-2)+(n-3)+ … +3+2+1=n(n-1)/2次，其时间复杂度为O(n2)。

空间复杂度

只需要一个额外的空间，所以空间复杂度为最佳。

算法稳定性

假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

使用事项

1. 直接插入排序比较适合用于数据量较少的情况。
2. 直接插入排序适用于大部分数据已经过排序数组，此排序法会造成数据的大量移动，建议在链表结构上使用。

四. 代码实现

（1）c++代码实现

#include <iostream>
using namespace std;

void insertSort(int* array, int length);
void show(int* array, int length);

int main() {
    int array[] = {6, 1, 9, 5, 2};
    int length = sizeof(array) / sizeof(array[0]);
    insertSort(array, length);
    show(array, length);
    return 0;
}

void insertSort(int* array, int length)
{
    //从第2个元素开始
    int j;
    for (int i = 1; i < length; i++)
    {
        //后面的元素小于前面的元素
        if (array[i] < array[i-1])
        {
            int moveTemp = array[i];
            for (j = i - 1; j >= 0 && array[j] > moveTemp; j--)
            {
                array[j+1] = array[j];
            }
            array[j+1] = moveTemp;
        }
        cout<<"第"<<i<<"轮排序结果为："<<endl;
        for (int k = 0; k < length; k++) {
            cout<<array[k]<<" ";
        }
        cout<<endl; 
    }
}

void show(int* array, int length)
{
    cout<<"最终排序结果为："<<endl;
    for (int i = 0; i < length; i++) {
        cout<<array[i];
    }
    cout<<endl;
}

结果