C++ 冒泡排序法

zltzlt

冒泡排序

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

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

冒泡排序原理

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

冒泡排序例题

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

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

我的程序如下：

1. // File: sort.cpp
   
2. // 冒泡排序算法
   
3. 
   
4. #include <iostream>
   
5. using namespace std;
   
6. 
   
7. int main()
   
8. {
   
9.     int a[100] = {}, n, i, ncopy;
   
10.     cin >> n;
    
11.     ncopy = n - 1;
    
12.     for (i = 0; i < n; i++)
    
13.     {
    
14.         cin >> a[i];
    
15.     }
    
16.     while (true)
    
17.     {
    
18.         int flag = 1, temp;
    
19.         for (i = 0; i < ncopy; i++)
    
20.         {
    
21.             if (a[i] > a[i + 1])
    
22.             {
    
23.                 temp = a[i];
    
24.                 a[i] = a[i + 1];
    
25.                 a[i + 1] = temp;
    
26.                 flag = 0;
    
27.             }
    
28.         }
    
29.         ncopy--;
    
30.         if (flag)
    
31.             break;
    
32.     }
    
33.     for (i = 0; i < n; i++)
    
34.     {
    
35.         cout << a[i] << " ";
    
36.     }
    
37.     return 0;
    
38. }

复制代码

冒泡排序总结

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

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

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