一起来学习最基础的排序算法冒泡排序

站长

2023年09月08日 04:00 · 阅读数 34

排序算法，不仅实用，而且也是算法面试的常考题目。虽然各个语言都提供了相关排序的API，但是我们还是有必要去通过学习各种排序算法的思想来提高我们的编码、逻辑、算法能力~

复杂度和稳定性一览

复杂度：就是算法优劣里面常常会涉及到的概念，包括以下两个概念：

时间复杂度
空间复杂度

不过「排序算法」里面还涉及到了另一个指标概念，即：「稳定性」

一起来学习最基础的排序算法冒泡排序

这里的稳定性指的是：对于存在相等元素的序列，排序过后，原相等元素的排序结果中的相对位置相比原输入序列不变。

相对位置：指保证在原来数组中的位置顺序，不是绝对的。即原有数组中[1,2,3,4]。以下例子2和3是否保证相对顺序不变：

[2,1,3,4] √ (2还是在3前面)
[3,2,1,4] × (2在3的后面)
[2,1,4,3] √ (2还是在3前面)

而稳定性是排序过后原相等元素的排序结果中的相对位置相比原输入序列不变。所以如果这样一个数组[2,31,32,1][2,3_1,3_2,1][2,31,32,1]。它们排序过后保证稳定性得到的数组一定是[1,2,31,32][1,2,3_1,3_2][1,2,31,32]。313_131一定是在323_232前面的。

不过这里可能大家会存在疑问？这种数值的排序，是否稳定没有区别？那么有什么用呢？

一起来学习最基础的排序算法冒泡排序

其实也很好理解，既然排序对象如果只是数值没有用。那么如果是对引用类型进行排序，排序依据是该类型中某个可比较的数值字段，那么当我们希望该字段相同的时候，其他字段不同的元素相对位置相比输入位置保持不变，这时候就需要稳定排序了。稳定性在某些应用场景中非常有用，以下是一些稳定性的应用场景和好处：

保持相对顺序：在某些情况下，元素的相对顺序很重要。例如，如果有一个记录列表，按照一定条件排序后，希望相同条件的记录保持原来的相对顺序，那么就需要使用稳定的排序算法。
多次排序：有时需要对相同数据集进行多次排序，但每次排序的依据不同。如果使用稳定的排序算法，可以确保后续排序不会影响先前的排序结果。
保持先前有序性：如果数据集本身已经是有序的，但需要对其中的某些属性进行排序，希望不影响原有的有序性，那么稳定的排序算法是必需的。
关键字排序：在一些应用中，需要对多个关键字进行排序，先按一个关键字排序，然后再按另一个关键字排序。如果第一个关键字相同的元素在第二个关键字排序后仍然保持相对顺序，那么稳定性是必要的。

总之，稳定性在需要保持相对顺序、多次排序、保持有序性等场景中非常有用，可以提供更精细的排序控制和更准确的结果。

下面是各大排序算法的时间复杂度和空间复杂度，以及稳定性

排序算法	平均时间	最好时间	最坏时间	空间	稳定性*
冒泡	O(n2)O(n^2)O(n2)	O(n)O(n)O(n)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	稳定
选择	O(n2)O(n^2)O(n2)	O(n2)O(n^2)O(n2)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	不稳定
插入	O(n2)O(n^2)O(n2)	O(n)O(n)O(n)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	稳定
希尔	O(nlogn)O(nlogn)O(nlogn) ~ O(n2)O(n^2)O(n2)	O(nlogn)O(nlogn)O(nlogn)	O(n2)O(n^2)O(n2)	O(1)O(1)O(1)	不稳定
希尔	O(nlog3n)O(nlog_3n)O(nlog3n) ~ O(n32)O(n^\frac{3}{2})O(n23)	O(nlog3n)O(nlog_3n)O(nlog3n)	O(n32)O(n^\frac{3}{2})O(n23)	O(1)O(1)O(1)	不稳定
归并	O(nlogn)O(nlogn)O(nlogn)	O(nlogn)O(nlogn)O(nlogn)	O(nlogn)O(nlogn)O(nlogn)	O(n)O(n)O(n)	稳定
快速	O(nlogn)O(nlogn)O(nlogn)	O(nlogn)O(nlogn)O(nlogn)	O(n2)O(n^2)O(n2)	O(logn)O(logn)O(logn)	不稳定
堆	O(nlogn)O(nlogn)O(nlogn)	O(nlogn)O(nlogn)O(nlogn)	O(nlogn)O(nlogn)O(nlogn)	O(1)O(1)O(1)	不稳定
计数	O(n+k)O(n + k)O(n+k)	O(n+k)O(n + k)O(n+k)	O(n+k)O(n + k)O(n+k)	O(n+k)O(n + k)O(n+k)	稳定
基数	O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数	O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数	O(d(n+k))O(d(n + k))O(d(n+k))kkk 为常数	O(n+k)O(n + k)O(n+k)	稳定
桶	O(n)O(n)O(n)	O(n)O(n)O(n)	O(n2)O(n^2)O(n2) or O(nlogn)O(nlogn)O(nlogn)	O(n)O(n)O(n)	稳定

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。—— 百度百科

