【c语言】冒泡排序和选择排序

傷城~ 2022-04-12 11:47 372阅读 0赞

## **1.冒泡排序** ##

冒泡排序将一个列表中的两个元素进行比较，并将最小的元素交换到顶部。两个元素中较小的会冒到顶部，而较大的会沉到底部，该过程将被重复执行，直到所有元素都被排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70][]

冒泡排序示意图

以如图所示的冒泡排序为例，每次比较相邻的两个值，值小的交换到前面，每轮结束后值最大的数交换到了最后。第一轮需要比较4次；第二轮需要比较3次；第三轮需要比较2次；第四轮需要比较1次。

那么如何用二重循环将5个数排序呢？5个数存放在一维数组中，外层循环控制比较多少轮，循环变量i;内层控制每轮比较多少次，循环变量就，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70 1][]

代码如下：

#include <stdio.h>
    #define NUM 5
    void arrsort(int[],int);
    void arrout(int[],int);
     main(){
    	 int a[NUM]={16,25,9,90,23};
    	 arrout(a,NUM);//输出a数组中原始数据
    	 arrsort(a,NUM);//对a数组中的数进行排序
         arrout(a,NUM);//输出排序后a数组中的数据
    }
    void arrsort(int a[],int n){
    	for(int i=0;i<n-1;i++){
    		for(int j=0;j<n-1-i;j++){
    			if(a[j]>a[j+1]){ 
    			  int temp =a[j+1];
    			  a[j+1] = a[j];
    			  a[j] = temp;
    			}
    		}
    	}
    	
    }
    void arrout(int a[],int n){
       int i;
       for(i=0;i<n;i++){
        printf("%3d",a[i]);
       }
       printf("\n");
     }

输出结果为：

![20181203114752555.png][]

## **2.选择排序** ##

在介绍选择排序法之前，凭介绍一种把最小的数放在第一个位置上的算法，当然也可以用前面所讲的冒泡排序法，现在我们改用一种新的算法: 其指导思想是先并不急于调换位置，先从a\[0\]开始逐个检查，看哪个数最小，就记下该数所在的位置p,等一躺扫描完毕，再把a\[p\]和a\[0\]对调，这时a\[0\] a\[9\]最小的数据就换到了最前面的位置。算法的步骤如下。  
(1)先假设a\[0\]的数最小，记下此时的位置p。  
(2)依次把a\[p\]和a\[i\]（从2变化到9)进行比较，每次比较时，若a\[j\]的数比a\[p\]中的数小，则把i的值赋给p,使p总是指向当前所扫描过的最小数的位置，也就是说a\[p\]总是等于所有扫描过的数中最小的那个数。在依次一一比较后，p就指向 10个数中 最小的数所在位置，即a\[p\]就是10 个数中最小的那个数。  
(3)把a\[p\]和a\[0\]的数对调，那么最小的数就在a\[0\]中了，也就是在最前面了。

如果现在重复此算法，但每重复一次， 进行比较的数列范围就向后移动一个位置，即第二遍比较时范围就从第2个数一直到第 n个数，在此范围内找最小的数的位置p,然后把a\[p\]与a\[2\]对调，这样从第2个数开始到第n个数中，最小数就在a\[2\]中了，第三遍就从第个数到第n 个数中去找最小的数，再把a\[p\]与a\[3\]对调..此过程重复n-1次后，就把a组中n个数按从小到大的顺序排好了。这种排序的方法就是选择排序法。

下面我们定义一个临时变量temp代替a\[p\],进行排序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70 2][]

选择排序修改为：从键盘输入的十个整数按升序排列输出

#include <stdio.h>
    void main(){
      int i,j,k;
      int a[10];
      for(k=0;k<10;k++){
         scanf("%d",&a[k]);
      }
      for(i=0;i<9;i++){
    	  for(j=i+1;j<10;j++){
    		 
    		  if(a[i]>a[j]){ 
    		   int temp = a[j];
    		   a[j] = a[i];
    	        a[i] = temp;
    		  }
    	  }
    	  
    
      }
      for(i=0;i<10;i++){
        printf("%d ",a[i]);
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70]: /images/20220412/6ac6463088fd41dfac6e01e3991f43cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70 1]: /images/20220412/ca857f6144204adfae56113e1e28fb15.png
[20181203114752555.png]: /images/20220412/67aece5134a94e5da7baebfaaa5b3c85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicWx6Y2g_size_16_color_FFFFFF_t_70 2]: /images/20220412/1d108324d3854d93b112e206e92742b3.png