排序算法-插入算法
Contents
[NOTE] Updated November 19, 2015. This article may have outdated content or subject matter.
描述
大多数纸牌游戏都采用插入排序来排列他们手中的纸牌。他们保持已发到手中的牌有序,当拿到一张新牌时,将其插入到合适的位置。为了将数组x[n]按升序排列,我们首先将第一个元素视为有序子数组x[0..0],然后插入x[1],…,x[n-1],下面4行展示了该止算法在一个四元数组上的执行过程,“|”代表变量i,它左边是有序的,而它右边的元素则还是初始顺序。
3|1 4 2
1 3|4 2
1 3 4|2
1 2 3 4|
筛选过程通过一个从右到左的循环实现,该循环使用变量j跟踪被筛选的元素。只要该元素具有前驱(即j>0)且没有到达最终位置(即该元素小于它的前驱),就交换该元素和它的前驱。完整的程序如下所示
|
|
说明: 本文非原创,是编程珠玑的看书笔记
Author beyondkmp
LastMod 2015-11-19