如果需要对一个小型数组进行升序排列那么可以选用插入排序,插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述
可以把左手中的牌比做已經摸起的牌,即已经被排列好的牌左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同;而在桌子上的那部分没摸的牌则是未被排序的牌,这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分
一开始摸起的第一张牌不需要排序,可以认定其為已排序的牌
如果用外层循环for来表示摸起的牌的话,则可以抽象为:
// 从数组的第二个元素开始抽取
而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置这里示范的排列策略是升序排列,摸起了这张牌后便自右向左地和手中的牌进行比较。
把pick称作摸起的牌如果pick比手中的牌小,则手中较大的那张牌就向右挪一位pick再和下一张牌做比较,如果下一张牌仍然比pick大那么那张牌便也向右移动一个位置,依此类推
如果手中下一张和pick比较的牌比pick小,那么pick就被插入在了手中前一张牌移动后空下的位置;
或者手中所有嘚牌都比pick大那么所有的牌就都向右移动过一个位置,所以pick最终被插入在了手中最左边的位置
// 从数组的第二个元素开始抽取
// 如果循环了j+1佽,即j = -1时还未找到比pick小的牌
// 那么pick就是最小的牌被插入在位置A[0]处
// A[j]是当前手中和pick进行比较的牌
// 未找到可插入位置则A[j]向后挪一位
// j减1继续向左定位手中下一张供和pick比较的牌--j;
// while结束后,j+1所表达的位置便是pick可以插入的位置
// 对于有N个元素的数组A采用插入排序法排序时,当外层循环进行了N-1佽后排序完毕
}