算法笔记冒泡排序

Dear 丶 2022-06-01 00:50 181阅读 0赞

排序是指将一个无序序列按某个规则进行有序排列，而冒牌排序是排序算法中最基础的一种。先给出一个序列a，其中元素的个数为n，要求将他们按从小到大的顺序排序。  
冒泡排序的本质在于**交换**，即每次通过交换的方式把当前剩余元素的最大值移动到一端，而当剩余元素减少为0时，排序结束。为了使排序过程更加清楚，举个例子。  
现在有一个数组a，其中有5个元素，分别为a\[0\] = 3,a\[1\] = 4,a\[2\] = 1,a\[3\] = 5,a\[4\] = 2,要求把它们按从小到大的顺序排列。下面的过程中，每趟将最大数交换到最右边：  
（1）第一趟  
a\[0\]与a\[1\]比较(3与4比较)，a\[1\]大，因此不懂，此时序列为｛3，4，1，5，2｝；  
![这里写图片描述][SouthEast]  
a\[1\]与a\[2\]比较(4与1比较)，a\[1\]大，因此把a\[1\]和a\[2\]交换，此时序列为\{3,1,4,5,2\}  
![这里写图片描述][SouthEast 1]  
a\[2\]与a\[3\]比较(4与5比较)，a\[3\]大，因此不动，此时序列为\{3,1,4,5,2\};  
![这里写图片描述][SouthEast 2]  
a\[3\]与a\[4\]比较(5与2比较)，a\[4\]大，因此把a\[3\]和a\[4\]交换，此时序列为\{3,1,4,2,5\};  
![这里写图片描述][SouthEast 3]

*由此，第一趟排序结束，共进行了四次比较。*  
(2)第二趟  
a\[0\]和a\[1\]比较(3与1比较)，a\[0\]大，因此把a\[0\]和a\[1\]交换，此时序列为\{1,3,4,2,5\}  
![这里写图片描述][SouthEast 4]  
a\[1\]和a\[2\]比较(3与4比较)，a\[2\]大，因此不动，此时序列为\{1,3,4,2,5\}  
![这里写图片描述][SouthEast 5]  
a\[2\]和a\[3\]比较(4与2比较)，a\[2\]大，因此把a\[2\]和a\[3\]交换，此时序列为\{1,3,2,4,5\}  
![这里写图片描述][SouthEast 6]  
*由此，第二趟排序结束，共进行了三次比较。*  
(3)第三趟  
a\[0\]和a\[1\]比较(1与3比较)，a\[1\]大，因此不动，此时序列为\{1,3,2,4,5\}  
![这里写图片描述][SouthEast 7]  
a\[1\]和a\[2\]比较(3与2比较)，a\[1\]大，因此把a\[1\]和a\[2\]交换，此时序列为\{1,2,3,4,5\}  
![这里写图片描述][SouthEast 8]  
*由此，第三趟排序结束，共进行了两次比较。*  
(4)第四趟  
a\[0\]和a\[1\]比较(1与2比较)，a\[1\]大，因此不动，此时序列为\{1,2,3,4,5\}  
![这里写图片描述][SouthEast 9]

*由此，第四趟排序结束，共进行了一次比较。*  
至此，已经无法在继续比较，序列已经有序，冒泡排序结束。  
下面来看看如何实现，先来学习如何交换两个数（借助中间变量）。

#include<stdio.h>
    int main(){
        int a = 1,b = 2;
        int temp = a;
        a = b;
        b = temp;
        printf("a = %d, b = %d\n",a,b);
        return 0;
    }

输出结果：

a = 2,b= 1

然后实现冒泡排序。

#include<stdio.h>
    int main(){
        int a[5] = {
       3,1,4,5,2};
        for(int i = 1;i <= 4;i ++){
            for(int j = 0;j < 5 - i;j++){
                if(a[j] > a[j + 1]){
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for(int i = 0;i < 5;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }

输出结果：

1 2 3 4 5

> 摘录自《算法笔记》胡凡，曾磊主编

[SouthEast]: /images/20220601/6f3e3a9f65194a0093472f9f52884305.png
[SouthEast 1]: /images/20220601/33fc517c934644b9950607dbad30c29e.png
[SouthEast 2]: /images/20220601/5e4ca1c173a141649a574d0c0d6c69ac.png
[SouthEast 3]: /images/20220601/ccf5c4b137e44a61abe63f6332defc70.png
[SouthEast 4]: /images/20220601/1f05aff150204b009c96c12c4ca29ee2.png
[SouthEast 5]: /images/20220601/5e446f01e46140b4a36f4b5b7633ed59.png
[SouthEast 6]: /images/20220601/6187db26ec9e41fdb36dd5229bd10b87.png
[SouthEast 7]: /images/20220601/1051140332cb44bc99e4aea7009e77af.png
[SouthEast 8]: /images/20220601/bf00d7f6358b4e588d5037abb2ce942c.png
[SouthEast 9]: /images/20220601/0efb6aa4ade04af58b031e819b604486.png