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


----------

时间: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;

}