C语言之常用几种排序

冒泡排序

假设要对含有n个数的序列进行升序排列,冒泡排序算法步骤是:

1、从存放序列的数组中的第一个元素开始到最后一个元素,依次对相邻两数进行比较,若前者大后者小,则交换两数的位置;

2、第1趟结束后,最大数就存放到数组的最后一个元素里了,然后从第一个元素开始到倒数第二个元素,依次对相邻两数进行比较,若前者大后者小,则交换两数的位置;

3、重复步骤1 n-1趟,每趟比前一趟少比较一次,即可完成所求。

例1、随机产生10个100以内的数,将其用冒泡法按升序排列后输出。

编程思路:用最后一个数与前一个数比较,若比前一个数小

则交换位置,然后再与前一个数比较,若比前一个数小再交换

位置,知道比前一个数大或者已经在最前面!如此循环8次就可以排好循序!

 1#include <stdio.h>
 2#include <stdlib.h>
 3#define n 10 
 4int main(void)
 5{    
 6     int a[n],i,j,t;
 7     printf("随机产生10个100以内的数:\n");
 8     for(i=0;i<n;i++)
 9     {
10       a[i] = rand()%100;
11       printf("%d\n",a[i]);
12     }
13     printf("输出:\n");
14      for(j=1;j<=n-1;j++)
15      {     /*n个数处理n-1趟*/
16        for(i=0;i<=n-1-j;i++)
17        {    /*每趟比前一趟少比较一次*/
18          if(a[i]>a[i+1]) 
19          { 
20            t=a[i];
21            a[i]=a[i+1];
22            a[i+1]=t; 
23          }
24        }
25     }
26    for(i=0;i<n;i++)
27    {
28        printf("%d\n",a[i]);
29    }
30    return 0 ;
31}

运行结果:

选择排序

选择法排序是相对好理解的排序算法。假设要对含有n个数的序列进行升序排列,算法步骤是:

1、从数组存放的n个数中找出最小数的下标(算法见下面的“求最值”),然后将最小数与第1个数交换位置;

2、除第1个数以外,再从其余n-1个数中找出最小数(即n个数中的次小数)的下标,将此数与第2个数交换位置;

3、重复步骤1 n-1趟,即可完成所求。

代码案例实现:

 1#include <stdio.h>
 2#include <stdlib.h>
 3#define n 10 
 4int main()
 5{ 
 6       int a[n],i,j,k,t;
 7       printf("随机产生10个100以内的数:\n");
 8     for(i=0;i<n;i++)
 9     {
10        a[i] = rand()%100;
11        printf("%d\n",a[i]);
12     }
13     printf("输出:\n");
14     for(i=0;i<n-1;i++)         /*处理n-1趟*/
15     {
16         k = i;      /*总是假设此趟处理的第一个(即全部数的第i个)数最小,k记录其下标*/
17         for(j=i+1;j<n;j++)
18         {
19             if(a[j] < a[k])
20                k = j; 
21         }
22         if (k != i)
23         { 
24             t = a[i]; 
25             a[i] = a[k]; 
26             a[k] = t; 
27         }
28     } 
29     for(i=0;i<n;i++)
30        printf("%d\n",a[i]); 
31        return 0 ;
32}

运行结果:

随机产生10个100以内的数字,排序后输出

插入排序

插入法排序的要领就是每读入一个数立即插入到最终存放的数组中,每次插入都使得该数组有序。

代码案例:

 1#include <stdio.h>
 2#include <stdlib.h>
 3#define n 10 
 4
 5int main()
 6{ 
 7  int a[n]={-1,3,6,9,13,22,27,32,49};  /*注意留一个空间给待插数*/
 8  int x,j,k;   
 9  x = rand()%100;
10  printf("随机产生x的值为:%d\n",x);
11  if(x>a[n-2]) 
12  {
13     a[n-1]=x ;    /*比最后一个数还大就往最后一个元素中存放*/
14  }
15  else          /*查找待插位置*/
16  {
17       j=0;
18       while( j<=n-2 && x>a[j])
19       { 
20             j++;            
21        }
22       for(k=n-2; k>=j; k--)
23       {    /*从最后一个数开始直到待插位置上的数依次后移一位*/
24            a[k+1]=a[k];
25       }
26               a[j]=x;      /*插入待插数*/ 
27  }
28  printf("输出:\n");
29       for(j=0;j<=n-1;j++)  
30         printf("%d  ",a[j]);
31    return 0 ;
32}

运行结果:

随机产生一个数插入到已有的数组中,排序后输出:

归并排序

即将两个都升序(或降序)排列的数据序列合并成一个仍按原序排列的序列。

代码案例:

 1#include <stdio.h>
 2#include <stdlib.h>
 3#define m 6
 4#define n 4
 5int main()
 6{ 
 7      int a[m]={-3,6,19,26,68,100} ,b[n]={8,10,12,22};
 8     int i,j,k,c[m+n];
 9     int l ;
10      i=j=k=0;
11      printf("a数组的元素:\n");
12      for(l = 0 ; l < m ; l++)
13      {
14          printf("%d  ",a[l]);    
15    }
16    printf("\nb数组的元素:\n");
17    for(l = 0 ; l < n ; l++)
18      {
19          printf("%d  ",b[l]);    
20    }
21    printf("\n合并后的数组元素:\n");
22    while(i<m && j<n)    /*将a、b数组中的较小数依次存放到c数组中*/
23    { 
24        if(a[i]<b[j]) 
25        {
26            c[k]=a[i]; 
27            i++;
28        }
29         else 
30        {
31            c[k]=b[j]; 
32            j++;
33        }
34         k++;
35     }
36    while(i>=m && j<n)   /*若a中数据全部存放完毕,将b中余下的数全部存放到c中*/
37    { 
38        c[k]=b[j]; 
39        k++; 
40        j++; 
41    }
42     while(j>=n && i<m)   /*若b中数据全部存放完毕,将a中余下的数全部存放到c中*/
43     { 
44        c[k]=a[i]; 
45        k++; 
46        i++; 
47    }
48     for(i=0;i<m+n;i++)  
49      printf("%d  ",c[i]);
50    return 0 ;
51}

运行结果:

原文发布于微信公众号 - 嵌入式开发圈(gh_d6ff851b4069)

原文发表时间:2019-05-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券