C语言笔记：冒泡排序法精讲+改进

﹏ヽ暗。殇╰゛Y 2023-06-06 04:00 0阅读 0赞

### 文章目录 ###

*  算法描述+实现
 *  改进一
 *  改进二
 *  关于冒泡排序法的稳定性问题

# 算法描述+实现 #

*  第一轮：从上往下扫描数组的N个元素，先比较第一对相邻元素（第一个元素与和第二个元素），如果逆序（第一个元素大于第二个元素）则交换，使小元素上移，再比较第二对相邻元素（第二个元素和第三个元素），如果逆序则仍交换，以此类推，经过第一轮处理，小元素慢慢上移，而最大的元素被移到最后的位置上，这也是它最终应该在的位置（最底部）
 *  第二轮：对于无序区的N-1个元素，仍然是从第一对相邻元素到最后一对相邻元素依次比较，如果逆序就交换，与第一轮不同的是，少比较了一对，结果使第二大的元素被移到倒数第二位置上，这也是排序后它的最终位置，即沉淀到了无序区N-1个元素底部。
 *  …

比如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]

实现代码：

#include <stdio.h>
    #define N 6
    void Input(int r[],int n);//输入数组的n个元素
    void Output(int r[],int n);//输出数组的n个元素
    void BubbleSort(int r[],int n);//使用冒泡排序法对数组的n个元素进行排序
    void Swap(int *pa,int *pb);//交换pa和pb所指变量的值 
    int main(void)
    { 
     int a[N];//定义大小为N的数组
     printf("输入数组的%d个元素：\n",N);
     Input(a,N);//输入数组的N个元素 
     printf("排序前数组a的元素为：");
     Output(a,N);//输出排序前数组的元素
     BubbleSort(a,N);//冒泡排序
     printf("排序后数组a的元素为：");
     Output(a,N);
     return 0; 
    } 
    void Input(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      scanf("%d",&r[i]);
     }
    }
    void Output(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      printf("%-4d",r[i]);
     }
     printf("\n");
    }
    void BubbleSort(int r[],int n)
    { 
     for(int i=1;i<n;i++)//控制轮数 
     { 
      for(int j=0;j<=n-1-i;j++)//每一轮对于无序区进行比较 
      { 
       if(r[j]>r[j+1])
       { 
        Swap(&r[j],&r[j+1]); 
       }
      }
     } 
    }
    void Swap(int *pa,int *pb)
    { 
     int temp;
     temp=*pa;
     *pa=*pb;
     *pb=temp;
    }

运行结果：  
![在这里插入图片描述][20191010094350984.PNG]  
第一轮（i=1）时，6个元素需要比较5次（j从0到4循环；j=0时，比较r\[0\]与r\[1\]；j=1时，比较r\[1\]与r\[2\]，依次类推），此时数组最后一个下标存放最大元素，接着比较前5个元素

第二轮（i=2）时，5个元素需要比较4次（j从0到3循环；j=0时，比较r\[0\]与r\[1\]；j=1时，比较r\[1\]与r\[2\]，依次类推），此时数组倒数第二个下标存放第二大元素，接着比较前4个元素

…

# 改进一 #

由上面的图和代码可知，在第三轮冒泡排序时，这整个数组完成排序，但是上面的代码仍会去循环扫描第四轮，第五轮。即不论冒泡排序情况如果，都要循环N-1轮，所以改进数组全部排序好了，不再进行循环扫描工作

#include <stdio.h>
    #define N 6
    void Input(int r[],int n);//输入数组的n个元素
    void Output(int r[],int n);//输出数组的n个元素
    void BubbleSort(int r[],int n);//使用冒泡排序法对数组的n个元素进行排序
    void Swap(int *pa,int *pb);//交换pa和pb所指变量的值 
    int main(void)
    { 
     int a[N];//定义大小为N的数组
     printf("输入数组的%d个元素：\n",N);
     Input(a,N);//输入数组的N个元素 
     printf("排序前数组a的元素为：");
     Output(a,N);//输出排序前数组的元素
     BubbleSort(a,N);//冒泡排序
     printf("排序后数组a的元素为：");
     Output(a,N);
     return 0; 
    } 
    void Input(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      scanf("%d",&r[i]);
     }
    }
    void Output(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      printf("%-4d",r[i]);
     }
     printf("\n");
    }
    void BubbleSort(int r[],int n)
    { 
     int swapflag=1;//设置swapflag为某轮是否有元素交换的标记，有交换则其值为1，否则为0，保证第1次必须扫描，初始值为1 
     for(int i=1;swapflag&&i<n;i++)//控制轮数,在某一轮排序结束后如果swapflag=0，则表示整个数组的排序完成，不再循环后面的轮数 
     { 
      swapflag=0;
      for(int j=0;j<=n-1-i;j++)//每一轮对于无序区进行比较 
      { 
       if(r[j]>r[j+1])
       { 
        Swap(&r[j],&r[j+1]); 
        swapflag=1; 
       }
      }
      printf("%d轮排序结果：",i);
      Output(r,n);
     } 
    }
    void Swap(int *pa,int *pb)
    { 
     int temp;
     temp=*pa;
     *pa=*pb;
     *pb=temp;
    }

