通俗易懂的让你彻底搞懂冒泡排序的由来

迷南。 2022-06-04 23:26 233阅读 0赞

先上图：

![这里写图片描述][SouthEast]

冒泡排序是属于简单排序当中的，为什么叫冒泡排序呢，  
假如我们把我们的元素用泡泡去比喻，那么数据不同，泡泡就不同大小。

假如我们想把数据从小到大排序，那么在排序的过程中小泡泡会慢慢往上被交换出来也叫冒上来。

分析冒泡过程：

既然冒泡排序就是元素不断交换的过程，那么我们图中假如有5个泡泡，那么我们假如开始第一趟冒泡比较，第一个泡和第二个泡比较大小，大的泡泡会放在下面的位置，那么就有2个可能，要么小泡往上冒，要么不动，那么我一直2 个相邻的泡泡进行大小比较，出现下面的泡小就往上冒，那么比到最后一个泡就结束了第一趟过程，这样我们的最后一个泡泡就是最大的。 接下来我们就需要把剩余的4个泡继续上面过程，我们知道冒一趟就找到一个最大的放他对应的位置，那么就5个泡，我们假如冒了4趟后最大的4个泡泡就已经在最下面。那么第一个泡泡是不是最小的呢，肯定是，因此我们知道了需要冒泡的回合数就是泡泡数-1.

现在我们来具体上代码：

//冒泡排序
    //参数A[] 把需要的数组给我，以及数组的元素个数也给我 我将给你一个有序的数组
    void Bubble_Sort(ElementType A[], int n)
    {
       int flag = 0;  //标志初始为0表示没有发现元素交换 为了改善性能用，如果没有元素交换说明本来就有序直接跳出循环
       //由上面分析我们知道了排序的回合数是n - 1;
       //开始循环回合数
       for(int i = 0，flag = 0; i < n - 1; i++)
       {
             //我们规定大索引的数是看成河底下的泡泡  依次索引减少 泡泡就位于接近地面
            //开始真正的每一趟的比较
            //j我们先从最大索引也就是水最底层开始拿出数据或者叫泡泡去和上个索引对应的泡泡比较大小
            //如果大索引的泡泡也就是数值大我们就让泡泡和小泡泡交换位置也称为向上冒泡
            //这个时候j--就拿到最大索引--之后的冒泡继续比较
            //当索引出现等于i + 1的时候  说明第一趟冒泡完毕  我们把最小的泡泡冒到最上层
            //然后外面的循环继续选择第二个最小的泡泡依次冒.............
            for(int j = n - 1; j >= 1 + i; j-- ) 
            {
                if(A[j] > A[j - 1]) 
                {
                    //交换下元素
                    Swap(A[j],A[j + 1]);
                    flag = 1; //表示元素交换过
                }
            }
    
            //第一趟比较完后开始跑后面代码  这个时候我们就可以了解是不是换过元素
            //开始判断标志 来了解元素是不是早就有序
            if(flag == 0)
            {
               //说明元素有序了
               break;    //直接跳出循环，没有必要进行后续的for循环了
            }
       }
    }
    
    
    排序时间复杂度分析：最坏的情况就是我们执行完第一趟就发现已经序，这个时候我们仅仅是和这个n也就是元素的多少有关。时间复杂度为0（n）
    
    最坏情况： 每一趟是时间复杂度是n 进行了n - 1趟。 那么最终是n*(n - 1) 时间复杂度则为0(N^2)
    
    注意：请学习思路，不要用我的代码，我代码是直接在博客手写的，没有去vs上写，我希望分享的思想是，程序来源于生活。用现实去架构代码思想，我相信你进步很大。具体代码实现如果不是按照直接思想写出来的，我想对你们意义并不大。有什么问题可以直接提出。
    我不保证代码的正确性，千万别想着克隆我的直接运行成功就完事，这样可能对你们没有多少好处，实现代码其实很多。

[SouthEast]: /images/20220605/5db3440a24634b4284e0e6cbb5b01152.png