每日一题之冒泡排序

冒泡排序

1、冒泡排序原理

冒泡排序就是一种交换排序，最核心的思想就是冒泡，把数组中最大的那个数字往上冒，但是冒泡的过程中只能和数组中与之相邻的元素进行冒泡。
冒泡的过程中，就是两个相邻的元素进行比较，将数字较大（较小）的元素交换到最右边（左边），每次只能进行相邻的两个元素之间的替换，然后依次后移，进行下两个元素之间的替换，由此从0到n-1次两两元素之间的替换。重复扫描待排序序列，并比较每一对相邻的元素，当该对元素顺序不正确时进行交换。一直重复这个过程，直到没有任何两个相邻元素可以交换，就表明完成了排序。

2、冒泡排序的步骤

临时定义一个数组[4,1,3,7,5]，按照从小到大进行排序，来模拟演示每一次的排序过程

• 第一轮排序，此时整个序列中的元素都位于待排序序列，依次扫描每对相邻的元素，并对顺序不正确的元素对交换位置。

1. 第一次比较：4和1进行比较，4比1大，则新序列变成[1,4,3,7,5]
2. 第二次比较：4和3进行比较，4比3大，则新序列变成[1,3,4,7,5]
3. 第三次比较：4和7进行比较，此时7比4大，则序列不变，仍为[1,3,4,7,5]
4. 第四次比较：7和5进行比较，7比5大，则新序列变成[1,3,4,5,7]

   经过第一轮冒泡排序，从待排序序列中找出了最大数 7，并将其放到了待排序序列的尾部，并入已排序序列中。

• 第二轮排序，此时待排序序列只包含前 4 个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置。

1. 第一次比较：1和3进行比较，此时3比1大，则序列不变，仍为[1,3,4,5,7]
2. 第二次比较：3和4进行比较，此时4比3大，则序列不变，仍为[1,3,4,5,7]
3. 第三次比较：4和5进行比较，此时5比4大，则序列不变，仍为[1,3,4,5,7]

   经过第二次冒泡排序，从待排序序列中找到了最大数 5，并将其放到了待排序序列的尾部，并入已排序序列中。

• 第三轮排序，此时待排序序列只包含前 3 个元素，一次扫描每对相邻元素，对顺序不正确的元素对交换位置。

1. 第一次比较：1和3进行比较，此时3比1大，则序列不变，仍为[1,3,4,5,7]
2. 第二次比较：3和4进行比较，此时4比3大，则序列不变，仍为[1,3,4,5,7]

   进过三第三次冒泡排序，从待排列序列中找到了最大数 4，并将其放到了待排序序列的尾部，并入到已排序虚了中。

• 第四轮排序，此时待排序列中只包含两个元素[1,3]

1. 第一次比较：1和3进行比较，此时3比1大，则序列不变，仍为[1,3,4,5,7]

当进行第五轮冒泡排序时，由于待排序序列中仅剩 1 个元素，无论再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列

所以最终的比较结果为[1,3,4,5,7]

2、冒泡排序的代码实现

作者能力有限，考虑到自己的基础问题，只能写出来C、C++、Java版本的算法实现

• java

import java.util.Arrays;

public class BubbleSort {

    private static void bubbleSort(int[] nums) {
        boolean hasChange = true;
        for (int i = 0, n = nums.length; i < n - 1 && hasChange; ++i) {
            hasChange = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    hasChange = true;
                }
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 7, 9, 5, 8};
        bubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

• C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

/* 简单版本 */
void bubblesort(vector<int> &vec)
{
    for (int i = 0; i < vec.size() - 1; i++)
    {
        for (int j = 0; j < vec.size() - i - 1; j++)
        {
            if (vec[j] > vec[j + 1])
            {
                swap(vec[j], vec[j + 1]);
            }
        }
    }
}

/* 改进版本 */
void bubblesort1(vector<int> &vec)
{
    for (int i = 0; i < vec.size() - 1; i++)
    {
        bool exchange = false;
        for (int j = 0; j < vec.size() - i - 1; j++)
        {
            if (vec[j] > vec[j + 1])
            {
                swap(vec[j], vec[j + 1]);
                exchange = true;
            }
        }

        if (!exchange)
        {
            break;
        }
    }
}

void printvec(const vector<int> &vec, const string &strbegin = "", const string &strend = "")
{
    cout << strbegin << endl;
    for (auto val : vec)
    {
        cout << val << "\t";
    }

    cout << endl;
    cout << strend << endl;
}

int main(void)
{
    vector<int> vec = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    printvec(vec);

    bubblesort1(vec);

    printvec(vec, "after sort", "");
}

4、冒泡排序的算法分析

通过分析冒泡排序的实现代码可以得知，该算法的最差时间复杂度为O(n2)，最优时间复杂度为O(n)，平均时间复杂度为 O(n2)。

冒泡排序是一种简单的排序算法，它也是一种稳定排序算法。

一般情况下，称某个排序算法稳定，指的是当待排序序列中有相同的元素时，它们的相对位置在排序前后不会发生改变。