冒泡排序算法实现思想个人理解

技术交流QQ群:1027579432，欢迎你的加入！

一、冒泡排序算法个人理解

• 主要是以两个形成嵌套的for循环来完成的。外层的for循环以索引ix的值来逐个访问序列中的每个元素，ix的值由0开始增加到size(sequence) - 1，当外部的for循环迭代完成后，由ix索引取出的元素已经被放在正确的位置上了。放元素的操作是由内层的for循环来实现的，内层for循环的索引的值jx从ix+1依次递增到size(sequence) - 1为止，它比较位于ix和jx上的两个元素，如果jx上的元素较小，就将两个元素互换。具体排序过程见下图：

  
  
  

  冒泡排序.jpg

二、冒泡排序算法代码实现(C++版本)

#include "iostream"

using namespace std;

void bubleSort(int * a, int n);


int main(){
    int ix;
    int a[] = {8, 34, 3, 13, 1, 21, 5, 2};
    int a_length = (sizeof(a)) / (sizeof(a[0]));
    cout << "冒泡排序前:";
    for (int ix = 0; ix < a_length; ix++)
        cout << a[ix] << " ";
    cout << endl;

    bubleSort(a, a_length);

    cout << "冒泡排序后:";
    for (int ix = 0; ix < a_length; ix++)
        cout << a[ix] << " ";
    cout << endl;

    return 0;
}

void bubleSort(int * a, int n){   // int * a;定义一个数组指针，方便从主函数传入一个变化长度的数组
    int ix, jx, temp;
    for (int ix=0; ix < n; ix++){
        for (jx=ix+1; jx < n; jx++){
            if (a[jx] < a[ix]){
                temp = a[jx];
                a[jx] = a[ix];
                a[ix] = temp;
            }
        }
    }
}

• STL实现

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;



// 打印元素
void PrintV(vector<int>& v){
    for(auto &e: v){
        cout << e << ' ';
    }
    cout << endl;
}


// 冒泡排序基本版本
void BubbleSort(vector<int>& v){
    int n = v.size();
    for(int i=0; i < n-1; ++i){
        for(int j=0; j < n-1-i; ++j){
            if(v[j] > v[j+1]){
                swap(v[j], v[j+1]);
            }
        }
    }
}

// 函数模板来实现
template<typename T>   // 模板头
void BubbleSort1(T arr[], int len){
    for(int i=0; i < len-1; ++i){
        for(int j=0; j < len-1-i; ++j){
            if(arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}



// 冒泡排序优化版本
void BubbleSort2(vector<int>& v){
    int n = v.size();
    bool flag = false;  // flag标志：表示序列是否有序
    for(int i=0; i < n-1 && !flag; ++i){
        flag = true;
        for(int j=0; j < n-1-i; ++j){
            if(v[j] > v[j+1]){
                flag = false;  // 发生交换则仍非有序
                swap(v[j], v[j+1]);
            }
        }
    }
}



// 自己实现两个数的交换
void Swap(int& a, int& b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}


int main(){
    vector<int> v{7, 30, 16, 4, 1, 2, 9};
    cout << "冒泡排序前: ";
    PrintV(v);
    BubbleSort2(v);
    cout << "冒泡排序后: ";
    PrintV(v);
    return 0;
}

三、结果

结果.png

四、冒泡排序时间复杂度总结：

• 平均时间复杂度：O(n**2)
• 最好情况：O(n)
• 最坏情况：O(n**2)
• 空间复杂度：O(1)
• 稳定性：稳定