算法基础之插入算法和代码

　　之前我们了解了C语言中的选择排序算法和冒泡排序算法，今天课课家笔者给大家介绍C语言中的另一种算法--插入算法。那么到底什么是C语言中的插入算法呢？它的具体编写运用又是怎样的呢？下面由笔者慢慢道来。

　　在实际的编写程序过程中，在对一个已经有序的数据序列中插入一个数，要求插入后此数据序列仍然有序，此时我们通常会使用到插入排序算法来进行操作。插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，这种算法适用于少量数据的排序，时间复杂度为O(n^2)，它是一种稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（也就是待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

　　插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。插入排序是排序算法的一种，它不改变原有的序列（数组），而是创建一个新的序列，在新序列上进行操作。在实际使用中，通常是排序整个无序数组，所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮将第一个元素作为排序好的子数组，插入第二个元素；第二轮将前两个元素作为排序好的数组，插入第三个元素。以此类推，第i轮排序时在前i个元素的子数组中插入第i+1个元素，直到所有元素都加入排序好数组。

　　下面笔者以对3241进行选择排序说明插入过程，并使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。

　　第1轮

　　[3][241]（最初状态，将第1个元素分为排序好的子数组，其余为待插入元素）

　　[3][241]（由于3>2，所以待插入位置j=1）

　　[23][41]（将2插入到位置j）

　　第2轮

　　[23][41]（第1轮排序结果）

　　[23][41]（由于2<4，所以先假定j=2）

　　[23][41]（由于3<4，所以j=3）

　　[234][1]（由于4刚好在位置3，无需插入）

　　第3轮

　　[234][1]（第2轮排序结果）

　　[234][1]（由于1<2，所以j=1）

　　[1234]（将1插入位置j，待排序元素为空，排序结束）

　　◎总结及实现

　　选择排序对大小为N的无序数组R[N]进行排序，进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组，然后将剩余的N-1个元素逐个插入到已经排序好子数组；。因此在第i轮排序时，前i个元素总是有序的，将第i+1个元素插入到正确的位置。

　　#include<stdio.h>

　　#include<stdlib.h>

　　#defineN8

　　voidinsert_sort(inta[],intn);

　　//插入排序实现,这里按从小到大排序

　　voidinsert_sort(inta[],intn)//n为数组a的元素个数

　　{

　　//进行N-1轮插入过程

　　for(inti=1;i<n;i++)

　　{

　　//首先找到元素a[i]需要插入的位置

　　intj=0;

　　while((a[j]<a[i])&&(j<i))

　　{

　　j++;

　　}

　　//将元素插入到正确的位置

　　if(i!=j)//如果i==j，说明a[i]刚好在正确的位置

　　{

　　inttemp=a[i];

　　for(intk=i;k>j;k--)

　　{

　　a[k]=a[k-1];

　　}

　　a[j]=temp;

　　}

　　}

　　}

　　intmain()

　　{

　　intnum[N]={89,38,11,78,96,44,19,25};

　　insert_sort(num,N);

　　for(inti=0;i<N;i++)

　　printf("%d",num[i]);

　　printf("\\n");

　　system("pause");

　　return0;

　　}

　　PS：插入排序是一种稳定的排序算法，它不会改变原有序列中相同数字的顺序。当然如果刚开始这个有序的小序列只有1个元素，那么它就是第一个元素，而比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，不然就一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

　　本次算法基础之插入算法和代码的讲解到此暂告一段落，如果以后有什么相关内容进行补充或者修改的话，笔者会继续在此进行相关内容的补充或者修改的工作，同时也欢迎大家对本次的讲解提出自己的建议和补充。最后笔者希望本次的教程对大家学习C语言能够起到一定的帮助作用！