使用C语言和Java分别实现冒泡排序和选择排序

经典排序算法——冒泡和选择排序法

Java实现冒泡排序

基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素放到顶端,最终达到完全有序,首先看个动图:

我们要清楚一点,冒泡排序是相邻元素的两两比较,再看下图是否会清晰些:

输入的数据为:10 30 40 33 5 78 11 100 23 66

第一次排序,从第一个数10依次比较,若10比后者小,则进行交换,当比较到5时,10比5大,所以10就停在第四个位置,再用5去比较,后面的数都比5大,所以5就排到最后了

同理,第二次排序,仍然从第一个数30开始比较,分别跟40,33交换了顺序,比到10的时候,30比10大,所以30就停在了第三个位置,再用10去比较,10只比5大,所以排在了倒数第二个位置

依次10次比较后,得到最终排序结果

Java实现冒泡排序代码如下,代码实现过程,用一个临时变量来做中间值,从而实现交换:

 1 package maopaopaixu;
 2 
 3 import java.util.Scanner;                        //使用到了scanner函数,所以需要导包
 4 
 5 public class maopao {
 6 
 7     public static void main(String[] args) {
 8         int i,j,k,temp;                            //声明变量    
 9         int a[]=new int[10];                    //定义一个数组,长度为10
10         Scanner sc=new Scanner(system.in);        //创建一个输入对象
11         System.out.println("请输入十个正整数:");        //输出
12         for(i=0;i<a.length;i++){                //使用for循环把数据存储到数组中
13             a[i]=sc.nextInt();
14         }
15         for(j=0;j<a.length;j++){                //外层循环控制排序趟数
16             for(k=0;k<a.length-1;k++){            //内层循环控制每一趟排序多少次
17                 if(a[k]<a[k+1]){                //取相邻两个数进行比较
18                     temp=a[k+1];                //条件为真,进行交换位置,采用temp临时变量
19                     a[k+1]=a[k];
20                     a[k]=temp;
21                 }
22             }
23         }
24         for(i=0;i<a.length;i++){                    //使用for循环,把排序的结果依次显示
25             System.out.print(a[i]+"\t");
26         }
27 
28     }
29 
30 }

加上一些代码可以看的更清晰,如下所示:

 1 package maopaopaixu;
 2 
 3 import java.util.Scanner;                        //使用到了scanner函数,所以需要导包
 4 
 5 public class maopao {
 6 
 7     public static void main(String[] args) {
 8         int i,j,k,temp;                            //声明变量    
 9         int a[]=new int[10];                    //定义一个数组,长度为10
10         Scanner sc=new Scanner(System.in);        //创建一个输入对象
11         System.out.println("请输入十个正整数:");        //输出
12         for(i=0;i<a.length;i++){                //使用for循环把数据存储到数组中
13             a[i]=sc.nextInt();
14         }
15         for(j=0;j<a.length;j++){                //外层循环控制排序趟数
16             for(k=0;k<a.length-1;k++){            //内层循环控制每一趟排序多少次
17                 if(a[k]<a[k+1]){                //取相邻两个数进行比较
18                     temp=a[k+1];                //条件为真,进行交换位置,采用temp临时变量
19                     a[k+1]=a[k];
20                     a[k]=temp;
21                 }
22             }
23             System.out.print("第"+(j+1)+"次排序为:");    //输出
24             for(i=0;i<a.length;i++){                //在外层循环中看每一次排序后的结果
25                 System.out.print(a[i]+"\t");
26             }
27             System.out.println();                    //换行
28         }
29         System.out.print("最终排序为:");                //输出
30         for(i=0;i<a.length;i++){                    //使用for循环,把排序的结果依次显示
31             System.out.print(a[i]+"\t");
32         }
33 
34     }
35 
36 }

Java实现选择排序法

基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。

在算法实现时,每一趟确定最小(或最大)元素的时候会通过不断地比较交换来使得首位置为当前最小(或最大),交换是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小(或最大)元素之前,这些交换都是无意义的。我们可以通过设置一个变量min(或max),每一次比较仅存储较小(或较大)元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小(或最大)元素的下标,此时再执行交换操作即可。

简言之,就是找到找到一组数中的最大与最小交换顺序

先看一张结果图,一看就明白:

输入的数据为:10, 35 67 88 99 100 2 34 77 55,我们可以从上图看出,进行第一次排序时,只是最大值100与最小值10交换了位置,其他数的位置都没有变化

同理,第二次就是该组数中的第二大的数99与第二小的数35交换位置,其他数位置不变

十次下来,就实现了排序功能

