算法 - 插入排序

131

概述

插入排序是最简单的排序算法,类似于整理扑克牌。假设左手拿牌,右手抽牌,当抽到第一张牌时直接放在左手中,以后每次抽到一张新牌,都需要对左手中已经排好序的牌进行从右向左一张一张的比较,直到找到比这张新牌小的一张牌,然后将这张新牌放到这张比它小的牌的后面。

图解

插入算法可以用下图说明:

插入排序

首先初始状态为 $4,2,6,5,3,1$。由于 $4$ 本身已经是排好序的了,因此从 $2$ 开始处理。

第一步,处理第二个数 $2$,将 $2$ 与已经排好序的数列的最后一个数 $4$ 做比较,因为 $2 < 4$,所以将 $4$ 移动到后面一个位置。$2$ 继续与数列中的前一个数做比较,因为此时已经到达了数列的开头,没有前一个数了,所以将 $2$ 放到数列的开头。第一步结束。此时已排好序的数列为 $2,4$。

第二步,处理下一个数 $6$,将 $6$ 与已经排好序的数列的最后一个数 $4$ 做比较,因为 $6 > 4$,所以 $6$ 不需要移动位置。第二步结束。此时已经排好序的队列为 $2,4,6$。

第三步,处理下一个数 $5$,将 $5$ 与已经排好序的数列的最后一个数 $6$ 做比较,因为 $5 < 6$,所以将 $6$ 移动到后面一个位置。$5$ 继续与数列中的前一个数 $4$ 做比较,因为 $5 > 4$,所以将 $5$ 放在 $4$ 的后面。第三步结束。此时已经排好序的数列为 $2,4,5,6$。

第四步,处理下一个数 $3$,将 $3$ 与已经排好序的数列的最后一个数 $6$ 做比较,因为 $3 < 6$,所以将 $6$ 移动到后面一个位置。$3$ 继续与数列中的前一个数 $5$ 做比较,因为 $3 < 5$,所以将 $5$ 移动到后面一个位置。$3$ 继续与数列中的前一个数 $4$ 做比较,因为 $3 < 4$,所以将 $4$ 移动到后面一个位置。$3$ 继续与数列中的前一个数 $2$ 做比较,因为 $3 > 2$,所以将 $3$ 放在 $2$ 的后面。第四步结束。此时已经排好序的数列为 $2,3,4,5,6$。

第五步,处理下一个数 $1$,将 $1$ 与已经排好序的数列的最后一个数 $6$ 做比较,因为 $1 < 6$,所以将 $6$ 移动到后面一个位置。$1$ 继续与数列中的前一个数 $5$ 做比较,因为 $1 < 5$,所以将 $5$ 移动到后面一个位置。$1$ 继续与数列中的前一个数 $4$ 做比较,因为 $1 < 4$,所以将 $4$ 移动到后面一个位置。$1$ 继续与数列中的前一个数 $3$ 做比较,因为 $1 < 3$,所以将 $3$ 移动到后面一个位置。$1$ 继续与数列中的前一个数 $2$ 做比较,因为 $1 < 2$,所以将 $2$ 移动到后面一个位置。$1$ 继续与数列中的前一个数做比较,因为此时已经到达了数列的开头,没有前一个数了,所以将 $1$ 放到数列的开头。第五步结束。此时已经排好序的数列为 $1,2,3,4,5,6$。

第六步,处理下一个数。因为没有下一个数了,排序结束。最终的数列为 $1,2,3,4,5,6$。

实现

版权声明:本文为原创文章,转载请注明出处。http://cynhard.com/2018/09/12/AL-Insertion-Sort/

推荐文章