C 语言编程:插入排序算法及实例代码

插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作。

这里以从小到大排序为例进行讲解。

基本思想及举例说明

插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的。

在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时,将第一个元素作为排序好的子数组,插入第二个元素;第二轮,将前两个元素作为排序好的数组,插入第三个元素。以此类推,第i轮排序时,在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。

下面,以对 3  2  4  1 进行选择排序说明插入过程,使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。

第1轮

[ 3 ]  [ 2  4  1 ]  (最初状态,将第1个元素分为排序好的子数组,其余为待插入元素) [ 3 ]  [ 2  4  1 ]  (由于3>2,所以待插入位置j=1) [ 2  3 ]  [ 4  1 ]  (将2插入到位置j)

第2轮

[ 2  3 ]  [ 4  1 ] (第1轮排序结果) [ 2  3 ]  [ 4  1 ] (由于2