基本思想:排序方式就像许多人排序扑克牌一样。开始的时候左手为空的并且桌子上的牌牌面朝下,然后我们依次从桌面上拿走一张牌(是牌堆顶部的那张牌)并从右到左的与已在左手中的每张牌进行比较,然后插入的相应的位置,使左手的牌总是排好序的。

/************************************************************************/
 
/*
 
*                       时间:2018年1月12日
 
*
 
*                       排序算法:直接插入排序
 
 
 
*                       时间复杂度:最好情况O(n),最坏情况O(n^2)
 
*                       空间复杂度:O(1)
 
*                       稳  定  性:稳定
 
*/
 
/************************************************************************/
 
 
 
#include<iostream>
 
#include<time.h>
 
void InsertSort(int Array[], int len)
 
{
 
    int key = 0;
 
    int i = 0;
 
 
 
    if (len < 2)
 
    {
 
        throw"Not enough numbers";
 
        exit(0);
 
    }
 
 
 
    for (int j = 1; j < len; j++)
 
    {
 
        key = Array[j];//保存当前值
 
        i = j - 1;
 
 
 
        while (i >= 0 && key < Array[i])
 
        {
 
            Array[i + 1] = Array[i]; //把大值放后面
 
            i--;
 
        }
 
        Array[i + 1] = key;
 
    }
 
}
 
 
 
int main()
 
{
 
    int n = 0;
 
    int *p = nullptr;
 
 
 
    srand((unsigned)time(NULL));
 
 
 
    std::cout << "请输入随机数个数:" << std::endl;
 
    std::cin >> n;
 
    p = new int[n];
 
 
 
    std::cout << "排序前: ";
 
    for (int i = 0; i < n; i++)
 
    {
 
        p[i] = rand() % 101;
 
        std::cout << p[i]<<"  ";
 
    }
 
 
 
    InsertSort(p, 10);
 
 
 
    std::cout << std::endl << "排序后: ";
 
    for (int i = 0; i < n; i++)
 
    {
 
        std::cout << p[i] << "  ";
 
    }
 
 
 
    system("pause");
 
 
 
    return 0;
 
}