复习数据结构：排序（一）——插入排序-蒲公英云

复习数据结构：排序（一）——插入排序

从这一篇开始，我开始复习数据结构的知识点，博文主要偏重于每个知识点的核心思想，以及代码实现。这一篇先从排序算法中的插入排序开始。

稳定排序、内排序、适合少量数据量的排序。
当输入数组已经排好序时，插入排序需要O(n)，快排需要O(n^2)。
当输入数组倒序排列时，插入排序时复为：O(n^2)。
平均时间复杂度：O(n^2)。

插入排序的基本做法是：将一个数插入到一个已经排列好的数组中，通过移动这个数的位置，使得插入之后的数组也是有序的，不断重复这个过程，使得最终所有的数都是有序的。

实现代码如下：

#include<iostream>
using namespace std; 
void InsertSort(int a[], int n)
{
    for(int i = 1; i < n; i++)
    {
        if(a[i] < a[i-1])  // a[i]是待排元素，前面i-1个数已经排序好
        {
            int j = i-1;  // 准备前移
            int x = a[i]; 
            a[i] = a[i-1]; 
            while(x < a[j])
            {
                a[j+1] = a[j]; 
                j--; 
            }
            a[j+1] = x; 
        }
    }
}
int main()
{
    int a[] = {2, 1, 5, 8, 4, 3}; 
    InsertSort(a, 6); 
    for(int i = 0; i< 6; i++)
        cout<<a[i]<<' '; 
    cout<<endl; 
    return 0; 
}