非数值计算常用经典算法,插入法三种常见排序算法分析

1、调换(两量交流借助第三者) 不信赖第多个变量

一、冒泡法(起泡法)

参考:

 算法须求:用起泡法对11个整数按升序排序。

2、累加

   
算法分析:假如有n个数,则要开展n-1趟相比较。在第1趟比较中要扩充n-1次相邻成分的两两相比较,在第j趟比较中要进行n-j次两两相比。相比较的种种在此从前以后,经过一趟相比后,将最值沉底(换来最终三个因素地点),最大值沉底为升序,最小值沉底为降序。

累加算法的中心境想是形如“s=s+A”的累加式,此式必得出现在循环中本事被再三试行,进而达成拉长功效。“A”经常是有规律变化的表达式,s在走入循环前必需须到适当的初值,平时为0。比如:求1+2+3+……+100的和。sum=0;i=1;sum=sum+i;i++;

    算法源代码:

3、累乘

# include <stdio.h>

累乘算法的要点是形如“s=s*A”的累乘式,此式必须出现在循环中技能被反复施行,进而完结累乘成效。“A”平常是有规律变化的表明式,s在进入循环前必需得到适当的初值,日常为1。比如:求10!n=10;sum=1;n>0sum=sum*n;n–;

main()

非数值总括常用杰出算法

1、穷举**

也称之为“枚举法”,就要恐怕出现的各类状态每种测验,判别是不是满足条件,平日选用循环来促成。比如:用穷举法输出全体的姚女花数(即那样的几人正整数:其每位数位上的数字的立方和与该数相等,举个例子:13+53+33=153)。

#include <stdio.h>int main(){ int a,b,c,i; for(i=100;i<1000;i++){ a=i/100; b=%10; c=i%10; if(i==a*a*a+b*b*b+c*c*c) printf; }}
2.排序

参考:

冒泡排序

永利澳门游戏网站,比如要对蕴含n个数的行列进行升序排列,冒泡排序算法步骤是:1、从寄放体系的数组中的首个成分开头到最终贰个因素,依次对相近两数举办相比,若前面一个大前者小,则沟通两数的职分;2、第一趟甘休后,最大数就存放到数组的末梢叁个因素里了,然后从第二个要素开头到尾数第三个要素,依次对周围两数实行比较,若前面二个大前面一个小,则交流两数的职位;3、重复步骤1
n-1趟,每一回比前一趟少相比较一遍,就能够到位所求。

#include <stdio.h>#define GET_ARRAY_LEN(array,len) {len = (sizeof / sizeof);}int main(){ int i,j,len=0; int a[5]={1,5,3,2,4}; GET_ARRAY_LEN; printf("%dn",len); for(i=0;i<len-1;i++){ for(j=0;j<len-i-1;j++){ if(a[j]>a[j+1]){ int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=0;i<len;i++){ printf("%dn",a[i]); }}

挑选法排序

挑选法排序是相持好精通的排序算法。假使要对含有n个数的类别进行升序排列,算法步骤是:1、从数组寄放的n个数中找寻最小数的下标(算法见上面包车型大巴“求最值”),然后将小小数与第一个数沟通地点;2、除首个数以外,再从另外n-1个数中搜索最小数(即n个数中的次小数)的下标,将此数与第4个数调换个方式置;3、重复步骤1
n-1趟,就能够成功所求。

#include <stdio.h>#define GET_ARRAY_LEN(array,len) {len = (sizeof / sizeof);}int main(){ int a[5]={5,2,1,4,3}; int i,j,min,temp; for(i=0;i<5-1;i++){ min=i; //查找最小值 for(j=i+1;j<5;j++) if(a[min]>a[j]) min=j; //交换 if{ temp =a[min]; a[min]=a[i]; a[i]=temp; } } for(i=0;i<5;i++){ printf("%dn",a[i]); }}

安顿法排序

要想很好地明白此算法,先请垂询“有序体系的插入算法”,就是将某数码插入到贰个照猫画虎体系后,该体系依然长久以来。插入法排序的要点正是每读入二个数马上插入到终极寄存的数组中,每便插入都使得该数组有序。参谋:

#include <stdio.h>#define GET_ARRAY_LEN(array,len) {len = (sizeof / sizeof);}int main(){ int a[5]={5,2,1,4,3}; int i,j,temp; //假定第一个元素被放到了正确的位置 for(i=1;i<5;i++){ j=i; temp=a[i]; while(j>0&&temp<a[j-1]){ a[j]=a[j-1]; j--; } a[j]=temp; } for(i=0;i<5;i++){ printf("%dn",a[i]); }}

**归并排序 **

就要四个都升序排列的数码连串合併成一个仍按原序排列的种类。比如:有二个包括6个数据的升序种类和一个包罗4个数据的升序体系,将两端合并成三个含有十一个数据的升序种类。

参考:

#include <stdlib.h>#include <stdio.h> typedef int RecType;//要排序元素类型 void Merge(RecType *R,int low,int m,int high) { //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high] int i=low,j=m+1,p=0; //置初始值 RecType *R1; //R1是局部向量 R1=(RecType *)malloc((high-low+1)*sizeof; if { return; //申请空间失败 } while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 { R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; } while //若第1个子文件非空,则复制剩余记录到R1中 { R1[p++]=R[i++]; } while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中 { R1[p++]=R[j++]; } for(p=0,i=low;i<=high;p++,i++) { R[i]=R1[p]; //归并完成后将结果复制回R[low..high] } } void MergeSort(RecType R[],int low,int high) { //用分治法对R[low..high]进行二路归并排序 int mid; if(low<high) { //区间长度大于1 mid=/2; //分解 MergeSort(R,low,mid); //递归地对R[low..mid]排序 MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序 Merge(R,low,mid,high); //组合,将两个有序区归并为一个有序区 } } void main() { int a[7]={49,38,65,97,76,13,27}; //这里对8个元素进行排序 int low=0,high=6,i; //初始化low和high的值 printf("Before merge sort: "); for(i=low;i<=high;i++) { printf("%d ",a[i]); //输出测试 } printf; MergeSort(a,low,high); printf("After merge sort: "); for( i=low;i<=high;i++) { printf("%d ",a[i]); //输出测试 } printf; } 
3.查找

逐条查找

依次查找的思绪是:将待查找的量与数组中的每三个要素举办比较,若有一个成分与之对等则找到;若比少之又少个因素与之齐名则找不到。举个例子:大肆读入10个数寄存到数组a中,然后读入待查找数值,寄放到x中,决断a中有无与x等值的数。

#include <stdio.h>#define MAX 10int main(){ int a[MAX]; int x,i; for(i=0;i<MAX;i++){ scanf("%d",&a[i]); } printf; for(i=0;i<MAX;i++){ printf("%d",a[i]); } printf; scanf("%d",&x); for(i=0;i<MAX;i++){ if printf; } return 0;}

折半招来

各种查找的频率很低,当数码很多时,用二分法查找能够升高功能。使用二分法查找的前提是数列必得有序。二分法查找的思路是:要寻觅的体贴值同数组的中档一个要素比较,若同样则查找成功,截止;不然决断关键值落在数组的哪半有些,就在那半某个中按上述方法继续比较,直到找到或数组中从不及此的成分值停止。举例:率性读入二个整数x,在升序数组a中寻找是还是不是有与x等值的要素。参照他事他说加以考察:

//递归折半 #include <stdio.h> int binary_search(int search_table[],int low,int high,int key) { if (low>high) return -1; int mid=/2; if (search_table[mid]==key) return mid; if (search_table[mid]>key) return binary_search(search_table,low,mid-1,key); else return binary_search(search_table,mid+1,high,key); }int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9}; int x,i,y; scanf("%d",&x); if((y=binary_search>=0) printf("%d是第%d个数",x,y+1); else printf("未找到%dn",x); return 0;}

{

  int a[10],i,j,t;

  printf(“Please input 10 numbers: “);

  /*输入源数据*/

  for(i=0;i<10;i++)

    scanf(“%d”,&a[i]);

  /*排序*/

  for(j=0;j<9;j++)    /*外循环调整排序趟数,n个数排n-1趟*/

    for(i=0;i<9-j;i++)   /*内循环每一回相比较的次数,第j趟相比n-j次*/

      if(a[i]>a[i+1])    /*相邻成分相比较,逆序则交换*/

      { t=a[i];

        a[i]=a[i+1];

        a[i+1]=t;

      }

  /*出口排序结果*/

  printf(“The sorted numbers: “);

  for(i=0;i<10;i++)

    printf(“%d   “,a[i]);

  printf(“n”);

}

   
算法特点:相邻成分两两比较,每一趟将最值沉底就可以鲜明二个数在结果的岗位,鲜明因素地方的逐个是从后往前,其他成分大概作相对地方的调动。能够实行升序或降序排序。

二、选择法

    算法供给:用选拔法对12个整数按降序排序。

   
算法分析:每便选出贰个最值和冬辰连串的第七个数调换,n个数共选n-1趟。第i趟若是i为最值下标,然后将最值和i+1至最后贰个数相比,寻找最值的下标,若最值下标不为初设值,则将最值成分和下标为i的因素沟通。

    算法源代码:

# include <stdio.h>

main()

{

  int a[10],i,j,k,t,n=10;

  printf(“Please input 10 numbers:”);

  for(i=0;i<10;i++)

    scanf(“%d”,&a[i]);

  for(i=0;i<n-1;i++)   /*外循环调控趟数,n个数选n-1趟*/

  {

发表评论

电子邮件地址不会被公开。 必填项已用*标注