算法描述

对于一个要排序（升序）的数组，从第一位开始从前往后比较相邻大小的数字。存在三种情况：

当前数字比之后的数字小。不做任何操作。
当前数字和之后的数字相等。不做任何操作。
当前数字比之后的数字大。交换两个数字的位置。

这样一轮比较下来，那么数组最后的元素，就一定是最大的。我们总共需要重复这个过程n-1次。（n为数组的长度）。同时我们每次都确定了一个本轮最大的元素，将其放在了数组的后面。所以我们每轮比较都只需要比较到还未排序的位置。即n-i-1（i为当前轮数），例如当i为0的时候是第一轮，此时就将本轮最大的元素放在了n-0-1这个位置上，当i为1的时候是第二轮，此时就将本轮最大的元素（数组第二大的元素）放在了n-1-1这个位置上，依此类推。

为什么是n-1次而不是n次呢，其实非常简单，如果我们有两个数，想让它变成有序，那么我们只要把最大的放在最后一个，那么剩下的就自然而然的就在第一个，只需要一次。而我们冒泡排序这个过程，就是把每轮最大的放在了数组的后面，每轮确定了一个元素的位置，那么最后剩下的一个就不需要移动了。

一起来学习最基础的排序算法冒泡排序

稳定性

通过我们之前的算法描述可以知道，存在的三种情况其中的第二种，两个相等的元素之间，是不做任何操作的。所以它是能保证稳定性的。

代码实现

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        //重复n-1次，冒泡排序过程
        for (int i = 0; i < n; ++i) {
            //比较次数
            for (int j = 0; j < n - i - 1; ++j) {
                if (arr[j + 1] < arr[j]) swap(arr, j, j + 1);
            }
        }
    }
    
    //交换数组元素
    public static void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }

时间空间复杂度

时间复杂度：两层 forforfor 循环，第 1 轮比较 n−1n - 1n−1 次 (n=arr.length)(n = arr.length)(n=arr.length) ，最后一轮比较 1 次。总比较次数为 n∗(n−1)/2n*(n - 1) / 2n∗(n−1)/2 次，时间复杂度为 O(n2)O(n^2)O(n2)。当输入数组为已排序状态时，在应用提前结束优化的情况下，只需一轮比较，此时为最佳时间复杂度 O(n)O(n)O(n)。

空间复杂度：算法中只有常数项变量，O(1)O(1)O(1)。

代码优化

提前结束

当我们这个数组排序对象如果已经有序，但是我们的算法还是会天真的继续执行剩下的次数进行比较。所以我们需要设置一个布尔值来记录此轮是否发生了交换。如果此轮没有发生交换，说明当前数组已经有序了，可以提前退出循环结束程序。

    public static void bubbleSortOpt(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            //标志本轮是否有数据交换
            boolean flag = false;
            for (int j = 0; j < n - 1 - i; ++j) {
                if (arr[j + 1] < arr[j]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            //没有数据交换，说明已经有序 提前结束
            if (!flag) break;
        }
    }
    
    //交换数组元素
    public static void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }

边界优化

记录前一轮交换的最终位置，该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。容易看出此优化包含了提前结束优化。举个例子：输入数组[1,3,2,4,5,6,7]

第一轮交换的最终位置是下标为1,即把3和2进行了交换。由于后面的元素是已经有序的，所以没有发生交换，这一轮记录的交换最终位置下标就一直是1。我们后面每轮的交换位置就变成了下标[0,1]而不再是从前固定的[0,n-i-1],同时我们也可以通过判断最终交换位置是否发生了改变，如果没变说明不存在交换，当前数组已经有序了。（提前结束）

    public static void bubbleFinalOpt(int[] arr) {
        int n = arr.length;
        //是否发生过交换
        boolean flag = true;
        //lastSwappedIdx表示前一轮交换的最终位置，即下标为lastSwappedIdx是未排序部分中的最后一个数的下标
        int lastSwappedIdx = n - 1;
        while (flag) {
            flag = false;
            //当前坐标
            int curIndex = -1;
            for (int i = 0; i < lastSwappedIdx; ++i) {
                if (arr[i + 1] < arr[i]) {
                    swap(arr, i, i + 1);
                    flag = true;
                    curIndex = i;
                }
            }
            lastSwappedIdx = curIndex;
        }
    }
    
    //交换数组元素
    public static void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }

当然冒泡排序还不只存在这两种优化情况。还有以下

双向冒泡排序
鸡尾酒排序
设置跳跃步长

需要注意的是，虽然这些优化策略可以提升冒泡排序的性能，但冒泡排序的最坏时间复杂度仍然是O(n^2)，因此在实际应用中，对于大规模数据集，更高效的排序算法如快速排序、归并排序等更为合适。所以学有余力的，可以自行去了解哦~~

认为本文写的不错的话，请来一个点赞，收藏，关注吧~~~~

一起来学习最基础的排序算法冒泡排序

转载自:https://juejin.cn/post/7272690326400647203