首页 > 数据算法> 详细内容
插入排序
日期:2020-03-13 

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

算法步骤

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

动图演示

插入排序原理很简单,讲一组数据分成两组,我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。就这样,每次插入一个元素,有序组增加,待插入组减少。直到待插入组元素个数为0。当然,插入过程中涉及到了元素的移动。

算法实现:直接插入排序是将无序序列中的数据插入到有序的序列中,在遍历无序序列时,首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置,一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4,6,8,5,9}来说,我们首先先确定首元素4是有序的,然后在无序序列中向右遍历,6大于4则它插入到4的后面,再继续遍历到8,8大于6则插入到6的后面,这样继续直到得到有序序列{4,5,6,8,9}。

(1)我们用一个变量tmp存放关键字,因为我们先确定第一个元素是暂时有序的,所以tmp存放无序序列的第二个元素,然后i开始也为第二个元素的下标,j则为i-1,因为j要用有序的区域元素来与无序的区域元素比较。那么一开始i=1,tmp=6,j=0,因为6>4,所以6就不用进行插入;然后i向右走,i=2,tmp=arr[2]=8,j=i-1=1,8>6>4也不用插入。

(2)i继续向右走,i=3,tmp=arr[3]=5,j=i-1=2,5<8则要将8给5所在的元素数据,j向左走继续遍历有序区域。

(3)当j向右走到6时发现6>tmp=5,所以将6给它右边的第一个值(j+1的位置),再继续遍历有序区域,j=0时发现4<5则j+1的位置就是5该在的位置那么就将tmp的值5给j+1的位置的元素的值。

(4)再继续上面的操作,i最后到9发现比前面有序区域的元素都大,则不用再插入了,这样就得到了一个有序序列{4,5,6,8,9}。

代码实现:
void StraightSort(int *arr,int len)
{
int tmp;
int i;
int j;
for (i = 1;i < len;i++)
{
tmp = arr[i];
for (j = i - 1;j >= 0 && arr[j] > tmp;j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}