文章插图
插入排序(insertion sort)
如果需要对一个小型数组进行升序排列，那么可以选用插入排序，插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述 。
可以把左手中的牌比做已经摸起的牌，即已经被排列好的牌，左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同；而在桌子上的那部分没摸的牌则是未被排序的牌，这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分 。
一开始摸起的第一张牌不需要排序，可以认定其为已排序的牌 。
如果用外层循环for来表示摸起的牌的话，则可以抽象为：
// 对象数组
// 桌子上的牌
int A[] = {5,1,3,6,2,4};
// 从数组的第二个元素开始抽取
for(int i = 1; i < sizeof A/sizeof A[0]; ++i)
{
int pick = A[i]; // 被摸起的牌
int j = i - 1; // j记录已排序部分的最后一张牌的位置
. . .
}
而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置，这里示范的排列策略是升序排列，摸起了这张牌后，便自右向左地和手中的牌进行比较 。
把pick称作摸起的牌，如果pick比手中的牌小，则手中较大的那张牌就向右挪一位，pick再和下一张牌做比较，如果下一张牌仍然比pick大，那么那张牌便也向右移动一个位置，依此类推 。
如果手中下一张和pick比较的牌比pick小，那么pick就被插入在了手中前一张牌移动后空下的位置；
或者手中所有的牌都比pick大，那么所有的牌就都向右移动过一个位置，所以pick最终被插入在了手中最左边的位置 。
这个过程可以抽象为：
// 对象数组
// 桌子上的牌
int A[] = {5,1,3,6,2,4};
// 从数组的第二个元素开始抽取
for(int i = 1; i < sizeof A/sizeof A[0]; ++i)
{
int pick = A[i]; // 被摸起的牌
int j = i - 1; // j记录已排序部分的最后一张牌的位置
// 如果循环了j+1次，即j = -1时还未找到比pick小的牌
// 那么pick就是最小的牌被插入在位置A[0]处
// A[j]是当前手中和pick进行比较的牌
while(j >= 0 && A[j] > pick)
{
// 未找到可插入位置，则A[j]向后挪一位
A[j+1] = A[j];
// j减1继续向左定位手中下一张供和pick比较的牌--j;
}
// while结束后，j+1所表达的位置便是pick可以插入的位置
A[j+1] = pick;
}
// 对于有N个元素的数组A，采用插入排序法排序时，当外层循环进行了N-1次后排序完毕
【C语言的插入排序法是什么？】
推荐阅读
- aum是什么意思
- 哈尔滨黑山街有什么好玩的
- 哈尔滨规模最大的学校在在哪里
- 哈尔滨工业大学的文科专业
- 哈尔滨服装城附近有什么好吃的
- 哈尔滨多大面积
- 哈尔滨的中国移动营业厅的地址
- 哈尔滨的雪乡在什么城市
- 哈尔滨的雪乡好看吗
- 哈尔滨的哪些高校有播音主持专业