经典算法学习之------冒泡排序

​
​学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

活动地址：CSDN21天学习挑战赛

一、什么是算法

1. 算法的定义

以下为经典教材《Introduction.to.Algorithms》开篇中的内容。

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

可以看到，任何被明确定义的计算过程都可以称作算法，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。
这样的概括是比较标准和抽象的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。
概括的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果数据描述清楚了，那么算法所做的事情也就清楚了。我们在设计一个算法时也是需要先明确我们有什么和我们要什么，这一点相信大家在后面的文章中会慢慢体会到。

2. 补充的概念

• 数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题（如：排序），使用不同的数据结构来存储数据，对应的算法可能千差万别。所以在整个学习过程中，也会涉及到各种数据结构的使用。
常见的数据结构包括：数组、堆、栈、队列、链表、树等等。

• 算法的效率

在一个算法设计完成后，还需要对算法的执行情况做一个评估。一个好的算法，可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准来确定一个量级，通常会使用到时间复杂度和空间复杂度这两个概念。

• 时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。
对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n) 。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n)) ，其中的O就是代表数量级。
常见的时间复杂度有（由低到高）：O(1)、O( log ⁡ 2 n \log _{2} n log2​n)、O(n)、O( n log ⁡ 2 n n\log _{2} n nlog2​n)、O( n 2 n^{2} n2)、O( n 3 n^{3} n3)、O( 2 n 2^{n} 2n)、O(n!)。

• 空间复杂度

程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如：如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1)。

• 伪代码约定

伪代码是用来描述算法执行的步骤，不会具体到某一种语言，为了表达清晰和标准化，会有一些约定的含义：
缩进：表示块结构，如循环结构或选择结构，使用缩进来表示这一部分都在该结构中。
循环计数器：对于循环结构，在循环终止时，计数器的值应该为第一个超出界限的值。
to：表示循环计数器的值增加。
downto：表示循环计数器的值减少。
by：循环计数器的值默认变化量为1，当大于1时可以使用by。
变量默认是局部定义的。
数组元素访问：通过"数组名[下标]"形式，在伪代码中，下标从1开始（"A[1]“代表数组A的第一个元素）。
子数组：使用”…"来代表数组中的一个范围，如"A[i…j]"代表从第i个到第j个元素组成的子数组。
对象与属性：复合的数据会被组织成对象，如链表包含后继（next）和存储的数据（data）,使用“对象名 + 点 + 属性名”。
特殊值NIL：表示指针不指向任何对象，如二叉树节点无子孩子可认为左右子节点信息为NIL。
return：返回到调用过程的调用点，在伪代码中允许返回多个值。
and和or：与运算和或运算默认短路，即如果已经能够确定表达式结果时，其他条件不会去判断或执行。

二、交换排序

1. 交换排序介绍

交换排序的核心思想是，每次将元素两两比较，如果不满足正确的相对序列（如：较小的应该在前）则进行交换。不断的根据某个规律进行比较和交换，直到全部满足为止，此时也就得到了一个有序的序列。

• 冒泡排序

也称气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换，再进行下一对儿元素的比较。每一趟冒泡后，就会送一个最小的元素达到最上端。在无序区中重复这个过程，直到所有的元素有序。

• 快速排序

快速排序是冒泡排序的改进算法，主要思想是在待排序列中取一个元素（通常为第一个）作为参照，将序列分为两个子序列，比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并得到两个子序列。在子序列中继续执行该步骤，直到子序列的长度为0或1。\

2. 冒泡排序

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

• 输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。

• 算法说明

总结来说，每一趟冒泡排序将会排好一个元素。排序时会（在无序区中）的一端开始元素的扫描，先以最后一个元素为基准，与前一个元素进行比较，如果较小，则交换。如果遇到一个更小的，则不交换，继续向前进行两个相邻元素的比较。按照这样的过程执行后，无序区中最小的元素一定会被交换至最前，被划入有序区，也就排好了一个元素。
不断的在无序区中执行该步骤，如果在某一次比较的过程中没有发生元素的交换，则证明元素都已经有序，可以提前结束整个算法。或者直到无序区中的元素减少到一个时，整个算法结束，此时整个序列应有序。

