小朋友学数据结构（12）：冒泡排序

咱们在学C语言的时候，学过冒泡排序，请参考《小朋友学C语言（26）：冒泡排序》：https://www.jianshu.com/p/587ff823ba5b

《大话数据结构》第九章，讲了一种优化的冒泡排序，完整代码如下：

#include<iostream>
using namespace std;

#define MAX 5
typedef struct
{
    int r[MAX + 1];
    int len;
}seq;


void myswap(seq *x, int i, int j)
{
    int temp = x->r[i];
    x->r[i] = x->r[j];
    x->r[j] = temp;
}


void bubbleSort(seq *x)
{
    bool flag = true;
    // i表示第几轮比较，不表示数组下标
    for (int i = 1; i < x->len && flag; i++)
    {
        cout << "第" << i << "轮排序：";
        flag = false;
        // j表示数组下标，这里是从后往前比较，能同时挪动多个，提高了效率
        // 比如，{3, 2, 1, 5, 4}经过一轮比较变成{1, 3, 2, 4, 5}
        for (int j = x->len - 1; j >= i; j--)
        {
            if (x->r[j] > x->r[j + 1])
            {
                myswap(x, j, j + 1);
                flag = true;
            }
        }

        for(int i = 1; i <= x->len; i++)
        {
            cout << x->r[i] << ' ';
        }
        cout << endl;
    }
}


int main()
{
    cout << "输入数据：";
    seq s;
    for(int i = 1; i <= MAX; i++)
    {
        cin >> s.r[i];
    }
    s.len = MAX;

    bubbleSort(&s);

    cout << "排序结果：";
    for(int i = 1; i <= s.len; i++)
    {
        cout << s.r[i] << ' ';
    }
    cout << endl;

    return 0;
}

运行结果：

输入数据：3 2 1 5 4
第1轮排序：1 3 2 4 5
第2轮排序：1 2 3 4 5
第3轮排序：1 2 3 4 5
排序结果：1 2 3 4 5

加入少儿信息学奥赛QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码

QQ群和公众号.png