精华内容
下载资源
问答
  • 排序算法合集(C语言
    2019-12-04 21:08:08

    1.冒泡排序算法

    一种比较基础的排序方法。其核心思想是:在数列中从左向右(或从右向左)依次两两比较,若前者大于后者则两者交换位置(最终结果为从小到大排列)。

    思考:由于该方法在一次扫描后无法完成排序,所以需要一级循环来控制它的扫描次数;在每一次扫描时需要从左到右遍历一次因此还需要一级循环来控制扫描时的进度。(我个人喜欢将这类问题想象成一个二维坐标,一层循环代表x轴,一层循环代表y轴,通过这两层循环,就可以扫描到二维坐标上的每一个整数点了,然后只需在特定地点的特定条件下做特定的动作即可。)

    代码实现:

    #include<stdio.h>
    int a[82]={1};// 储存需要排序的数列。 
    int main ()
    {
       int n,i,j,k;
       scanf("%d",&n);//确定数列中数的个数。
       for(i=0;i<n;i++){
       	scanf("%d",&a[i]);//将待排列的数列录入数组中。 
       }
       for(i=0;i<n-1;i++) {//控制扫描次数 
       	for(j=0;j<n-1-i;j++){//控制每次扫描的进程 
       		if(a[j]>a[j+1]){
       			k=a[j];
       			a[j]=a[j+1];
       			a[j+1]=k;
       		}
       	}
       }
       for(i=0;i<n;i++){
       	printf("%d ",a[i]);
       }
       return 0;
    } 
    

    冒泡排序算法的弊端:如果数列早在前几次扫描后便以有序,但上述代码依然会继续执行扫描,这样就会使代码效率变差。

    冒泡排序算法的优化:可以利用引入一标志变量来解决。当一次扫描完成后,数列未进行交换及证明其以有序(可通过标志变量来判断),当其有序后跳出循环即可。
    代码实现:

    #include<stdio.h>
    int a[82]={1};// 储存需要排序的数列。 
    int main ()
    {
    	int n,i,j,k,m;
    	scanf("%d",&n);//确定数列中数的个数。
    	for(i=0;i<n;i++){
    		scanf("%d",&a[i]);//将待排列的数列录入数组中。 
    	}
    	for(i=0;i<n-1;i++) {//控制扫描次数 。 
    		m==0;//初始化标志变量 (极其重要) 。 
    		for(j=0;j<n-1-i;j++){//控制每次扫描的进程 。 
    			if(a[j]>a[j+1]){
    				k=a[j];
    				a[j]=a[j+1];
    				a[j+1]=k;
    				m=1;//若交换则改变标志变量 。 
    			}
    		}
    		if(m==0) break;//判断数列是否发生交换。 
    	}
    	for(i=0;i<n;i++){
    		printf("%d ",a[i]);
    	}
    	return 0;
     } 
    

    2.选择排序算法

    与冒泡排序非常相似的一种排序算法。其核心思想是在扫描的每一轮中都找出剩余数中的最小值(或最大值)放在未排号数列的最左边(最终结果为从小到大排序)。

    思考:与冒泡排序相似用两重循环来分别控制行和列,只是其中部分细节不同。

    代码实现:

    #include<stdio.h>
    int a[82]={0};//储存需要排序的数列。 
    int main ()
    {
    	int n,i,j,k,m;
    	scanf("%d",&n);//确定数列中数的个数。
    	for(i=0;i<n;i++){
    		scanf("%d",&a[i]);//将待排列的数列录入数组中。 
    	}
    	for(i=0;i<n-1;i++) {//控制扫描次数 。
    		k=i;//用于记录未排序的数列最左边的序号。 
    		for(j=i;j<=n-1;j++){//控制每次扫描的进程 。
    			if(a[j]<a[k]){
    				k=j;//找出剩余数中最小的。 
    			}
    		}
    		if(k!=i){//当最小值非最左边的数时,使其与最左边的数交换。 
    			m=a[i];
    			a[i]=a[k];
    			a[k]=m;
    		}
    	} 
    	for(i=0;i<n;i++){
    		printf("%d ",a[i]);
    	}
    	return 0;
     } 
    

    3. 快速排序:

    快速排序的基本思想:
    1.在数列中找到一个基准数。
    2.在数列中找到比该数大的数放在其右侧,找到比该数小的数放在其左侧。
    3.在基准数的两端放别再进行2步骤直到分别只剩一个数时为止。

    思考:看着这个基本思想看起来到还好像挺轻松的,那我们再来看看到底具体怎样实现它呢。
    实际上快速排序可以拆分为两个函数:挖空填数法+分治法

    挖空填数法

    以数列中的第一个数为基准数用x来保存它,即第一个数的位置被我们挖了一个空(该位置我们用i记录)。首先从数列右侧开始找到第一个比x小的数(这个数的位置我们用j记录),将其放在我们挖的空中(也就是第一个数的位置)之后i++,此时j的位置就又变成了我们的空;之后从i的位置向左找,找到第一个比x大的数放在我们j的位置之后j–;…重复以上做法直到i与j相当时即可(也就代表了整个数列已经被扫描完了)
    代码实现:

    int wakong(int a[],int b,int c)
    {
    	int i,j,x;
    	i=b;j=c;x=a[b];//分别记录左端,右端,基准数 。 
    	while(i<j){//直到i=j 时停止循环 
    		while(i<j&&a[j]>=x) j--;//从右向左找比基准数小的数并用j记录其位置 
    		if(j>i){
    			a[i]=a[j];//将找到的数放在i的空中 
    			i++;
    		}
    		while(i<j&&a[i]<x) i++;//从左到又找比基准数大的数并用i记录其位置 
    		if(j>i){
    			a[j]=a[i];//将找到的数放在j的空中 
    			j--;
    		}
    	}
    	a[i]=x;//当扫描完整个数列后i=j(此时在数列的中间位置),此时将 x(基准数) 填入该空即可 
    	return i;//返回中间的位置将数列分为左区和右区以便分治法时确定端点 
    }
    

    分治法

    分治法的精髓:
    分–将问题分解为规模更小的子问题;
    治–将这些规模更小的子问题逐个击破;
    合–将已解决的子问题合并,最终得出“母”问题的解;
    类似于递归的思想。(关于递归我会再写一篇博客在其中详细说明)。
    代码实现:

    void quck(int a[],int b,int c)
    {
    	 if(b<c){
    	 	int i=wakeng(a,b,c);//调用挖空法调整端点的位置; 
    	 	quck(a,b,i-1);//左区递归 
    	 	quck(a,i+1,c);//右区递归 
    	 }
    }
    

    将两种函数结合起来就是我们所说的快速排序法了。
    代码实现:

    #include<stdio.h>
    int wakong(int a[],int b,int c)
    {
    	int i,j,x;
    	i=b;j=c;x=a[b];//分别记录左端,右端,基准数 。 
    	while(i<j){//直到i=j 时停止循环 
    		while(i<j&&a[j]>=x) j--;//从右向左找比基准数小的数并用j记录其位置 
    		if(j>i){
    			a[i]=a[j];//将找到的数放在i的空中 
    			i++;
    		}
    		while(i<j&&a[i]<x) i++;//从左到又找比基准数大的数并用i记录其位置 
    		if(j>i){
    			a[j]=a[i];//将找到的数放在j的空中 
    			j--;
    		}
    	}
    	a[i]=x;//当扫描完整个数列后i=j(此时在数列的中间位置),此时将 x(基准数) 填入该空即可 
    	return i;//返回中间的位置将数列分为左区和右区以便分治法时确定端点 
    }
    void quck(int a[],int b,int c)
    {
    	 if(b<c){
    	 	int i=wakeng(a,b,c);//调用挖空法调整端点的位置; 
    	 	quck(a,b,i-1);//左区递归 
    	 	quck(a,i+1,c);//右区递归 
    	 }
    }
    int main ()
    {
    	int n,i,j,k,m,x;
    	int num[82];
    	scanf("%d",&n);//确定数列中数的个数。
    	for(i=0;i<n;i++){
    		scanf("%d",&num[i]);//将待排列的数列录入数组中。 
    	}
    	quck(num,0,n-1);
    	for(i=0;i<n;i++){
    		printf("%d ",num[i]);
    	}
    }
    

    4.插入排序

    插入排序的基本思想:将一个数放在在一个有序数列里的正确位置中。

    思考:开始看到它的基本思想是时,我心想难不成要拿一个数组存储有序数列,从另一个数组中拿数往里面放?实际上并不用这么麻烦,用我们在快速排序里讲到的挖空填数法便可以很好的解决这个问题了。
    代码实现:

    
      1 #include<stdio.h>
      2 int main ()
      3 {
      4         int a[82];
      5         int n,i,j,temp;
      6         scanf("%d",&n);
      7         for(i=0;i<n;i++){
      8                 scanf("%d",&a[i]);
      9         }
     10         for(i=1;i<n;i++){//这里假设第一个数已经有序,从第二个开始。
     11                 temp=a[i];//将要找位置的数对应的值保存起来。
     12                 j=i-1;//从该数以左分别与其比较。
     13                 while(j>=0&&a[j]>temp){
     14                         a[j+1]=a[j];//当其后的数比它大时,其后的数前移。
     15                         j--;//继续向后继续判断。
     16                 }
     17                 a[j+1]=temp;//此时其后的数比其小则在该位置讲保存的值放下。
     18         }
     19         for(i=0;i<n;i++){
     20                 printf("%d ",a[i]);
     21         }
     22 }
    

    代码讲解:这里我们假设第一个数即为有序数列,我们从第二个数开始给它找位置(我们用一个temp暂存它的值),我们从第二个数以后依次与其进行比较,倘若其后的数比其大,则其后的数向前移动,继续向后进行比较;倘若其后的数比其小,则证明以找到合适的位置,则将该值(temp)放在比它小的前一个数即可。然后开始找第三个数,以此类推。直到找到数列最后一个数的正确位置,则证明数列以有序。

    5. 希尔排序

    希尔排序实际上是插入排序的升级版,所以熟练掌握了插入排序那么希尔排序也是非常简单的。

    算法基本思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    思考:首先我们可以把每次的增量设置为n/2(下一次设为n/4,再下一次设为n/8…直到增量为1)(n为数列的总数)假设数列共有8位,那么第一次增量便为4,则整个数列被分为四组其中(0,4)(1,5)(2,6)(3,7)各为一组,然后在每一组中进行插入排序;接下来增量变为2,则整个数列被分为2组其中(0,2,4,6,)(1,3,5,7)各为一组,再在每一组中进行插入排序;接下来增量变为1,则整个数列为1组,对这一组进行插入排序后整个数列就变有序了,自此希尔排序便结束了。(提示:希尔排序在进行时并不是分别对每一组进行插入排序,而是各组交叉进行,这一点在代码中可以很容易看出)

    补充:看到这里可能有的读者会想希尔排序这么麻烦才把数列变的有序,那我为什么不直接用插入排序呢?事实上是应为直接插入排序的优势是:插入排序在对比较短小的数列或几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;但其缺点在于:面对比较混乱的数列时,它的效率会非常低,实际上插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。所以才有了希尔排序,将一个数列分为不同的组,在这些组内的数列一般都比较短可以提高插入排序的效率,并且在增量等于1时经过前几轮的排序数列以变的基本有序了,这样也可以提高插入排序的效率。所以说希尔排序是插入排序的升级版。

    代码展示:

    #include<string.h>
    void fun(int a[82],int i,int j,int n)//按增量分组进行的插入排序函数
    {
            int m;
            int z=a[j];
            for(m=j-i;m>=0&&a[m]>z;m=m-i) a[m+i]=a[m];
            a[m+i]=z;
    }
    int main()
    {
            int n;
            int a[82];
            scanf("%d",&n);
            for(int i=0;i<n;i++) scanf("%d",&a[i]);
            for(int i=n/2;i>0;i=i/2){//控制每次分组的增量,当i=1时即可完成排序
                    for(int j=0;j<n;j++){//从这里就可以看出,在插入排序时是对各组分别进行的
                            fun(a,i,j,n);
                    }
            }
            for(int i=0;i<n;i++) printf("%d ",a[i]);
    }
    

    题外话:从直接插入排序和希尔排序两个算法中我们便可以看出事实上算法其实也是有优劣之分的,而一个算法的优劣是如何判断的呢?一般情况下我们从以下几个角度判断:
    1.时间复杂度。2.空间复杂度。3.正确性。4.稳定性(也叫容错性)。5.算法思路是否简单(也可以叫做可读性)。
    (这一块的知识就不详细阐明了,之后我也会单独写篇博客来详细说明)

    6.桶排序

    桶排序是我个人认为最简单粗暴的一种排序方法,也是比较容易实现的一种排序算法。

    算法基本思想:在一个数列中必有其最大值和最小值,而我们可以拿俩值差(max-min)个空盒子,那么这些盒子会将每一个数都覆盖,然后我们给这些盒子按照从min到max的顺序标上号,最后我们遍历数列,遍历到的数其对应的盒子都放上一个小球。那么每一个数都有了其对应的位置,然后我们按照盒子的标号顺序及其中小球的数量将其代表的数输出即可得到有序数列。(其中标号代表数字大小,小球个数代表该数字有多少)

    思考:我们可以拿出一个很大的数组(事实上如果读者学习了动态内存申的请,那么就可以申请数列最大值长度的数组了)让每一个数组值都是0(代表数组小标数字的个数为0个),将数列中的每一个数都放在对应的位置上(例:数字8,则我们给arr[8]++)代表数字8有一个。将数列里的所有数都遍历完后,我们只需从小到大依次输出数组的下标及其数组值对应的含义即可。(数组下标代表数字的大小,数组值代表了该数字的多少)

    代码展示:

    #include<stdio.h>
    int a[100000]={0};//一个用来储存数列,一个用来当盒子
    int b[100000]={0};
    int main ()
    {
            int n,i;
            scanf("%d",&n);
            for(i=0;i<n;i++) scanf("%d",&a[i]);
            for(i=0;i<n;i++){
                    b[a[i]]++;//给每个数列的值找对应的盒子
            }
            for(i=0;i<100000;i++){
                    if(b[i]!=0){
                            while(b[i]--){//按照对应含义输出即可
                                    printf("%d ",i);
                            }
                    }
            }
    }
    

    7.基数排序

    基数排序的原理类似与桶排序,但并没有桶排序那么简单粗暴。

    算法基本思想:排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。

    步骤详解:先定义一个二维数组用来暂存数据,其次在无序的数列之中找到最大值,并判断它是几位数,以此来确定循环次数。第一次循环先对个位进行分配,把每个数按照个位对应的数依序存放在二维数组中,然后是收集,把二维数组中的数据按照个位数由小到大的顺序依序依次重新赋值给数列。第二次循环再对十位数重复上述操作 …直到把每一位都“分配”和“收集”过后(也就是达到了循环次数时)原先数列就变为有序数列了。

    举例说明:数列:58 89 1 56 895 32 5 647
    首先该数列中最大值为895为三位数,所以循环三次。
    第一次循环:
    分配
    0:
    1: 1
    2: 32
    3:
    4:
    5: 895 , 5
    6: 56
    7: 647
    8: 58
    9: 89
    收集:1 32 895 5 56 647 58 89(收集后的数列)
    第二次循环:
    分配
    0: 1 , 5
    1:
    2:
    3: 32
    4: 647
    5: 56 , 58
    6:
    7:
    8: 89
    9: 895
    收集: 1 5 32 647 56 58 89 895(收集后的数列)
    第三次循环:
    分配
    0: 1 , 5 , 32 , 56 , 58 , 59
    1:
    2:
    3:
    4:
    5:
    6: 647
    7:
    8: 895
    9:
    收集:1 5 32 56 58 59 647 895(收集后的数列)
    自此三次循环都结束了最后一次得到的数列也变为了有序数列。

    代码展示:

      1 #include<stdio.h>
      2 int fun(int a,int b)//笔者在这里自己写了一个计算a的b次的函数,功能类似于pow函数
      3 {   
      4     int sum=1;
      5     for(int i=0;i<b;i++){
      6         sum=sum*a;
      7     }
      8     return sum;
      9 }
     10 int main ()
     11 {   
     12     int a[82];
     13     int b[10][82]={0};//用二维数组来暂存数据
     14     int n,sum=0,m=0;
     15     scanf("%d",&n);
     16     for(int i=0;i<n;i++){//找到数列中的最大值
     17         scanf("%d",&a[i]);
     18         if(i==0) sum=a[i];
     19         if(a[i]>sum) sum=a[i];
     20     }
     21     while(sum>0){//按照最大值位数控制循环次数
     22         for(int i=0;i<n;i++){
     23             for(int k=0;k<n;k++){
     24                 if(b[(a[i]/fun(10,m))%10][k]==0){
     25                     b[(a[i]/fun(10,m))%10][k]=a[i];//将数据按照对应关系分配到二维数组中
     26                     break;
     27                 }
     28             }
     29         }
     30         int i=0;
     31         for(int q=0;q<10;q++){
     32             for(int j=0;j<82;j++){
     33                 if(b[q][j]!=0){
     34                     a[i]=b[q][j];//收集二维数组中的数据,获得收集后的数列
     35                     i++;
     36                 }
     37             }
     38         }
     39         sum=sum/10;//与while中的条件一同控制循环次数
     40         m++;
     41         for(i=0;i<10;i++){
     42             for(int j=0;j<82;j++){
     43                 b[i][j]=0;//将二维数组清零,以便下一次存放数据
     44             }
     45         }
     46     }
     47     for(int i=0;i<n;i++){
     48         printf("%d ",a[i]);
     49     }
     50     printf("\n");
     51 }
    

    8.归并排序

    归并排序采用的主要方法是我们在快速排序中讲的分治法,所以理解好了快速排序,实际上归并排序也并不难理解。

    算法思想:归并排序主要分两个步骤=归+并。
    一个无序数列我们可以将它分为两个部分,其次设法将这两个部分变为有序,然后把这两个有序部分归为一个数列即可。
    那么问题来了,我们怎样将两个部分的无序数列变为有序呢?
    事实上我们可以把这两个部分继续分下去,直到每个部分都只剩一个元素的时候,那么每个部分也就默认有序了(分的过程其实就是归)。所以从这里我们可以看出归并的主要问题就落在了如何把两个有序数列合并为一个有序数列。(这个过程就是并)

    并:
    我们可以另外开辟一个数组来暂存数据。由于两个数列都已经有序,我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了,输的一方为小值,将这个值放入临时数组,然后输的一方继续拿出一个值来PK,直至有一方没有元素后,将另一方的所有元素依次接在临时数组后面即可。

    代码展示:

      3 int b[82];//暂时存储数据的数组
      4 int a[82];
      5 void fun(int low,int mid,int high)//一个有序数列在数组中的位置在low到mid;另一个在mid+1到high
      6 {
      7     int i=low,j=mid+1,k=low;
      8     while(i<=mid&&j<=high){//两个数列轮番pk
      9         if(a[i]<a[j]){
     10             b[k++]=a[i++];
     11         }else {
     12             b[k++]=a[j++];
     13         }
     14     }
     15     while(i<=mid){//将赢的数列的剩下的部分依次接在临时数组中
     16         b[k++]=a[i++];
     17     }
     18     while(j<=high){
     19         b[k++]=a[j++];
     20     }
     21     for(i=low;i<=high;i++){//把整合好的数列放会原来的数列中
     22         a[i]=b[i];
     23     }
     24 }
    

    归:
    归的方法实质上就是二分法,我们在快速排序中已经讲过了,这里就不再赘述了。直接上代码。

    代码展示:

     25 void mergesort(int n,int m)
     26 {
     27     if(n<m){
     28         int mid=(n+m)/2;
     29         mergesort(n,mid);
     30         mergesort(mid+1,m);
     31         fun(n,mid,m);
     32     }
     33 }
    

    自此归并排序就已经写完了,接下来我们就来看看完整代码吧。

    代码展示:

      1 #include<stdio.h>
      2 #include<string.h>
      3 int b[82];//暂时存储数据的数组
      4 int a[82];
      5 void fun(int low,int mid,int high)//一个有序数列在数组中的位置在low到mid;另一个在mid+1到high
      6 {
      7     int i=low,j=mid+1,k=low;
      8     while(i<=mid&&j<=high){//两个数列轮番pk
      9         if(a[i]<a[j]){
     10             b[k++]=a[i++];
     11         }else {
     12             b[k++]=a[j++];
     13         }
     14     }
     15     while(i<=mid){//将赢的数列的剩下的部分依次接在临时数组中
     16         b[k++]=a[i++];
     17     }
     18     while(j<=high){
     19         b[k++]=a[j++];
     20     }
     21     for(i=low;i<=high;i++){//把整合好的数列放会原来的数列中
     22         a[i]=b[i];
     23     }
     24 }
     25 void mergesort(int n,int m)//二分法函数
     26 {
     27     if(n<m){
     28         int mid=(n+m)/2;
     29         mergesort(n,mid);
     30         mergesort(mid+1,m);
     31         fun(n,mid,m);//直接调用并的函数
     32     }
     33 }
     34 int main ()
     35 {
     36     int n;
     37     scanf("%d",&n);
     38     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
     39     mergesort(1,n);
     40     for(int i=1;i<=n;i++) printf("%d ",a[i]);
     41     printf("\n");
     42 }
    
    更多相关内容
  • 用蛮力法实现选择排序,冒泡排序程序;用减治法实现插入排序;分治法应用-快排,合并排序,0-1背包问题;Prim算法求最小生成树。伪代码以及java代码实现
  • 分治算法,顾名思义就是“分而治之”,即把规模较大的...五大常用算法之分治算法分治算法的通俗理解一般来说,规模小的问题比规模大的问题解决起来简单,例如数组排序问题,只有 2 个元素的数组处理起来要比有 2000 ...

    分治算法,顾名思义就是“分而治之”,即把规模较大的复杂问题拆分为若干规模较小的类似子问题,并逐个解决,最后再将各个子问题的解决结果合并,得到原始问题的结果的方法。这个技巧是很多高效算法的基础,例如快速排序算法、归并排序算法、快速傅里叶变换等等。

    19603280908ba937dc3260461dedb5e6.png五大常用算法之分治算法

    分治算法的通俗理解

    一般来说,规模小的问题比规模大的问题解决起来简单,例如数组排序问题,只有 2 个元素的数组处理起来要比有 2000 个元素的数组简单。这是分治算法的基本立足点,也是使用条件之一,总结一下就是,对于一个规模较大的问题,可以拆分成若干不相关的子问题,并且子问题解决起来更加简单。

    分治算法在我们日常生活中无处不在,例如国家依次划分为省市县镇村来管理,本质上也是因为解决“子问题”(管理村)要简单许多。

    有这样一个非常经典的问题:生产线生产了 99 个工件,其中 1 个工件是劣品,比其他 98 个工件质量轻一些,如果用天平称,至少多少次一定能找到这个劣品工件?

    要解决这个问题,最简单粗暴的方法是逐个比较,如果第 x 个工件比第 y 个工件轻,第 x 个工件就是劣品。那么 99 个工件至少需要比较 50 次才能确保一定找到劣品。

    9421a8751a7e51950a51a52eb6c669b0.png逐个比较

    能够发现,使用逐个比较的方法的时间开销与工件总数有关,如果工件总数很少,比如只有 2 个,那么只需要比较一次就可以找到劣品了。因此该问题满足使用“分治算法”的必要条件之一:规模较小的子问题解决起来更简单。现在尝试使用分治算法解决该问题:

    将 99 个工件等分为 3 份,每份 33 个工件;比较第 1、2 份,如果天平平衡,那么劣品必定在第 3 份中,否则劣品在轻的那一份中;将劣品所在的那一份再等分为 3 份,每份 11 个工件;重复第 2 步;将劣品所在那一份再分为 3 份,每份分别为 3、3、2 个工件;重复第 2 步;不管劣品所在那一份为 3 个工件还是 2 个工件,只需再比较一次,就可找到劣品。可见,使用分治算法只需要比较 4 次就可以找到劣品,这远低于逐个比较法的 50 次。不过也应该注意到,使用分治法找劣品时,每次拆分子问题时,各个子问题是互不干扰的——例如其中一份的 33 个工件质量不会影响其他份的 33 个工件质量。

    归并排序法

    从前面这个简单的实例可以看出,分治法有时的确能够极大的提升解决问题的效率,事实上,在C语言程序开发中,许多优秀的算法本质上都是基于分治思想的,一个非常典型的例子就是归并排序法,它在处理数组排序时有着不错的效率。

    在处理数组排序时,如果数组中只有 1 个元素,那么该数组本身就可看作是排好序的数组。如果数组中有 2 个元素,那么最多只需比较一次就可以得到排好序的数组。这其实是归并排序法的核心,也即规模越小的数组,对其排序越简单。下图是一个长度为 5 的数组,为了排序,先把它拆分到不能继续拆为止。

    875d1ecff18181d60131ee69e323210c.png拆分到不能继续拆

    显然,“拆分到不能继续拆”后,子问题已经变成了只有 1 个元素的数组,这样的数组已经是“排好序”的数组了。按照我们前面讨论的,现在需要做的就是把这些已经排好序的子数组合并,问题转化为:按照顺序合并有序数组,如下图所示:

    0d40e4bd6c0f464646a183ab46aca3e4.png按照顺序合并有序数组

    归并排序的C语言实现

    根据前面的分析,使用C语言实现归并排序法需要实现两个子模块:拆分和合并。拆分数组有多种方法,通常采用二等分法,设数组头的索引为 start,数组尾的索引为 end,mid=(start+end)/2,每次平均拆分,都会将数组分为 start 到 mid,和 mid+1 到 end 两个子数组,再对这两个子数组执行同样的拆分,一直到不能拆分为止。所谓“不能拆分”,其实就是数组中只有一个元素,也即 start 等于 end,这一过程非常适合使用递归实现。我们先确定递归的停止条件:

    void divide(int *arr, int start, int end){

    if (start >= end)

    return;

    }

    否则,我们将继续拆分子数组(start, mid)和(mid+1, end),这一过程的C语言代码如下:

    void divide(int *arr, int start, int end){

    if (start >= end)

    return;

    int mid = (start+end)/2;

    divide(arr, start, mid);

    divide(arr, mid+1, end);

    }

    关于 divide() 递归函数的理解,我之前的这篇文章详细讨论过。

    搞定拆分模块后,再来看看合并模块。按照前面讨论的,拆分到“不能拆为止”的都可认为是已经排好序的子数组,所以合并模块要按照顺序(本例从小到大)将子数组合并:

    dd296b4437e6b4de5a7960697191d810.pngC语言代码1

    我们先将要合并的拆分后的两个子数组分别保存在 left 和 right 数组里,应注意,这里使用了C语言的变长数组语法,因此在编译时要指定-std=c99选项。接着,我们逐个比较 left 和 right 中的元素,按照顺序填入 arr,这一过程的C语言代码如下所示:

    8726a826811770a5aa86774785597043.pngC语言代码2

    执行完毕后,left 和 right 中可能还有剩余元素,这些剩余元素必定是需要放在 arr 后部分的,因此C语言代码可以如下写:

    61add4f43c7a152ef3811410ac49da95.pngC语言代码3

    到这里,merge() 函数就完成了,将之与 divide() 函数组合起来,也即:

    f94cb37b96db9c96efcefba912c345d5.pngC语言代码4

    现在 divide() 函数便可对输入的数组 arr 排序了。

    测试归并排序法

    这里使用 8 个元素的数组做测试:

    9e6e0f17ea5b8cb4947201a84a8c62db.pngC语言代码5

    编译并执行这段C语言代码,得到如下输出:

    # gcc t.c -std=c99

    # ./a.out

    1 2 3 4 5 6 7 8

    归并排序算法的时间复杂度

    在计算过程中,累加和比较的过程是关键操作,一个长度为 n 的数组在递归的每一层都会进行 n 次操作,分治法的递归层级在 logN 级别,所以整体的时间复杂度是 O(nlogn)。

    归并排序法是一个效率不错的排序算法,可能时间复杂度看起来不是特别直观,我们将之与简单粗暴的“冒泡排序算法”对比,在我的机器上分别对不同规模的数组排序,得到如下结果:

    2eaccf724ce6b6485d87ed7000d054d7.png排序效率对比

    冒泡排序算法是比较简单的算法,在处理规模较小的数组时和归并排序法的效率不相上下,但是在处理规模较大的数组时,冒泡排序算法的效率逐渐远离归并排序了,且数组的规模越大,二者的效率差异越大,在处理 100 万个数组元素时,归并排序算法仅消耗 230 毫秒就处理完毕了,而冒泡排序算法在执行 2 分钟后仍然还没有完成,我没有耐心等下去,提前结束它了。

    小结

    分治法是解决问题的优秀思想,不仅在现实生活中,在程序开发中更是如此,本文主要通过归并算法实例讨论了这一点。不过应该注意,使用分治法解决问题时,问题应该满足以下条件:

    问题可以拆分为若干类似的彼此不干扰的子问题问题规模缩小时,更容易解决子问题的解可以合并为原始问题的解显然,这些条件是容易理解的。

    d46514e0447acaf025ba6a72bf08c9f5.png点个关注

    欢迎在评论区一起讨论,质疑。文章都是手打原创,每天最浅显的介绍C语言、linux等嵌入式开发,喜欢我的文章就关注一波吧,可以看到最新更新和之前的文章哦。

    未经许可,禁止转载。

    举报/反馈

    展开全文
  • 冒泡排序 基本思想 对有n个记录的序列进行冒泡排序,首先将第一个数字与第二个数字进行比较,若为逆序,则将两个数字的顺序交换。然后比较第二个数字与第三个数字,若为逆序,则将两个数字的顺序交换…依此类推,...

    冒泡排序

    基本思想

    对有n个记录的序列进行冒泡排序,首先将第一个数字与第二个数字进行比较,若为逆序,则将两个数字的顺序交换。然后比较第二个数字与第三个数字,若为逆序,则将两个数字的顺序交换…依此类推,经过第一轮排序后,最大的数字将“下沉”到最后,每趟的比较次数依次减少。经过n-1轮排序,将得到一个递增的序列。

    在这里插入图片描述

    空间复杂度:O(1)

    时间复杂度:O(n^2)

    稳定性:稳定

    代码实现

    n个记录总共要进行n-1趟排序,第i趟的比较次数为n-i次。可以使用双层循环,外层循环控制第几轮排序,内层控制每一轮比较的次数。

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100
    void Input(); //输入数组
    void Output(); //输出数组
    void BubbleSort(); //冒泡排序
    
    int arr[MAXSIZE];
    int count = 0;
    
    //冒泡排序
    void BubbleSort(){
        int i ,j ,temp;
        for ( i = 0; i < count-1; i++)
        {
            for ( j = 0; j < count-i-1; j++)
            {
                if (arr[j] > arr[j+1])
                {
                   temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
                }
            }
        }
    }
    //输入函数
    void Input(){
        int x,i;
        char s;
        printf("please input less than 100 numbers, end with enter:\n");
        for (i = 0; s != '\n'; i++)
        {
            scanf("%d",&arr[i]);
            s = getchar();
            count++;
        }
    }
    
    //输出函数
    void Output(){
        printf("sorted numbers:\n");
        for (int i = 0; i < count; i++){
            printf("%d\t",arr[i]);
        }
        printf("\n");
    }
    
    int main(){
        Input();
        BubbleSort();
        Output();
        system("pause");
        return 0;
    }
    

    运行结果:
    在这里插入图片描述

    快速排序

    基本思想

    快速排序是从冒泡排序改进而得的一种“交换”排序方法。采用的是一种分治的策略。

    1. 先从数列中取出一个数作为基准数(称为枢轴)。

    2. 将比基准数大的数全放到它的右边,小于或等于基准数的全放到它的左边。

    3. 再对左右两部分重复第(2)步,直到各区间只有一个数,达到整个序列有序。

    在这里插入图片描述

    空间复杂度:最好:O(n lb n),最坏:O(n)

    时间复杂度:平均:O(n lb n),最坏:O(n^2)

    稳定性:不稳定

    代码实现

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 100
    void Input(); //输入数组
    void Output(); //输出数组
    int Partition(int low ,int high);//一趟快速排序排
    void QuikSort(int s, int e); //快速排序
    
    int arr[MAXSIZE];
    int count = 0;
    //一趟快排
    //定义一个high,low,key(记录枢轴的值)
    //最后将枢轴移到正确位置,返回枢轴的位置
    int Partition(int low ,int high){
        arr[0] = arr[low]; //arr[0]记录枢轴,待排序列从arr[1]开始
        while (low < high)
        {
           while(low < high&&arr[high] >= arr[0])
                --high;
            arr[low] = arr[high];
           while (low < high&&arr[low] <= arr[0])
                ++low;
            arr[high] = arr[low];
        }
        arr[low] = arr[0];
        return low;  //返回枢轴的位置
    }
    //快排(递归调用)
    void QuikSort(int s,int e){
        if (s < e) //s与e是待排序区域的上下界
        {
            int keyPosition = Partition(s,e); //对待排序列进行一次划分,并返回枢轴位置
            QuikSort(s,keyPosition-1);        //对左侧子序列递归排序
            QuikSort(keyPosition+1,e);        //对右侧子序列递归排序
        }
        
    }
    //输入函数
    void Input(){
        int x,i;
        char s;
        printf("please input less than 100 numbers, end with enter:\n");
        for (i = 1; s != '\n'; i++)
        {
            scanf("%d",&arr[i]);
            s = getchar();
            count++;
        }
    }
    
    //输出函数
    void Output(){
        printf("sorted numbers:\n");
        for (int i = 1; i <= count; i++){
            printf("%d\t",arr[i]);
        }
        printf("\n");
    }
    
    int main(){
        Input();
        QuikSort(1,count);
        Output();
        system("pause");
        return 0;
    }
    

    运行结果:

    在这里插入图片描述

    展开全文
  • #C语言七大排序算法之分治 在上个星期,我看完了七大排序算法(其实是看完了除选择、冒泡、插入排序之外的四种) 而在这篇文章中,我会把快速和归并算法通过自己的理解描述出来。 快速排序算法 归并排序算法 快速...

    #C语言七大排序算法之分治之快速排序
    在上个星期,我看完了七大排序算法(其实是看完了除选择、冒泡、插入排序之外的四种)
    而在这篇文章中,我会把快速排序算法通过自己的理解描述出来。
    ##分治
    首先要学习快速排序算法,那我们就得先来理解一下什么是分治?
    所谓分治,就是将问题分解成一个个子问题,将子问题再分解,分解到很简单的问题为止。用到递归了哦。
    既然说完分治后,那我们就进入正题。
    快速算法:
    Q:为什么要用快速算法呢?
    A:因为它快啊(手动滑稽)。其实在排序比较大的数组时,其他五大算法排序所需的时间是比较长的,而快速算法的可以很快的排序出来,但是快速排序不稳定
    快速排序算法到底有多快呢(来看这张表吧)排序算法时间复杂度分析表
    我们来说快速排序实现的原理:
    假如我们有一个乱序数组,其中有n个数
    乱序数组
    以数组的第0个为标志temp(a[0]=5),先和第n-1个比较(我用语句来形容我说的(但不是最终代码的形式))
    第一次换位

    	int j=n-1;
    	while(temp<a[j])
    		j--;
    

    从a[n-1]=9往左走,遇到比5小的数时,便交换它们,便会得到
    第一次换位
    第一次完成。
    第二次换位

    int i=0;
    while(temp<a[i])
    	i++;
    

    从a[i]往右走,遇到比5大的数时,便交换它们,得到以下数组
    第二次换位
    第三次换位再从a[j]开始往左走,和第一次一样。
    第四次换位从a[i]开始往右走,和第二次一样。
    最后会得到以下数组
    在这里插入图片描述
    当i=j时,这一波换位结束。
    递归思想,将数组分成两半
    在这里插入图片描述
    再次进行和上一波换位的操作,完成后再分,直到i=j时,便return。

    #include <iostream>
    using namespace std;
    void quicksort(int a[],int s,int e){
    	if(s>=e)
    		return;
    	int i=s,j=e;
    	int temp=a[s];		//标志temp 
    	while(i!=j){		//换位 
    		while(j>i&&a[j]>=temp)
    			--j;
    		int t=a[i];
    		a[i]=a[j];
    		a[j]=t;
    		while(j>i&&a[i]<=temp)
    			++i;
    		t=a[i];
    		a[i]=a[j];
    		a[j]=t;
    		}
    		quicksort(a,s,i-1); //递归 
    		quicksort(a,i+1,e);
    }
    int main(){
    	int a[]={5,2,4,1,8,6,3,0,7,9};
    	int n=sizeof(a)/sizeof(int);
    	int b[n];
    	quicksort(a,0,n-1);		//n-1
    	for(int i=0;i<n;i++)
    		printf("%d ",a[i]);
    	return 0;
    }
    

    完成快速排序。
    关于快速排序的稳定性,如果遇到有顺序的数组时,如
    在这里插入图片描述
    分析时间复杂度,即为O(n²)。那就没实现快速排序的目的了
    Q:如何解决这个问题?
    A:打乱这个有序数组,即可实现O(nlogn)。
    在这里插入图片描述
    章外话:第一次发帖,如有错误,望大家指正。

    展开全文
  • 这次实现的是蛮力中的两个例子,选择排序冒泡排序法,使用的编译环境是vs2013,下面对这两个算法做一个简单介绍,然后是两个算法的c++实现代码。选择排序比较的范围是整个列表,每次扫描结束找出最小的一个...
  • 文章目录一、冒泡排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现二、快速排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现三、希尔排序1.简单介绍2.算法原理3.图形实例4.C语言代码实现四、归并排序1.简单...
  • 1.冒泡排序 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 算法步骤 比较相邻的...
  • 将一个大的集合分成无数的小的集合,符合了『 分治法 』中将一个大的问题分成小问题来解决的思想,而对两个元素进行排序,再将各个小的有序集合合并成一个大的有序集合这个过程就是『 治 』。==算法不仅仅是...
  • 目录一、冒泡排序二、快速排序三、小结一、冒泡排序冒泡排序是各种教材中 经常提到的一种排序 方法,基本思想就是:① 从数组的头部开始,比较相邻两个数,如果第1个数比第2个数大,就交换他们两个。也就是让较大的...
  • 1.冒泡排序基本思想:比较相邻的两个数,如果前者比后者大,则进行交换。每一轮排序结束,选出一个未排序中最大的数放到数组后面。#include//冒泡排序算法voidbubbleSort(int*arr,int n) {for(inti =0; ifor(intj...
  • 快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟 扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次 扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只 减少1。快速...
  • 分治法 | 快速排序,归并排序 | 原理及代码实现
  • 分治法解题的一般步骤:(1)分解,将要解决的问题划分成若干规模较小的同类问题;(2)求解,当子问题划分得足够小时,用较简单的方法解决;(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。一言以蔽之...
  • c语言排序算法的分析和总结C语言中三种常见排序算法分析 一、冒泡法 算法要求:用起泡对10个整数按升序排序。 算法分析:如果有n个数,则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较,在第j...
  • C语言-交换排序(Swap Sort)

    千次阅读 2020-08-11 22:43:02
    1.冒泡排序(Bubble Sort): void BubbleSort(int *r) { int i,j; for(i=0;i<Maxsize;i++) for(j=1;j<Maxsize-i;j++) if(r[j-1]>r[j]) Swap(r[j-1],r[j]); } 2.升级版冒泡排序: ...
  • //调用冒泡排序 } //左右各距中线d的区域的最近对算法 void middle(const List & L, CloseNode &cnode, int mid, double midX) { int i, j; //分别表示中线左边,右边的点 double d = sqrt(cnode.space); i = mid; ...
  • 排序C语言实现)

    2021-12-10 21:22:18
    C语言实现几个重要的排序
  • 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首...冒泡排序算法的C语言实现代码如下: #include <stdio.h
  • C语言排序排序的目的桶排序概念思路 排序的目的 排序: 把无序变成有序 桶排序 概念 桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再...
  • 八大排序算法(C语言实现)

    万次阅读 多人点赞 2021-05-09 13:50:26
    文章目录插入排序插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序并归排序并归排序 插入排序 插入排序 希尔排序 选择排序 选择排序 堆排序 交换排序 冒泡排序 快速排序 并归排序 并归排序 ...
  • 冒泡排序 O(n2) O(n2) O(1) 稳定 选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定 插入排序 O(n2) O(n2) O(1) 稳定 快速排序 O(n*log2n) O(n2) O(log2n) 不稳定 堆排序 O(n*log2n) O(n
  • 直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。 算法复杂度比较: 算法分类 一、直接插入排序 一个插入排序是另一种简单排序,它的思路是:每次从未排好的序列中选出第一...
  • 1. 冒泡排序 算法思想: 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 3. 针对所有的...
  • 【C】分治算法

    千次阅读 2015-10-20 20:27:50
    比如在有序顺序表中的二分查找就是分治法的其中一个实例。它的时间复杂度经常性能把一个问题从O(n)降为O(nlogn),虽然它的代码往往涉及到递归调用,看起来非常复杂。 比如以下的一个简单得不能再简单的问题,求数组...
  • 什么是排序?...2、冒泡排序 动图演示 概念 思路 demo 运行效果 3、选择排序 动图演示 概念 思路 demo 运行结果 4、插入排序 动图演示 概念 思路 demo 运行效果 5、快速排序 动图演示 概念 思路 demo 运行结果
  • 通过分治法和分区(partition)可以只将k所在范围内的值进行查找即可。当然可以使用二分法去确立k的范围,但是我的课本上没有所以我们今天不讨论。下面介绍两种算法:随机选择和中位数选择。随机选择随机选择是在...
  • 这里写目录标题冒泡排序归并排序 原理部分:十大经典排序算法(动图演示) 冒泡排序 归并排序 1、递归方法
  • 通过分治法和分区(partition)可以只将k所在范围内的值进行查找即可。当然可以使用二分法去确立k的范围,但是我的课本上没有所以我们今天不讨论。下面介绍两种算法:随机选择和中位数选择。随机选择随机选择是在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,576
精华内容 630
关键字:

分治法 冒泡排序c语言