• 算法流程

注：在进行升序排列时，可以将较小元素逐一向左调整，也可以将较大元素逐一向右调整，降序排列同理。
第一趟冒泡排序：

1. 元素8与元素3进行比较，相对顺序正确，不需交换。
2. 元素3与元素2进行比较，相对顺序正确，不需交换。
3. 元素2与元素4进行比较，相对顺序错误，需要交换。
4. 元素2与元素5进行比较，相对顺序错误，需要交换。
5. 元素2排好，有序区元素个数为1，无序区元素个数为4。

第二趟冒泡排序：

1. 元素8与元素3进行比较，相对顺序正确，不需交换。
2. 元素3与元素4进行比较，相对顺序错误，需要交换。
3. 元素3与元素5进行比较，相对顺序错误，需要交换。
4. 元素3排好，有序区元素个数为2，无序区元素个数为3。

第三趟冒泡排序：

1. 元素8与元素4进行比较，相对顺序正确，不需交换。
2. 元素4与元素5进行比较，相对顺序错误，需要交换。
3. 元素4排好，有序区元素个数为3，无序区元素个数为2。

第四趟冒泡排序：

1. 元素8与元素5进行比较，相对顺序正确，不需交换。
2. 元素5排好，有序区元素个数为4，无序区元素个数为1。
3. 无序区元素个数为1，算法结束。

3. 伪代码

for i = 1 to n-1
    change = 0
    for j = n downto i + 1
        if A[j] < A[j - 1]
            exchange A[j] with A[j-1]
            change = 1
    if change == 0
        return
1
2
3
4
5
6
7
8

由于每趟排序会排好一个元素，所以至多需要n-1趟就可以完成排序，由外层循环控制。
如果在某一次比较中，没有发生元素的交换，则证明互相比较的元素都已经相对有序，也就说明无序区中的元素都已排好，算法可以提前结束，使用change变量来进行标记。

三、算法实践

1. 算法实现

• 输入数据（input）：11，34，20，10，12，35，41，32，43，14
• Java源代码

public class BubbleSort {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 调用冒泡排序
        sort(a);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

    private static void sort(int[] a){
        // 外层循环：控制排序的总趟数
        for(int i = 0;i < a.length - 1;i++){
            // 定义变量记录是否发生交换
            int change = 0;
            // 内层循环用于元素的两两比较和交换
            for (int j = a.length - 1;j > i;j--){
                // 如果后面的元素较小，则交换
                if (a[j] < a[j-1]){
                    // 两个元素进行交换
                    int tmp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = tmp;
                    // 记录发生了交换
                    change = 1;
                }
            }
            // 如果一次比较中没有发生交换则提前结束
            if (change == 0){
                return;
            }
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

• 执行效果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P219WHY8-1660294979558)(https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/36bfc131f29d466286e547f2111100e3~tplv-k3u1fbpfcp-zoom-1.image)]

• 输出数据（output）：10，11，12，14，20，32，34，35，41，43

2. 时间复杂度

• 最坏的情况

对于冒泡排序来说，最坏的情况依然是元素逆向有序，此时需要执行n-1趟，并且两两元素都需要交换，相当于是最小的元素排在末尾，一路交换到第一位，然后是次最小一路交换至第二位，此时的时间复杂度为：O( n 2 n^{2} n2) 。

• 最好的情况

最好的情况就是元素正向有序的时候，只需要执行一趟排序来确认元素的顺序即可。此时内层循环执行一次，元素两两比较，一共需要进行n-1次，由于没有发生交换，算法提前结束，此时的时间复杂度为：O(n) 。

• 平均境况

综合两种情况，冒泡排序的时间复杂度为O( n 2 n^{2} n2) 。

3. 空间复杂度

算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1) 。