排序—插入法

来自软件实验室
跳转至: 导航搜索
算法要求:用插入排序法对10个整数进行降序排序。
   算法分析:将序列分为有序序列和无序列,依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数,其余n-1个数组成无序序列,则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找,在未找到插入点之前可以同时向后移动元素,为插入元素准备空间。
   算法源代码:
  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] 算法要求:用插入排序法对10个整数进行降序排序。
   算法分析:将序列分为有序序列和无序列,依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数,其余n-1个数组成无序序列,则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找,在未找到插入点之前可以同时向后移动元素,为插入元素准备空间。
   算法源代码:
  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("\n");

}

   算法特点:每趟从无序序列中取出第一个数插入到有序序列的合适位置,元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置(可从前往后或从后往前),再将插入位置之后的元素(有序列中)逐个后移一个位置,最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前,则可将两个操作结合在一起完成,提高算法效率。仍可进行升序或降序排序。=a[j]; /*若未找到插入位置,则当前元素后移一个位置*/
   a[j+1]=t;        /*找到插入位置,完成插入*/
 }
 printf("The sorted numbers: ");
 for(i=0;i<10;i++)
   printf("%d   ",a[i]);
 printf("\n");

}

   算法特点:每趟从无序序列中取出第一个数插入到有序序列的合适位置,元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置(可从前往后或从后往前),再将插入位置之后的元素(有序列中)逐个后移一个位置,最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前,则可将两个操作结合在一起完成,提高算法效率。仍可进行升序或降序排序。