经典算法冒泡排序之标志位优化版

分手后的思念是犯贱 2024-03-31 16:17 33阅读 0赞

## 前言 ##

今天总结一下优化版的经典算法——冒泡排序，不同于以往的暴力二重for循环，这里的冒泡排序增加了一个标志位。我们要理解该冒泡排序的概念，算法流程与算法思想，探讨时间复杂度。

## 冒泡排序算法解析 ##

### 一、理解冒泡排序思想 ###

#### 1、算法概念 ####

也称气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换，再进行下一对元素的比较。

#### 2、算法思想 ####

总结来说，每一趟冒泡排序将会排好一个元素(极值)。不断的在无序区中执行该步骤，如果在某一次比较的过程中没有发生元素的交换，则证明元素都已经有序，可以提前结束整个算法。或者直到无序区中的元素减少到一个时，整个算法结束，此时整个序列有序。

### 二、算法分析 ###

#### 1、算法流程 ####

假如要对该序列进行冒泡排序，解析一下算法流程：

![3b6d2a0edd353d0e6367db19b41d30c8.png][]

第一趟排序：7和4 交换位置，变为：

![f95fcd5aa87ae9ca3a5aced2ca2980da.png][]

第二趟排序：6和4 交换位置，变为：

![54b24acfb6d75e5d2021020aec9e69be.png][]

此时序列符合升序排列，提前结束循环，排序完成，退出循环

#### 2、实现步骤 ####

首先当外层循环 i 为0时，内层循环中从序列里第一个元素开始两两计较，不是升序则交换位置，是升序则往后遍历，那么第一次外层循环一定可以确定最大值且位置在序列末尾。  
那么当外层循环次数增多，内层循环范围就要对应缩减，应为总长度 - 外层循环次数 - 1(减1是为了防止 i 等于0时数组溢出)。  
重复以上步骤，如果序列已经为升序，通过标志位来提前结束程序。

### 三、代码实现 ###

#### 1、源码及运行效果 ####

C++源代码：

#include<iostream>
    using namespace std;
    //冒泡排序声明
    void maopaosort(int A[], int len);
    //冒泡排序实现
    void maopaosort(int A[], int len)
    {
        for (int i = 0; i < len; i++) {
            int flag = 0;//标志位
            for (int j = i; j < len - i - 1; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                    flag = 1;
                }
            }
            if (flag == 0)//如果已经升序，不再继续外层循环，结束此函数
                return;
        }
        return ;
    }
    int main(void)
    {
        int A[7] = { 3,6,7,4,8,9,10 };
        int len = sizeof(A) / sizeof(A[0]);
        cout << "排序前：" << endl;
        for (int i = 0; i < len; i++) {
            cout << A[i] << " ";
        }
        maopaosort(A,len);
        cout << "排序后：" << endl;
        for (int i = 0; i < len; i++) {
            cout << A[i] << " ";
        }
    }

运行效果：

![eb095e4aba23aaf148a9dc15bfe7235d.png][]

#### 2、时间复杂度分析 ####

最好的情况：  
该序列为升序排列，内层循环执行了n-1次，那么相当于遍历了n次，时间复杂度为O(n)。  
最坏的情况：  
对于冒泡排序来说，最坏的情况依然是元素逆向有序，此时需要执行n-1趟，并且两两元素都需要交换，相当于是最小的元素排在末尾，—路交换到第一位，然后是次最小一路交换至第二位，此时的时间复杂度为: O(n^2)。  
平均情况：  
综合考虑下，冒泡排序算法的时间复杂度为O( n^2)

[3b6d2a0edd353d0e6367db19b41d30c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5362a854cabc4c4fafccf1dad7b188e4.png
[f95fcd5aa87ae9ca3a5aced2ca2980da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bd6c1b17c6094284b49fa2ba94c92496.png
[54b24acfb6d75e5d2021020aec9e69be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1e03f64757d14af08f0fbf4d7a64b3a6.png
[eb095e4aba23aaf148a9dc15bfe7235d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/69fb373ecd504cb69530b935081d12da.png