Java实现选择排序代码如下:

 1 package xuanzepaixu;
 2 
 3 import java.util.Scanner;                        //使用到了scanner函数,所以需要导包
 4 /*选择比较是找出最大的与第一个交换*/
 5 public class xuanze {
 6 
 7     public static void main(String[] args) {
 8         int i,j,k,temp,max,count=0;                //声明变量
 9         int a[] = new int[10];                    //定义一个数组,长度为10
10         Scanner sc=new Scanner(System.in);        //创建一个输入对象
11         System.out.println("请输入十个正整数:");        //输出
12         for(i=0;i<a.length;i++){                //使用for循环把数据存储到数组中
13             a[i]=sc.nextInt();
14         }
15         for(j=0;j<a.length;j++){                //外层循环控制排序趟数
16             max=a[j];                            //把数组中第j个值赋给max
17             count=j;                            //count记录下标,若if结果为假,则保持原样交换
18             for(k=j;k<a.length;k++){            //内层循环控制每一趟排序多少次
19                 if(max<a[k]){                    //假定的max值与数组依次去比较
20                     max=a[k];                    //为真就把a[k]的值赋给max
21                     count=k;                    //count是记录数的位置
22                 }
23             }
24             temp=a[j];                            //在外循环中对数据进行交换顺序
25             a[j]=a[count];
26             a[count]=temp;
27         }
28         for(i=0;i<a.length;i++){                    //使用for循环,把排序的结果依次显示
29             System.out.print(a[i]+"\t");
30         }
31 
32     }
33 
34 }

选择排序有个地方需要注意:就是count=j,若没有这句,当出现判断条件为假时,从而会导致整个排序出错

加上显示排序次数的代码更加清楚,如下所示:

package xuanzepaixu;

import java.util.Scanner;                        //使用到了scanner函数,所以需要导包
/*选择比较是找出最大的与第一个交换*/
public class xuanze {

    public static void main(String[] args) {
        int i,j,k,temp,max,count=0;                //声明变量
        int a[] = new int[10];                    //定义一个数组,长度为10
        Scanner sc=new Scanner(System.in);        //创建一个输入对象
        System.out.println("请输入十个正整数:");        //输出
        for(i=0;i<a.length;i++){                //使用for循环把数据存储到数组中
            a[i]=sc.nextInt();
        }
        for(j=0;j<a.length;j++){                //外层循环控制排序趟数
            max=a[j];                            //把数组中第j个值赋给max
            count=j;                            //count记录下标,若if结果为假,则保持原样交换
            for(k=j;k<a.length;k++){            //内层循环控制每一趟排序多少次
                if(max<a[k]){                    //假定的max值与数组依次去比较
                    max=a[k];                    //为真就把a[k]的值赋给max
                    count=k;                    //count是记录数的位置
                }
            }
            temp=a[j];                            //在外循环中对数据进行交换顺序
            a[j]=a[count];
            a[count]=temp;
            System.out.print("第"+(j+1)+"次排序为:");    //输出
            for(i=0;i<a.length;i++){                //在外层循环中看每一次排序后的结果
                System.out.print(a[i]+"\t");
            }
            System.out.println();                    //换行
        }
        System.out.print("最后排序为:");                //输出
        for(i=0;i<a.length;i++){                    //使用for循环,把排序的结果依次显示
            System.out.print(a[i]+"\t");
        }

    }

}

C语言实现冒泡排序

实现原理都一样,只是代码写法稍有不同罢了,所以就直接上代码了:

 1 #include<stdio.h>
 2 main()
 3 {
 4     int i,j,temp;
 5     int a[10];
 6     
 7     printf("请输入十个数:");
 8     for(i=0;i<10;i++)
 9     {
10         scanf("%d",&a[i]);
11     }
12     
13     
14     for(i=0;i<10;i++)
15     {
16         for(j=0;j<9-i;j++)
17         {
18             if(a[j]>a[j+1])
19             {
20                 temp=a[j];
21                 a[j]=a[j+1];
22                 a[j+1]=temp;
23             }
24         }
25     }
26     
27     for(i=0;i<10;i++)
28     {
29         printf("a[%d]=%d\n",i,a[i]);
30     }
31 } 

C语言实现选择排序

 1 #include<stdio.h>
 2 
 3 main()
 4 {
 5     int a[5],b,i,j,max,temp,count=0;
 6     
 7     printf("请输入五个数:");
 8     for(i=0;i<5;i++)
 9     {
10         scanf("%d",&a[i]);
11     } 
12     
13     for(i=0;i<4;i++)
14     {
15         count=i;
16         for(j=0;j<4-i;j++)
17         {
18             max=a[j];
19             if(max < a[j+1])
20             {
21                 max=a[j+1];
22                 b=j+1;
23                 temp=a[j];
24                 a[j]=a[j+1];
25                 a[j+1]=temp;
26             }
27         }
28     }
29     
30     for(i=0;i<5;i++)
31     {
32         printf("%d\n",a[i]);
33     }
34     
35     printf("最大值为:%d",max);
36 }

 

本文仅代表作者观点,系作者@温一壶清酒发表。转载请注明出处:http://www.cnblogs.com/hong-fithing/
赞 (0) 评论 分享 ()