2冒泡排序

发布时间: 2024-06-23 00:39:21

思想

以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。

#include <iostream>
using namespace std;
const int MAXN = 10001;
int main() {
    int n, i, j;
    float temp, a[MAXN];
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];
    //int ok = 1;
    for (i = n - 1; i >= 1; i--) {  // 进行n-1轮冒泡
        //if (ok != 2) {
            for (j = 0; j < i; j++) {   // 每轮进行i次的比较
                if (a[j] > a[j + 1]) {  // 相邻两个元素比较，若逆序就交换
                   // ok = 0;
                    swap(a[j], a[j + 1]);  // 交换
                }
            }
         //   if(ok==1) ok==2;
        }
    }
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

添加 ok变量为改进后的排序。

另外一种写法

#include <cstdio>
#include <iostream>
using namespace std;
long n, i, j, t, s, a[10000];
int main() {
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];              // 输入n个车厢号
    for (i = 1; i <= n - 1; i++)  // 冒泡排序另一种写法
        for (j = 1; j <= n - i; j++)
            if (a[j] > a[j + 1])  // 判断车厢号是否逆序
            {
                swap(a[j], a[j + 1]);
                s++;  // 统计车厢旋转的次数
            };

    for (i = 1; i <= n; i++)
        cout<< a[i];  
    cout << s;  // 最少的旋转次数
    return 0;
}

2冒泡排序

思想 ​

思想