插入排序

插入排序的基本思想：每次从未排序的序列中取一个元素，插入到已经排好序的序列的合适位置。小规模输入来说，插入排序速度比较快。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序。

数组的插入排序算法如下：

#include<iostream>

using namespace std;

void InsertSort(int array[], int length)
{
    for (int j = 1; j < length; ++j)
    {
        int key,i;
        key = array[j];
        i = j - 1;
        while (array[i] > key && i >= 0)
        {
            array[i + 1] = array[i];
            i--;
        }

        array[i + 1] = key;
    }

}

int main()
{
    int a[100];
    int n;
    cout << "请输入数字个数：";
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    InsertSort(a, n);
    cout << "排序后：";
    for (int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}