分类： 计算科技

冒泡排序算法的排序过程

（以下排序过程按照大数位于小数右边的规则展开说明，按照大数位于小数左边的规则进行的冒泡排序与此过程类似）

1. 首先进行第 1 次遍历，选取整个队列 (队列长度为 N) 的第 1 个数字 (记为 a)，和紧邻 a 后的数字 (记为 b) 比较大小，如果 a 大于 b, 则交换 a 与 b 的位置，此后，a 继续和紧邻 a 后的数字 c 比较；如果 a 小于 b, 则丢下 a, 拿起 b, 并和紧邻 b 后的后的数字比较大小。经过这一轮比较，当比较到整个队列结束时，一共进行了 N-1 次比较，此时，整个队列中最大的数字排在了整个队列的最后；
2. 现在进行第 2 次遍历，此时只需要遍历除了第 1 次遍历后得到的数列的最后一个数之外的 N-1 个数字，即需要比较 N-2 次，得到整个数列第 2 大的数字排在上一轮排序得到的最大的数字的左边；
3. 依照前面两步所示的规则继续进行第 3, 4, 5, …, N-1 轮循环就完成了整个排序过程。

以数列 [3,2,5,1,2] 为例，冒泡排序的过程如下：

第 1 轮第 1 次比较：[2,3,5,1,2];
第 1 轮第 2 次比较：[2,3,5,1,2];
第 1 轮第 3 次比较：[2,3,1,5,2];
第 1 轮结束：[3,2,1,2,5];
第 2 轮结束：[2,1,2,3,5];
第 3 轮结束：[1,2,2,3,5];
第 4 轮结束：[1,2,2,3,5].

下面这个动图很好的演示了冒泡排序的整个过程：
（该动图使用 VisuAlgo 制作，来自：https://visualgo.net/）

C++ 实现的冒泡排序算法

递归实现

#include <iostream>
using namespace std;

