推荐|排序——冒泡排序（Bubble sort）

定义

冒泡排序是一种较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动画演示

假设我们有一个数列，初始值为[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，使用冒泡排序过程如下图所示。

从这个动画过程中，我们可以看到：

第一次冒泡排序完成后，最大值50到达数列的最右边。

第二次冒泡排序完成后，次大值48到达数列的次右边。

以此类推。

算法分析

关键字比较次数记为C，记录移动次数记为M。

时间复杂度

假设数列本身是正序的，那么一趟扫描即完成排序。 $C_{min}=n-1$ ， $M_{min}=0$ 。所需的那么最好的时间复杂度为 $O(n)$ 。

假设数列本身是反序的，需要 $n-1$ 趟排序，每趟排序要进行 $n-i$ 次关键字比较 $（i\leqslant i\leqslant n-1）$ （ $1\leqslant i\leqslant n-1$ ），且每次比较都必须移动记录三次来达到交换记录位置。在这个情况下，比较和移动次数均达到最大值： $C_{max}=\frac{n\ast (n-1)}{2}=O(n^{2})$ ， $M_{max}=\frac{3\ast n\ast (n-1)}{2}=O(n^{2})$ 。所需的那么最坏的时间复杂度为 $O(n^{2})$ 。

综上所述，冒泡排序总的平均时间复杂度为 $O(n^{2})$ 。

空间复杂度

每次移动记录的时候，需要一个附件的空间。所以，冒泡排序的空间复杂度为 $O(1)$ 。

算法稳定性

冒泡排序算法是稳定的。

因为，冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变。

代码实现

C语言


#define ARR_LEN 255 /*数组长度上限*/
#define elemType int /*元素类型*/
 
void bubbleSort (elemType arr[], int len) {
    elemType temp;
    for (int i=0; i-1; i++) {
        /* 外循环为排序趟数，len个数进行len-1趟 */
        for (int j=0; j-1-i; j++) { 
            /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { 
                /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

C++


using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len) {
    T temp;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Python3


def bubble_sort(nums):
    for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums) - i - 1):  # j为列表下标
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

JAVA


public static void bubbleSort(int []arr) {
    for(int i =1;i
        for(int j=0;j
            if(arr[j]>arr[j+1]) {
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }    
    }
}

算法掌握要求

在OI比赛或者程序设计中，必须掌握冒泡算法，因为这是最简单、最基本的排序算法。

例题

题目链接

http://47.110.135.197/problem.php?id=1035。

题目

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入

有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。

输出

一个数据，是最少的旋转次数。

样例输入


4
4 3 2 1

样例输出

题目分析

从题目可知，就是查找逆序对。输入为4 3 2 1，可以知道，逆序对有（4, 3）、（4, 2）、（4, 1）、（3, 2）、（3, 1）和（2, 1），合计一共6对，所以答案为6。

解决方案

可以利用冒泡排序，对输入数据进行排序，记录调整顺序的次数，即为本题结果。

数据集

由于本题是一个模板题，所以数据量比较小，大小为1,000。使用冒泡排序，时间复杂度为 $O(n^{2})$ ，可以完成任务。

如果数据集进一步扩大，那么冒泡排序就力不从心了，主要是因为时间复杂度太大，必须使用时间复杂度为 $O(nlogn)$ 的稳定排序算法，比如归并排序。

参考代码


#include 
using namespace std;
 
int bubble_sort(T arr[], int len) {
    int ans = 0;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                ans++;
            }
        }
    }
    return ans;
}
 
const int MAXN = 1e3;
int data[MAXN] = {};
 
int main() {
    int n;
    cin >> n;
    
    for (int i=0; i
        cin >> data[i];
    }
 
    cout << bubble_sort(data, n) << endl;
 
    return 0;
}

定义