插入排序直接插入排序

插入排序

呃，先声明下，这是我查课本后一个字一个字码上去的，可不是ctrl+c,ctrl+v上去的··· 插入排序有好几种，如：直接插入排序，二分插入排序，表插入排序··· 这里只介绍直接插入排序，其余还望楼主自己上网找资料。

代码(只给出整型数组排序） void InsertSort(int*array,int n) { int i,j,t;//i表示插入次数，共进行n-1次插入 for(i=1;i<n;i++) { t=array[i];//把待排元素赋给t，移动 j=i-1; while((j>=0)&&(t<array[j])) { array[j+1]=array[j]; j--;//顺序比较和移动 } array[j+1]=t;//再次移动 } } 效率分析： 从空间上看：它只需要一个元素的辅助空间，用于元素的位置交换。

从时间分析：向有序表中逐个插入记录的操作，进行了n-1次，每次操作分为比较关键码和移动记录，而比较次数和移动记录的次数取决于待排序列关键码的初始排列。

最好情况下，即待排序列已按关键码有序，每次操作只需1次比较，2次移动。

总比较次数=n-1次 总移动次数=2(n-1)次 最坏情况下，即第j次操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。

总比较次数= n-1 ∑j=(1/2)n(n-1); j=1 总移动次数= n-1 ∑(j+1)=(1/2)n(n-1)+2n; j=1 平均情况下，即第j次操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录次数为j/2+2次。

因此，直接插入排序的时间复杂度为O（n2)。

直接插入算法的元素移动是顺序的，该方法是稳定的。

希望能帮到你~~~

C语言插入法排序

算法要求：用插入排序法对10个整数进行降序排序。

算法分析：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。

初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。

寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。

算法源代码： # include <stdio.h> main() { int a[10],i,j,t; printf("Please input 10 numbers: "); for(i=0;i<10;i++) scanf("%d",&a[i]); for(i=1;i<10;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/ { t=a[i]; /*将待插入数暂存于变量t中*/ for( j=i-1 ; j>=0 && t>a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/ a[j+1]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/ a[j+1]=t; /*找到插入位置，完成插入*/ } printf("The sorted numbers: "); for(i=0;i<10;i++) printf("%d ",a[i]); printf(" "); } 算法特点：每趟从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一趟插入后才能确定位置。

也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。

该算法的特点是在寻找插入位置的同时完成元素的移动。

因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。

仍可进行升序或降序排序。

c语言插入排序

已经测试过可行。

#include"stdio.h" #define MAXSIZE 20//一个用作示例的小顺序表的最大长度 int Insertsort(int r[],int n) {//作直接插入排序 int i,j; for(i=2;i<=n;i++) { r[0]=r[i]; //r[0]用作哨兵单元 j=i-1; while(r[0]什么叫插入排序?本来准备用个人理解来说的, 但是怕误导了你, 还是看百科里面的解释吧, 很详细. 如果觉得太多, 可以只看基本概念, 很清晰的. 插入排序: /zh/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F 冒泡排序: /view/254413.html?fromTaglist

直接插入排序

直接插入排序的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。