手撕排序算法：冒泡排序

文章目录

• 1.算法思想
• 2.冒泡排序具体过程
• 3.算法分析
• • 3.1时间复杂度
  • 3.2空间复杂度
  • 4.算法的优缺点
  • • 4.1算法的优点
    • 4.2算法的缺点
    • 5.冒泡排序优化方案
    • 6.算法实现
    • 7.实战
    • • 7.1 力扣88. 合并两个有序数组
      • 7.2力扣2148.元素计数
      • 7.3力扣1046.最后一块石头的重量

        冒泡排序(Bubble Sort)是一种简单的排序算法，通过多次比较和交换相邻的元素，将数组

        
        （图片来源网络，侵删）

        中的元素按升序或降序排列。

        1.算法思想

        冒泡排序的基本思想是：每次遍历数组，比较相邻的两个元素，如果它们的顺序错误，就将它

        们交换，直到数组中的所有元素都被遍历过。

        具体的算法步骤如下：

        第一步、遍历数组的第一个元素到最后一个元素。

        第二步、对每一个元素，与其后一个元素进行比较。

        第三步、如果顺序错误，就将它们交换。

        重复上述步骤，直到数组中的所有元素都被遍历过至少一次。

        2.冒泡排序具体过程

        首先需要将「第一个元素」和「第二个元素」进行「比较」，如果前者大于后者，则进行「交

        换」，

        然后再比较「第二个元素」和「第三个元素」，以此类推，直到「最大的那个元素」被移动

        到「最后的位置」。

        然后，进行第二轮「比较」，直到「次大的那个元素」被移动到「倒数第二的位置」

        最后，经过一定轮次的「比较」和「交换」之后，一定可以保证所有元素都是「升序」排列

        的。

        3.算法分析

        3.1时间复杂度

        我们假设「比较」和「交换」的时间复杂度为O(1)(为什么这里说假设，因为有可能要「比

        较」的两个元素本身是数组，并且是不定长的，所以只有当系统内置类型，我们才能说这两个操

        是0(1)的)。

        「冒泡排序」中有两个嵌套循环。

        外循环正好运行一1次迭代。但内部循环运行变得越来越短：

        当i=0,内层循环n一1次「比较」操作。

        英雄哪里出来182585442552122

        当i=1,内层循环n一2次「比较」操作。

        当i=2,内层循环n一3次「比较」操作。

        当i=n一2，内层循环1次「比较」操作。

        当i=n一1，内层循环0次「比较」操作。

        英雄哪里出来海豚知通552122

        因此，总「比较」次数如下：

        总的时间复杂度为：O(n^2)

        3.2空间复杂度

        由于算法在执行过程中，只有「交换」变量时候采用了临时变量的方式，而其它没有采用任何

        的额外空间，所以空间复杂度为O(1)。

        4.算法的优缺点

        4.1算法的优点

        1.简单易懂：冒泡排序的算法思想非常简单，容易理解和实现。

        2.稳定排序：冒泡排序是一种稳定的排序算法，即在排序过程中不会改变相同元素的相对顺

        序。

        4.2算法的缺点

        1.效率较低：由于需要进行多次比较和交换，冒泡排序在处理大规模数据时效率较低。

        2.排序速度慢：对于大型数组，冒泡排序的时间复杂度较高，导致排序速度较慢。

        5.冒泡排序优化方案

        「冒泡排序」在众多排序算法中效率较低，时间复杂度为O(2)。

        想象一下，当有=100000个数字。即使我们的计算机速度超快，并且可以在1秒内计算

        10^8次操作，但冒泡排序仍需要大约一百秒才能完成。

        但是，它的外层循环是可以提前终止的，例如，假设一开始所有数字都是升序的，那么在首轮「比较」的时候没有发生任何的「交换」，那么后面也就不需要继续进行「比较」了，直接跳出外

        层循环，算法提前终止。

        「改进思路」如果我们通过内部循环完全不交换，这意味着数组已经排好序，我们可以在这个

        点上停止算法。

        6.算法实现

        void Bottle_Sort(int nums[],int numsSize) {  
            for (int i = 0; i   
                for (int j = 0; j  
        7.实战
         
        7.1 力扣88. 合并两个有序数组
         
        给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
        请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
        **注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
         
        void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {  
            int i,j,num;  
            for(i=0;i  
                nums1[m+i]=nums2[i];  
            }  
            for(i=0;i  
                for(j=0;j  
                    if(nums1[j]nums1[j+1])  
                    {  
                        num=nums1[j];  
                        nums1[j]=nums1[j+1];  
                        nums1[j+1]=num;  
                    }  
                }  
            }  
        }
          
            for (int i = 0; i   
                for (int j = 0; j