21天经典算法之冒泡排序

​
​

活动地址：CSDN21天学习挑战赛

专栏前言:

本专栏主要是算法训练，目的很简单。就是为了进厂
最近官方在组织 21 天挑战赛，趁此机会我也更新一下经典算法的文章
如果想一起“狂”或者交流，欢迎来私聊
还不快趁着这个机会来提升自己💪

👉排序算法介绍

排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。最终序列按照一定的规律进行呈现。

在排序算法中，稳定性和效率是我们经常要考虑的问题。

稳定性：稳定是指当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。

复杂度分析：
（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

常见的排序算法分为以下几种：

👉冒泡排序

原理

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

就像一个泡泡小的泡泡就会不断地上升或者下降，它的名字也就由此而来（冒泡排序）

代码实现

for (int i = 0; i < nums.length; i++) {
   for (int j = 0; j < nums.length - 1; j++) {
       if(nums[j] > nums[j+1]){
           int tmp = 0;
           tmp = nums[j];
           nums[j] = nums[j+1];
           nums[j+1] = tmp;
        }
   }
}

优化冒泡

for (int i = 0; i < nums.length - 1; i++) {
    boolean flag = false;
    for (int j = 0; j < nums.length - 1 - i; j++) {
       if(nums[j] > nums[j + 1]){
            int tmp = 0;
            tmp = nums[j];
            nums[j] = nums[j+1];
            nums[j+1] = tmp;
            flag = true;
        }
   }
   if(flag == false){
       return;
   }
}

复杂度分析

时间复杂度：

• 最好的情况：$O(n)$。如果元素排列是正序的，那么只需要循环比较一次，并且移动0次即可。冒泡排序最好的时间复杂度为$O(n)$ 。
• 最坏的情况：$O(n^2)$。如果元素排序反向有序，那么需要$n-1$次循环，并且每次排序都需要$n-i$次的比较。冒泡排序的最坏时间复杂度为 $O(n^2)$ 。
• 平均复杂度：$O(n^2)$。

空间复杂度：$O(1)$。冒泡排序的辅助变量空间仅仅是一个临时变量,并且不会随着排序规模的扩大而进行改变,所以空间复杂度为O(1)

稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

👉示例：

👉算法实践

💭
算法的整体思想已经在上面讲述了，下面直接使用一个例子来试试水。

冒泡排序

题目描述：

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

class Solution {
    public int[] sortArray(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if(nums[j] > nums[j + 1]){
                    int tmp = 0;
                    tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    flag = true;
                }
            }
            if(flag == false){
                return nums;
            }
        }
        return nums;
    }
}

冒泡在此题目中会超时，但是也可以使用这种方式。

👉课后习题

如果你觉得掌握了，那么赶快来实践一下吧

​