int * mp(int a[], int start, int end){
    if(start<end){
/*
使用start和end这两个变量定义递归的边界条件，
start表示数组的起始位置，end表示数组的结束
位置，每次循环结束时，end都会减1，因此当start
不再小于end的时候，就代表整个数组都被遍历了，
即递归操作完成。
*/
        int temp = 0;
        for(int i = 0; i <= 8; i++){
            if(a[i]>a[i+1]){
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
    end --;
    mp(a,start,end);
    }
    return a;
}

int main(){
    int start = 0;
    int end = 9;
    int a[10] = {7,6,2,1,5,6,4,0,8,5};
    int *p;
    p = mp(a,start,end);

    for(int j = 0; j <=8; j++){
        cout << *(p+j) << " ";
    }
    return 0;
}

运行后输出的结果：

0 1 2 4 5 5 6 6 7
Process returned 0 (0x0)   execution time : 0.085 s
Press any key to continue.

非递归实现

双层 for 循环实现的冒泡排序（无改进）

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    for(int i=0;i<=8;i++){
/*有10个数字的队列首次遍历需要比较9次，之后，
每次遍历需要比较的数字的个数都比上一次少1个。
这层循环用于确定需要遍历的队列的长度。*/
        for(int j=0;j<8-i;j++){
/*从队列第 1 个数字开始，比较到不需要比较的最后
一个数字为止，这层循环用于确定需要比较的具体的
数字。*/
            if(nums[j]>nums[j+1]){
/*如果前一个数大于后一个数，则交换两个数的位置，
把大的数字放到后面。*/
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
    }
    for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    return 0;
}

上面这个程序的时间复杂度为：O(n^2^), 空间复杂度为：O(1).

双层 for 循环实现的冒泡排序（使用位置交换标志位进行改进）

我们首先对上面“双层 for 循环实现的冒泡排序（无改进）”中给出的程序做一些改变，使其能打印出每一轮排序的结果，程序如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    for(int i=0;i<=8;i++){
        for(int j=0;j<8-i;j++){
            if(nums[j]>nums[j+1]){
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
        cout<<i<<"#:"<<" ";
        for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

运行上面的程序后可以得到如下结果：

0#: 6 2 1 5 6 4 0 7 8
1#: 2 1 5 6 4 0 6 7 8
2#: 1 2 5 4 0 6 6 7 8
3#: 1 2 4 0 5 6 6 7 8
4#: 1 2 0 4 5 6 6 7 8
5#: 1 0 2 4 5 6 6 7 8
6#: 0 1 2 4 5 6 6 7 8
7#: 0 1 2 4 5 6 6 7 8
8#: 0 1 2 4 5 6 6 7 8

Process returned 0 (0x0)   execution time : 0.267 s
Press any key to continue.

通过上面的运行结果可以看出第 6 轮循环结束时排序其实已经完成，之后的 7, 8 轮排序得出的结果和第 6 轮排序得出的结果完全一致。我们可以通过在程序中添加“位置交换标志位”来避免无用的排序，即一旦发现某一轮循环结束之后没有任何一个元素的位置发生了改变，就认为此时排序已经完成，不需要进行接下来的排序。
使用“位置交换标志位”改进后的程序如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main(){
    int nums[10]={7,6,2,1,5,6,4,0,8,5};
    int temp=0;
    bool SwapFlag = true;
/*
定义位置交换标志变量
当发生位置交换时置为 true
未发生位置交换时置为 false
*/
    for(int i=0;i<=8&&SwapFlag==true;i++){
            SwapFlag=false;
/*
每开始一轮排序时都将标志位复位
(初始默认本轮不会出现交换)
*/
        for(int j=0;j<8-i;j++){
            if(nums[j]>nums[j+1]){
                SwapFlag=true;
/*
只要在一轮排序中发生了一次交换
则标志位置为 true
*/
                temp = nums[j+1];
                nums[j+1]= nums[j];
                nums[j] = temp;
            }
        }
        cout<<i<<"#:"<<" ";
        for(int z=0;z<=8;z++){
        cout<<nums[z]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

输出结果如下：

0#: 6 2 1 5 6 4 0 7 8
1#: 2 1 5 6 4 0 6 7 8
2#: 1 2 5 4 0 6 6 7 8
3#: 1 2 4 0 5 6 6 7 8
4#: 1 2 0 4 5 6 6 7 8
5#: 1 0 2 4 5 6 6 7 8
6#: 0 1 2 4 5 6 6 7 8
7#: 0 1 2 4 5 6 6 7 8

Process returned 0 (0x0)   execution time : 1.070 s
Press any key to continue.

可以看到，经过改进之后，在使用相同的源代码逻辑和同一组数据的情况下，排序次数减少了 1 次。

更改记录：

1. 2019 年 05 月 29 日 17 时 17 分，在“冒泡排序算法的排序过程”中新增了一张演示冒泡排序的动图（图 1）并添加了有关说明。

EOF

预备知识

指针函数

C++ 中指针函数的基本形式：

函数类型 * 函数名 (参数数据类型 参数1, 参数数据类型 参数 2,...){
    执行体 1;
    执行体 2;
    ...
}

例如下面这个函数就是一个指针函数：

int * a(int b[], int c){
    cout<<"Hello";
    return b;
}

指针函数的返回值是一个指针，在 main() 函数中调用该指针函数的时候，可以使用一个同类型的指针来接收。指针函数的作用之一就是解决一个函数中存在多个返回值的时候，如何返回这多个数值的问题。

静态变量

C++ 中的变量，大致可以分为（该分类不严格，仅供参考）“全局变量”、“局部变量”、“静态变量”、“全局静态变量（或称“静态全局变量”）”、“局部静态变量（或称“静态局部变量”）”和指针变量等。局部变量是存放在内存的堆区的，一旦一个函数执行完毕，则编译器就会自动释放这部分内存，该局部变量也随之消失。全局变量和静态变量都是存放在数据区（也称“全局区”或者“静态区”）的，该区域的内容可以被全局共享，在整个程序结束时，由系统自动释放。

指针变量用来存放指针，而指针就是一块内存的地址，因此，指针变量存放的就是一个内存地址。指针变量也是一个变量，是变量就需要使用内存空间存放，需要使用内存空间就需要分配内存并获取内存地址，因此，指针变量本身也是有内存地址的，存放指针变量的内存地址又指向了它存放的内存地址。指针变量的定义形式一般如下：

基类型 *指针变量名称;

在函数中定义的变量都是局部变量（在一个程序的所有函数之外定义的变量称为“全局变量”），但是我们要返回这个变量供其他函数（例如 main() 函数）使用，这个时候就需要使用“局部静态变量”来达到这个目的。

局部静态变量的定义方法就是在定义的局部变量之前加上 static 关键字。

具体实现方法

C++ 中不允许把一个数组或者多个数值作为一个整体返回，也就是说，对于 C++ 中的任何一个函数， 其返回值只能是 0 个或者 1 个单独的数字，不能是一个数组或者多个数字。不过，我们可以结合使用指针和数组（由于数组在内存中是使用一块连续的区域存储的，因此，只要知道了一个数组中第一个元素的地址并且知道了这个数组的长度，那么就可以找到和处理整个数组）来达到返回多个数值的目的。

概括地说，至少有以下三种方法：

方法一

返回一个指针指向数组中第一个元素的地址，在已知数组中第一个元素的地址和数组长度的情况下，可以唯一确定一个数组。

示例程序如下：

#include <iostream>
using namespace std;

/*
定义一个返回指针的函数用于返回数组
*/
int * ReturnMyArr(){
    static int MyArr[5] = {0,1,2,3,4};
/*
C++ 不支持在函数外面返回局部变量的地址
因此，这里定义为 static 变量
*/

    return MyArr;
}

int main(){
    int *p;
/*
定义一个整数型指针
*/

    p = ReturnMyArr();
/*
将数组的第一个元素值在内存中
的地址赋值给指针变量p
*/

/*
通过指针p打印数组
*/
    for(int i = 0; i < 5; i++){
        cout << *(p+i) << " ";
    }
}

方法二

方法二其实没有返回数组，自然也没有涉及 return, 但是方法二同样可以对数组进行处理，并使 main() 函数获取到处理后得到的新数组。

方法二的主要原理就是把待处理的数组的第一个元素的地址作为参数传入用于处理该数组的函数，被处理后的数组写入到了内存中，main() 函数从内存中读取经过处理后的数组，这样就达到了返回多个数值的效果。

示例程序如下：

#include <iostream>
using namespace std;

/*
把指针变量作为形式参数输入函数
该指针指向的是数组 a[] 中第一
个元素的地址
函数 ReturnMyArr() 的作用是对数
组 a[] 进行操作，操作的结果就写
入到了内存中，可以被 main() 函数
使用，不需要有返回值，因此使
用 void
*/
void ReturnMyArr(int *p){

/*
使用指针逐个指向数组 a[] 的每一
个元素，将她们都赋值为 0
*/
    for(int j=0; j<3; j++){
        *(p + j) = 0;
    }
}

int main(){
    int i = 0;
    int a[3] = {1,2,3};

/*
将数组 a[] 以实参的形式传入函数
ReturnMyArr()
*/
    ReturnMyArr(a);

/*
循环打印
*/
    while(i < 3){
        cout << a[i] << " ";
        i++;
    }
}

运行结果如下：

0 0 0
Process returned 0 (0x0)   execution time : 0.232 s
Press any key to continue.

方法三

这里也可以不借助局部静态变量和指针实现对数组的返回。我们可以把变量定义在 main() 函数中，之后将这些变量作为参数传入指针函数。由于这些变量是定义在 main() 函数中的，因此只要 main() 函数没有结束，即使指针函数结束了，这些参数也不会由于内存回收而被销毁。

示例程序如下：

#include <iostream>
using namespace std;

int * ReturnMyArr(int a[]){
    for(int i = 0; i < 3; i++){
        a[i] = 0;
    }
/*
对数组 a[] 重新赋值
*/

    return a;
}

int main(){
    int a[3] = {1,2,3};
    int *p;
    p = ReturnMyArr(a);

    for(int i = 0; i <= 2; i++){
        cout << *(p+i) << " ";
    }

    return 0;
}

运行结果如下：

0 0 0
Process returned 0 (0x0)   execution time : 0.207 s
Press any key to continue.

如果我们不想改变数组 a[] 的数值，也可以新增一个数组 b[] 用于保存数组 a[] 经过指针函数计算后的结果。

示例程序如下：

#include <iostream>
using namespace std;

int * ReturnMyArr(int a[], int b[]){
    for(int i=0; i <= 2; i++){
        b[i] = a[i];
    }
    return b;
}

int main(){
    int a[3] = {1,2,3};
    int b[3];
    int *p;
    p = ReturnMyArr(a,b);

    for(int i = 0; i <= 2; i++){
        cout << *(p+i) << " ";
    }
    return 0;
}

运行结果如下：

1 2 3
Process returned 0 (0x0)   execution time : 0.194 s
Press any key to continue.