直接插入法排序

81 阅读 0 评论 54 点赞

我是靠谱客的博主多情凉面，最近开发中收集的这篇文章主要介绍直接插入法排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文试例在VS编译器下可正常使用

算法思想：每次从待排序的原始序列中取出一个元素，将其排入一个新的有序数列中，这实际上是一个有序子序列不断增长的过程，当有序子序列与原序列的长度一致时，排序完成。

假设有这个一个序列

初始状态： {(5)，6，3，9，2，7，1}

第1趟排序：{(6，5)，3，9，2，7，1}

第2趟排序：{(6，5，3)，9，2，7，1}

第3趟排序：{(9，6，5，3)，2，7，1}

第4趟排序：{(9，6，5，3，2)，7，1}

第5趟排序：{(9，7，6，5，3，2)，1}

第6趟排序：{(9，7，6，5，3，2，1)}

//直接插入法排序函数主体
//参数1：待排序的序列
//参数2：序列的长度
//实现从大到小的排序
void insertSort(int array[],int arraySize)
{
	int i , j , tmp;
	for(i = 1 ; i < arrySize ; i++)	//循环遍历序列
	{
		tmp = array[i];
		j = i - 1;
		while(j >= 0 && tmp > array[j])	//j >= 0 是为了检测是否排序完全部
		{
			array[j + 1] = array[j--];
		}
		array[j + 1] = temp;
	}
}

i j

1 0 主循环第一趟
2 1、0 主循环第二趟

3 2、1、0 主循环第三趟

4 3、2、1、0 主循环第四趟

5 4、3、2、1、0 主循环第五趟

6 5、4、3、2、1、0 主循环第六趟

while(j >= 0 && tmp >= array[j])

意思就是每次都会直接和有序序列的最后一个值进行比较，因为有序序列是按照从大到小来排列的，因此，如果他比最小的都还要小，也就不用再进行前面的比较了

直接执行array[j + 1] = temp;

把他插到有序序列的最后

倘若他比最后一个元素（最小值）要大，那他就会进入while的循环体中

其中

array[j + 1] = array[j--];

相当于

array[j + 1] = array[j];

j--;

意思就是如果发现tmp >= array[j]（也就是tmp的值要大于已形成的有序序列中的第j个元素）

就将有序序列中的第j个元素往后移动一位（因为是从大到小排序）

然后再将j自减1，下一趟就是进行再往前（往前是更大的元素），进行比较

如果前面没有元素了，或者，前一个元素的值比当前要插入的值要大，则跳出while循环。

执行array[j + 1] = temp;

如此往复，直至比较完成。

完整代码

#include <stdio.h>

//直接插入法排序函数主体
//参数1：待排序的序列
//参数2：序列的长度
//实现从大到小的排序
void insertSort(int  array[],int arraySize)
{
	int i , j , tmp,k = 0;
	for(i = 1 ; i < arraySize ; i++)	
	{
		tmp = array[i]; 
		j = i - 1;		
    	while(j >= 0 && tmp > array[j])	
		{
			array[j + 1] = array[j--];
		}
		array[j + 1] = tmp;
	}
}


int main()
{
	int a[7] = {5,6,3,9,2,7,1};
	insertSort(a,7);	
	int i = 0;
	for(i = 0 ; i < 7 ; i++)
	{
		printf("%d",a[i]);
	}
	printf("n");
	return 0;
}