冒泡排序（C++语言描述）

柔情只为你懂 2022-08-05 07:44 186阅读 0赞

**冒泡排序（Bubble Sort）：**一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

**其时间复杂度为：O（n^2）**  
以下是我写的代码及其程序结果，程序用C++写的，因为想回顾以下C++的基本知识，包括类、构造函数、友元等概念在程序中被应用到。  
一直用C语言写程序，渐渐地C++的一些写法都忘了，所以我在复习数据结构的过程中，尝试用C++的思想和语言来写，获益匪浅。  
在写类的过程中，**用构造函数初始化类中定义的私有数组成员时**，也遇到一些问题，包括我所犯的一些错误、原因以及解决办法，在注释中我都标明了。

#include <iostream>
    using namespace std;
    
    const int MAX_SIZE = 10;
    
    class Base{
    private:
        int r[MAX_SIZE];     /**待排序数列存放处**/
        int length;          /**顺序表长度，即数据元素个数**/
    public:
        Base()
        {
            r[0] = 1;
            r[1] = 2;
            r[2] = 0;
            r[3] = 5;
            r[4] = 8;
            r[5] = 9;
            r[6] = 7;
            r[7] = 3;
            r[8] = 6;
            r[9] = 4;
            length = 10;
        }
    /**以下写法会产生错误
        Base()
        {
            r[MAX_SIZE] = {1,2,0,5,8,9,7,3,6,4};
            length = 10;
        }
        这种写法之所以错误的原因在于，只有在数组定义的时候才能这样写；
        当定义结束以后，对数组的初始化，只能一个个循环赋值，或逐个赋值。
        当然也可以这样写：
        private:
        int r[MAX_SIZE]={1,2,0,5,8,9,7,3,6,4};
        但建议不要这样写，这只有在c++11标准里，才会通过编译。
        另一种思路：
        可以定义一个指针，将另外一个数组的地址赋给它。
    **/
        void swap_data(Base &ob,int i,int j);
        void Show(const Base &ob);
        friend int Bubble_Sort0(Base &ob);  /**这里一定要设为友元函数，不然该函数无法调用Base类的私有数据成员**/
        friend int Bubble_Sort(Base &ob);
        friend int Bubble_Sort2(Base &ob);
    };
    
    void Base::swap_data(Base &ob,int i,int j)  /**用于交换两个数据**/
    {
        int temp;
        temp = ob.r[i];
        ob.r[i] = ob.r[j];
        ob.r[j] = temp;
    }
    
    void Base::Show(const Base &ob)         /**用于输出数据**/
    {
        int i;
        for(i = 0;i < ob.length;i++)
            cout << ob.r[i] << ' ';
        cout << endl;
    }
    
    int Bubble_Sort0(Base &ob)              /**简单排序法：冒泡排序的初级版**/
    {
        int i,j;
        for(i = 0;i < ob.length;i++)
        {
            for(j = i+1;j < ob.length;j++)  /**注意这里 j = i+1; 不能写j = 0;不然会将降序的排法，又重新颠倒过来**/
            {
                if(ob.r[i] < ob.r[j])       /**让大的放前面，第一个和后面每一个比较，一轮循环后，这一轮第一个会是最大的**/
                    ob.swap_data(ob,i,j);
            }
        }
        return 0;
    }
    
    int Bubble_Sort(Base &ob)              /**冒泡排序正宗版**/
    {
        int i,j;
        for(i = 1;i < ob.length;i++)       /**只需length-1次就好了**/
        {
            for(j = ob.length-1;j >= i;j--)
            {
                if(ob.r[j-1] > ob.r[j])    /**让小的放前面，相邻两个两两交换**/
                    ob.swap_data(ob,j-1,j);
            }
        }
        return 0;
    }
    
    int Bubble_Sort2(Base &ob)              /**冒泡排序升级版**/
    {
        int i,j;
        bool flag = true;                   /**增加一个关键字，用于标记**/
        for(i = 1;i < ob.length && flag;i++)/**只需length-1次就好了**/
        {
            flag = false;                   /**当flag为false，即没有进行交换，也就是当这一轮都没有进行交换，说明之前那轮排序已经将数列顺序都排好了**/
            for(j = ob.length-1;j >= i;j--) /**因而flag为false可以忽略后面的无用操作，从而提升效率**/
            {
                if(ob.r[j-1] < ob.r[j])     /**让大的放前面，相邻两个两两交换**/
                {
                    ob.swap_data(ob,j-1,j);
                    flag = true;            /**只有进行了交换，flag才会置为true**/
                }
            }
        }
        return 0;
    }
    
    int main()
    {
        Base ob1;
        cout << "排序前的数据为:" << endl;
        ob1.Show(ob1);
    
        Bubble_Sort0(ob1);
        cout << "简单排序后的数据为（大的放前面）:" << endl;
        ob1.Show(ob1);
    
        Bubble_Sort(ob1);
        cout << "冒泡排序后的数据为（小的放前面）:" << endl;
        ob1.Show(ob1);
    
        Bubble_Sort2(ob1);
        cout << "升级版冒泡排序后的数据为（大的放前面）:" << endl;
        ob1.Show(ob1);
    
        return 0;
    }

![这里写图片描述][20150612140853028]  
/*点滴积累，我的一小步O(∩\_∩)O~*/

[20150612140853028]: /images/20220805/82e3990843e841aabe3b75f5ff1a1fab.png