冒泡排序（数据结构）

傷城~ 2024-04-23 20:13 74阅读 0赞

![在这里插入图片描述][c73f3101f93f43918085ea32b7e6064d.png]  
冒泡排序属于交换排序的一种。

--------------------

#### 冒泡排序 ####

**算法思想：**  
![在这里插入图片描述][a820cee740cd4be0b30bba4b473a05bf.png]

--------------------

![在这里插入图片描述][34833234e16042e5bc23998af177ab48.png]

--------------------

#### 复杂度 ####

![在这里插入图片描述][d4985372792040258f669c8063a06260.png]

--------------------

#### 代码实现 ####

/**
     * 冒泡排序
     * @file BubbleSort.cpp
     */
    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    void swap(int &a, int &b) {
        
        int temp = a;
        a = b;
        b = temp;
    }
    
    // void BubbleSort(int A[], int n) {
        
    //     for(int i = 0;i < n;i++) {
        
    //         bool flag = false;
    //         for(int j = i+1;j < n;j++) {
        
    //             if(A[i] > A[j]) {
        
    //                 swap(A[i], A[j]);
    //                 flag = true;
    //             }
    //         }
    //         if(flag == false) { // 本趟遍历没有发生交换，说明表已经有序
    //             return ;
    //         }
    //     }
    // }
    
    // void BubbleSort(int A[], int n) {
        
    //     for(int i = 0;i < n-1;i++) {// 控制遍历的趟数
    //         bool flag = false;
    //         for(int j = n-1;j > i;j--) {
        
    //             if(A[j] < A[j-1]) {
        
    //                 swap(A[j], A[j-1]);
    //                 flag = true;
    //             }
    //         }
    //         if(flag == false) {// 本趟遍历没有发生交换，则说明表已经有序
    //             return ;
    //         }
    //     }
    // }
    
    void BubbleSort(int A[], int n) {
        
        for(int i = 0;i < n-1;i++) {
        // 控制遍历的趟数
            bool flag = false;
            for(int j = 0;j < n-1;j++) {
        
                if(A[j] > A[j+1]) {
         // 若为逆序，则交换
                    swap(A[j], A[j+1]);
                    flag = true;
                }
            }
            if(flag == false) {
        // 本趟遍历没有发生交换，则说明表已经有序
                return ;
            }
        }
    }
    
    void PrintArray(int A[], int n) {
        
        for(int i = 0;i < n;i++) {
        
            cout << A[i] << " ";
        }
        cout << endl;
    }
    
    int main() {
        
        int arr[] = {
        100,6,5,3,2,1,99};
        cout << "排序前：";
        PrintArray(arr, 7);
        BubbleSort(arr, 7);
        cout << "排序后：";
        PrintArray(arr, 7);
        return 0;
    }

> 注：以上图片来自B站王道数据结构截图

[c73f3101f93f43918085ea32b7e6064d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e222af6e72bb4ca98268f1f43cc1cb9d.png
[a820cee740cd4be0b30bba4b473a05bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/69bd71b0b76c4106be424eafa8842285.png
[34833234e16042e5bc23998af177ab48.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/50c9daf9e43f4de298dc10ed79871b07.png
[d4985372792040258f669c8063a06260.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9830a36db7b243d3b85b7345c663bf32.png