基本思想：排序方式就像许多人排序扑克牌一样。开始的时候左手为空的并且桌子上的牌牌面朝下，然后我们依次从桌面上拿走一张牌（是牌堆顶部的那张牌）并从右到左的与已在左手中的每张牌进行比较，然后插入的相应的位置，使左手的牌总是排好序的。
----------
/*时间：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;
}