排序算法——插入排序

插入排序

假设

1. 待排序元素放在一个数组中(a[1], a[2], a[3], ..., a[n])

2. 待排序元素均为简单正整数

3. 排序目标是从左到右递增

步骤

1. 第一个元素放在原地，成为第一个已排序数组的第一个元素

2. 从第二个元素开始，将待排序数组第一个元素(a[j])与已排序数组最后一个(a[i])比较

2.1 如果小于它(a[j] < a[i])，就与已排序数组的倒数第二个元素(a[i-1])比较

2.2 如果大于或等于它(a[j] >= a[i])，就将其放在它后面

3. 已排序数组长度加1(i++)，继续处理下一个待排序元素(j++)

如下图所示

插入排序简介