数据结构——冒泡排序(C语言)

不念不忘少年蓝@ 2022-10-24 01:42 196阅读 0赞

### C语言详解冒泡排序 ###

*  一、基本思想
 *  二、算法实现及优化
 *  三、代码清单

# 一、基本思想 #

冒泡排序是交换排序中最易理解也最经典的一个排序，其基本思想是**从左向右依次比较相邻两个元素的大小，如果左边大于右边就交换，一趟排序后就可以让最大的值浮到最右侧。不断重复这个操作就可以让数组有序。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

# 二、算法实现及优化 #

想要实现冒泡排序，我们首先写出一趟冒泡排序，很简单，从左向右依次比较即可，只要左边大于右边就发生交换

注意：  
数组**有n个**元素，我们从数组的**第1个元素开始**比较，到数组的**第n-1个元素结束**，共**比较了n-1**次。例如下图，从第1个开始到第6个结束。一趟排序的代码就可以写出来：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

//1.第1趟排序，从第1个元素开始到n-1个元素结束,比较n-1次
    		for (int j = 0; j < n-1; ++j)
    		{
        
    			//如果左边大于右边，则交换位置
    			if (a[j] > a[j + 1])
    			{
        
    				Swap(&a[j], &a[j + 1]);
    			}
    		}

这样一趟排序下来就可以把最大的数字冒到最右边了，如果我们重复这个操作n-1次就可以把次大的数，再次大的数都冒到最右边，一个循环搞定

void BubbleSort1(int* a, int n)
    {
        
      //排n趟就可以让数组有序
      int end=n-1;
      while(end>0)
      {
        
        //一趟排序，从第一个元素开始到n-1个元素结束，
         for(int j = 0; j<n-1; ++j)
         {
        
            //如果左边大于右边，就交换
            if(a[j]>a[j+1])
            {
        
              Swap(&a[j],&a[j+1]);
            }
         }
         --end;
    
        PrintArr(a,n);
      }
    }

![在这里插入图片描述][20210128203246464.png]

这个代码虽然可以让数组有序，但却有冗余的排序，**因为一趟排序后数组中的最大元素就可以确定位置，第二趟排序后次大元素的位置也被确定**，因此我们可以继续优化代码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]  
如图，第一趟从一个元素开始比较n-1次，56冒到最右边；  
第二趟最后一个元素位置确定，只用比较n-2次即可，55冒到次右边；  
……  
第6趟只需要比较一次就可以让数组有序。  
**假设数组中有n个元素，则需要排n-1趟，每一趟用i表示，第i趟就需要比较n-i-1次**，代码

void BubbleSort2(int* a, int n)
    {
        
      //n-1趟排序
      for(int i = 0; i < n-1; ++i)
      {
        
        //每一趟比较n-i-1次
        for(int j=0; j<n-i-1; ++j)
        {
        
          if(a[j]>a[j+1])
          {
        
            Swap(&a[j],&a[j+1]);
          }
        }
    
        PrintArr(a,n);
      }
    }

![在这里插入图片描述][20210128203222364.png]  
这个算法依然可以优化，假设数组在第i趟排序后就已经有序，那么后面就不要再比较了，这种优化更加简单，只需要**定义一个flag，如果在一趟排序中flag没有发生变化，我们就可以认为这个数组已经有序**，则退出循环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]

void BubbleSort(int* a, int n)
    {
        
      //n-1趟排序
      for(int i = 0; i < n-1; ++i)
      {
        
        int flag = 0; //设置flag
        //每一趟比较n-i-1次
        for(int j=0; j<n-i-1; ++j)
        {
        
          if(a[j]>a[j+1])
          {
        
            flag = 1; //如果该趟排序发生交换，flag置1
            Swap(&a[j],&a[j+1]);
          }
        }
        PrintArr(a,n);
        //一趟排序过后没有发生变化，说明数组已经有序
        if(flag == 0)
          break;
      }
    }

![在这里插入图片描述][20210128203145199.png]

# 三、代码清单 #

#include <stdio.h>
    
    void PrintArr(int* a, int n)
    {
        
      for(int i = 0; i < n; ++i)
      {
        
        printf("%d ",a[i]);
      }
      printf("\n");
    }
    
    void Swap(int* px, int* py)
    {
        
      int tmp = *px;
      *px = *py;
      *py = tmp;
    }
    
    void BubbleSort1(int* a, int n)
    {
        
      //排n趟就可以让数组有序
      int end=n-1;
      while(end>0)
      {
        
        //一趟排序，从第一个元素开始到n-1个元素结束，
         for(int j = 0; j<n-1; ++j)
         {
        
            //如果左边大于右边，就交换
            if(a[j]>a[j+1])
            {
        
              Swap(&a[j],&a[j+1]);
            }
         }
         --end;
    
        PrintArr(a,n);
      }
    }
    
    
    void BubbleSort2(int* a, int n)
    {
        
      //n-1趟排序
      for(int i = 0; i < n-1; ++i)
      {
        
        //每一趟比较n-i-1次
        for(int j=0; j<n-i-1; ++j)
        {
        
          if(a[j]>a[j+1])
          {
        
            Swap(&a[j],&a[j+1]);
          }
        }
    
        PrintArr(a,n);
      }
    }
    
    void BubbleSort(int* a, int n)
    {
        
      //n-1趟排序
      for(int i = 0; i < n-1; ++i)
      {
        
        int flag = 0; //设置flag
        //每一趟比较n-i-1次
        for(int j=0; j<n-i-1; ++j)
        {
        
          if(a[j]>a[j+1])
          {
        
            flag = 1; //如果该趟排序发生交换，flag置1
            Swap(&a[j],&a[j+1]);
          }
        }
        PrintArr(a,n);
        //一趟排序过后没有发生变化，说明数组已经有序
        if(flag == 0)
          break;
      }
    }
    
    
    int main()
    {
        
      int a[] = {
        25,6,56,24,9,12,55};
      int b[] = {
        25,6,56,24,9,12,55};
      int c[] = {
        25,6,56,24,9,12,55};
      int n = sizeof(a)/sizeof(a[0]);
      printf("-----BubbleSort------\n");
      BubbleSort(a,n);
      printf("-----BubbleSort1------\n");
      BubbleSort1(b,n);
      printf("-----BubbleSort2------\n");
      BubbleSort2(c,n);
       //PrintArr(a,n);
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221024/51e0ff27dce04f378bdf63f4af773984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221024/46b2132942d94269967d530f846aace3.png
[20210128203246464.png]: /images/20221024/4046e3eabc754636a6a3844fd48cd033.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]: /images/20221024/ad55784c057a45c79036feb6425cd156.png
[20210128203222364.png]: /images/20221024/743fd399e7244649a6228e16abb17a19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]: /images/20221024/d8ad72dba7e04af9b80b31dff4e6ae2d.png
[20210128203145199.png]: /images/20221024/1178f84fe8f941cdb4afc8a3b5e0fb0f.png