算法-排序-插入

算法-排序

3 插入排序

特点

  • 简单
  • 对少量数据性能较好
  • 稳定

简介

插入排序,顾名思义,把待排序的数据插入到应该在的位置.

演示

原始数据(8个)
7 4 8 3 2 5 1 6

第一次排序
7 4 8 3 2 5 1 6

第二次排序
4 7 8 3 2 5 1 6

第三次排序
4 7 8 3 2 5 1 6

第四次排序
3 4 7 8 2 5 1 6

第五次排序
2 3 4 7 8 5 1 6

第六次排序
2 3 4 5 7 8 1 6

第七次排序
1 2 3 4 5 7 8 6

第八次排序
1 2 3 4 5 6 7 8

演示解析

第 i 次排序,是将a[i]从 i 向前移动 j 个数字,直到a[j]小于a[i]。

实现

1
2
3
4
5
6
7
8
9
10
void Sort(int array[], int n)
{
for(int i = 0; i < n; i++)
{
int j;
for(int j = i; j > 0 && array[j] < array[j - 1]; j--) //当a[j]大于a[j - i]且没越界
swap(array[j], array[j - 1]); //向后移动
array[j - 1] = array[i]; //填充空位
}
}

END

插入排序依旧是一中较为简单的排序,接下来还有快速、堆、桶排序等。