本文主要是介绍（直接）插入排序INSERT_SORT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、伪代码
/*INSERT_SORT(A)*/
for j = 2 to A.lengthkey = A[j]//Insert A[j] into the sorted sequence A[1..j-1].i = j-1while i>0 and A[i]>keyA[i+1] = A[i]i = i-1
A[i+1] = key二、算法描述
数组A[1..n]是一个包含n个元素的待排序的序列，其长度用A.length表示，显然有A.length=n.从序列A的第二个元素开始，在循环变量为j的for循环中，每次迭代开始时，包含元素A[1..j-1]的子序列是已经排序好的序列，剩下的子序列A[j+1..n]就是待排列的序列，而元素A[j]就是待插入（已排列好的序列A[1..j-1]中）元素，待排列中的第一个元素取就是下一次待插入的元素。将待排列元素A[j]的值存储在临时变量key中，然后key和A[j-1]即A[i]比较大小。当key的值小于已排列好的序列A[1..j-1]中的最大值即A[j-1],那么将A[j-1]向后移动一位即将A[j-1]的值赋给A[j],（此时A[j]的值仍然保存在变量key中，所以不必担心A[j]的值被覆盖）这一步是通过语句A[i+1]=A[i](i=j-1)来实现的。接着执行语句i=i-1,回到while语句的条件判断A[i]>key,即将key的值和已经排列好的序列中的第二大的元素A[j-2]即A[i](此时i=（j-1）-1),如果条件满足则重复上一过程，否则跳出while循环，并把key的值赋给元素A[i+1]，至此完成了一次插值，即为元素A[j]找到了合适的插入位置。
简单来说，（直接）插入排序算法就是依次从序列A[1..n]中取出一个元素A[j]并与前一个元素A [j-1]相比，如果取出的元素的值A[j]比之前一个元素的值A[j-1]大，则将取出的元素A[j]放在前一个元素A[j-1]之后，否则将取出的元素A[j]和前一个元素A[j-1]的前一个元素A[j-2]相比，重复该过程，直到找到第一个小于取出的元素A[j]的元素A[i],则将取出的元素A[j]放在元素A[i]之后，完成了一次插入排序。重复上述过程，直到完成所有元素的排序。
【注】上述过程假设将序列A[1..n]按照从小到大的顺序进行排序。
三、C语言源代码
/******************************
*源代码（一） By 羽墨
*根据《算法导论》中伪代码编写
*******************************/
void insert_sort(int *A)
{int length = 6;int i=0,j=0;int key=0;for(j=1;j<=length-1;j++){key = A[j];//Insert A[j] into the sorted sequence A[1..j-1].i = j-1;while(i>=0&&A[i]>key){A[i+1] = A[i];i = i-1;}A[i+1] = key;}
}
/******************************
*源代码（二） By 羽墨
*在理解上述代码的基础上重新编写
*******************************/
void insert_sort(int *A)
{int i=0;int length = 6;int key = A[0];for(i=0;i<length;i++){int j = 0;key = A[i];for(j=i-1;j>=0;j--){if(key<A[j]){A[j+1] = A[j];}else{break;}}A[j+1] = key;}
}
/*****************************
*主函数 By 羽墨
*****************************/
void main()
{int array[] = {5,2,4,6,1,3};//初始化待排序数组printf("The original");print_array(array);//打印原始数组insert_sort(array);printf("The sorted");print_array(array);//打印排序后的数组
}/**********************运行结果********************/
The original array = [5 2 4 6 1 3 ] //原始数组
The sorted array = [1 2 3 4 5 6 ] //排序后的数组
其中，数组打印函数为print_array()。
/******************************
*数组打印函数 By 羽墨
*******************************/
void print_array(int *array)
{int i = 0;printf(" array = [");for(i=0;i<=5;i++){printf("%d ",array[i]);}printf("]\n");
}以上代码为笔者阅读《算法导论》时的练习笔记，作记录之用，在VC++ 6.0环境中编译通过，仅供参考！
这篇关于（直接）插入排序INSERT_SORT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
