八种基本的排序（1）——冒泡排序（C语言实现）

–

八种基本的排序（1）——冒泡排序（C语言实现）

八种基本的排序（2）——直接选择排序（C语言实现）

八种基本的排序（3）——插入排序（C语言实现）

八种基本的排序（4）——归并排序（C语言实现）

八种基本的排序（5）——快速排序（C语言实现）

目录

冒泡排序（Bubble Sort）

是一种计算机科学领域的较简单的排序算法。1
它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

原理

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数$C$和记录移动次数$M$均达到最小值：$C_{min}=n-1$，$M_{min}=0$ 。
所以，冒泡排序最好的时间复杂度为 $O(n)$ 。
　　若初始文件是反序的，需要进行 趟排序。每趟排序要进行 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
$C_{max}=\frac{n(n-1)}{2}=O(n^{2})$

$M_{max}=\frac{3n(n-1)}{2}=O(n^{2})$
冒泡排序的最坏时间复杂度为$O(n^{2})$ 。
综上，因此冒泡排序总的平均时间复杂度为$O(n^{2})$ 。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

下面就是源代码了

源代码+注释

函数版

//冒泡排序，从小到大（方向可改） 。 #include 
          
          void bubble_sort(int a[], int n); //申明函数"bubble_sort"  int number[]; //在主函数外面定义数组可以更长  void bubble_sort(int a[], int n) //下面是函数bubble_sort的程序  { int i,j,temp; //定义三个整型变量  for (j=0;j 
        
          1;j++) 
         //用一个嵌套循环来遍历一遍每一对相邻元素 （所以冒泡函数慢嘛，时间复杂度高）  { 
         for (i= 
         0;i 
         
           1-j;i++) { 
          if(a[i]>a[i+ 
          1]) 
          //从大到小排就把左边的">"改为"<" ！！！ { temp=a[i]; 
          //a[i]与a[i+1](即a[i]后面那个) 交换 a[i]=a[i+ 
          1]; 
          //基本的交换原理"c=a;a=b;b=c"  a[i+ 
          1]=temp; } } } } 
          int main() 
          //主函数  { 
          int i,n; 
          printf( 
          "输入数字个数：\n"); 
          scanf( 
          "%d",&n); 
          //输入数字个数 
          printf( 
          "输入%d个数:\n",n); 
          for( 
          int j= 
          0;j 
          
            //用一个for循环来输入所有数字 
           scanf( 
           "%d",&number[j]) ; bubble_sort(number,n); 
           //引用函数bubble_sort  
           for (i= 
           0;i 
           
             1;i++) 
            //输出传来的排序好的数组  
            printf( 
            "%d ",number[i]); 
            //这里这么写是因为有些题有格式要求(最后一个数后面不能有空格)  
            printf( 
            "%d\n",number[i]); 
            return 
            0; } 
            //ENDING 
            
           
          
        

普通版

//当然这个版本是从小到大排的  #include 
          
          int number[]; int main() { int i,n,ii,j,temp; printf("输入数字个数：\n"); scanf("%d",&n); printf("输入%d个数:\n",n); for(int j=0;j 
        
          scanf( 
         "%d",&number[j]) ; 
         for (j= 
         0;j 
         
           1;j++) { 
          for (ii= 
          0;ii 
          
            1-j;ii++) { 
           if(number[ii]>number[ii+ 
           1]) 
           //顺序这里改 ！！！ { temp=number[ii]; number[ii]=number[ii+ 
           1]; number[ii+ 
           1]=temp; } } } 
           for (i= 
           0;i 
           
             1;i++) 
            printf( 
            "%d ",number[i]); 
            printf( 
            "%d\n",number[i]); 
            return 
            0; } 
            //ENDING 
            
           
          
        

>>>我的博客<<<