C++ 冒泡排序法

zltzlt

冒泡排序

冒泡排序的基本原理是对存放原始数据的数组，按从前往后的方式进行扫描。

当发现相邻两个数组的次序与排序要求的大小次序不符合时，就将两个元素互换。

冒泡排序原理

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
• 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 重复步骤 1~3，直到排序完成。
  

冒泡排序例题

输入 n 个 int 类型的数（n <= 100），将它们按照从小到大的顺序输出。

输入为两行，第一行为 n，表示 n 个数；第二行为待排序的 n 个数。
输出为一行，即按照从小到大的顺序排列好的 n 个数。

我的程序如下：

// File: sort.cpp
// 冒泡排序算法

#include <iostream>
using namespace std;

int main()
{
    int a[100] = {}, n, i, ncopy;
    cin >> n;
    ncopy = n - 1;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    while (true)
    {
        int flag = 1, temp;
        for (i = 0; i < ncopy; i++)
        {
            if (a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                flag = 0;
            }
        }
        ncopy--;
        if (flag)
            break;
    }
    for (i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

冒泡排序总结

排序算法有很多，冒泡排序只是其中一种比较简单的排序方法。

冒泡排序是最稳定的一种排序方法。

冒泡排序法的性能一般，平均时间复杂度为 O(n²)。