运行结果：  
![在这里插入图片描述][20191010101230499.PNG]

# 改进二 #

我们知道每进行一轮排序，则会从N-1无序序列中选中最大的元素，比如我们进行到第三轮排序，此时最大元素r\[5\]，第二大元素r\[4\]，第三大元素r\[3\]，已经分别占据r数组的倒数三个下标位置，在进行第四轮排序时，无需在循环比较数组r倒数3个元素的值，基于这种思想，我们设置一个变量lastSwapIndex记录上一轮最后交换的一对元素中前面元素的下标，下一轮开始首先应该根据上一轮是否有交换以及交换位置来决定此轮进行比较的范围。

#include <stdio.h>
    #define N 6
    void Input(int r[],int n);//输入数组的n个元素
    void Output(int r[],int n);//输出数组的n个元素
    void BubbleSort(int r[],int n);//使用冒泡排序法对数组的n个元素进行排序
    void Swap(int *pa,int *pb);//交换pa和pb所指变量的值 
    int main(void)
    { 
     int a[N];//定义大小为N的数组
     printf("输入数组的%d个元素：\n",N);
     Input(a,N);//输入数组的N个元素 
     printf("排序前数组a的元素为：");
     Output(a,N);//输出排序前数组的元素
     BubbleSort(a,N);//冒泡排序
     printf("排序后数组a的元素为：");
     Output(a,N);
     return 0; 
    } 
    void Input(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      scanf("%d",&r[i]);
     }
    }
    void Output(int r[],int n)
    { 
     for(int i=0;i<n;i++)
     { 
      printf("%-4d",r[i]);
     }
     printf("\n");
    }
    void BubbleSort(int r[],int n)
    { 
     int lastSwapIndex=n-1;//初始化为数组r最后一个下标
     for(int i=1;lastSwapIndex>0;i++)
     { 
      int temp=-1;//每次进行排序temp值重置为-1， 
      for(int j=0;j<lastSwapIndex;j++)
      { 
       if(r[j]>r[j+1])
       { 
        Swap(&r[j],&r[j+1]);
        temp=j;
       }
      }
      printf("%d轮排序结果：",i);
      Output(r,lastSwapIndex+1);//输出本轮扫描的元素以及交换后的结果 
      lastSwapIndex=temp;//本轮最后一对交换前面一个元素下标赋值给lastSwapIndex，由于第3次的时候没有进行任何交换操作，lastSwapIndex=temp=-1退出最外层循环 
     } 
    }
    void Swap(int *pa,int *pb)
    { 
     int temp;
     temp=*pa;
     *pa=*pb;
     *pb=temp;
    }

输出：  
![在这里插入图片描述][20191010145450925.PNG]

# 关于冒泡排序法的稳定性问题 #

首先什么是排序算法的稳定性呢？比如一组学生（有学号，成绩）按成绩递增排序，如果两个学生成绩相等，按排序前的位置排序，这就要求排序算法必须是稳定的。对于冒泡排序算法，任何元素的移动是发生在相邻元素r\[j\]>r\[j+1\]条件成立时，所以当r\[j\]==r\[j+1\]时，不符合交换条件，不改变它们的相对位置，所以冒泡排序是稳定的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEyNDIzNA_size_16_color_FFFFFF_t_70]: /images/20230601/918be7b71f3b475dbfd8ffb94000b4a0.png
[20191010094350984.PNG]: /images/20230601/2e4a163403db4003a7821112059cd805.png
[20191010101230499.PNG]: /images/20230601/b9e7bb346b0a47a093f2f26a45b8e6d1.png
[20191010145450925.PNG]: /images/20230601/8f0ffbe16279475ebdd5c97dfa3a1b04.png