排序算法 冒泡排序

重磅干货，第一时间送达

导言

排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。排序算法有很多，本文将介绍最经典的排序算法：冒泡排序，并分别利用C++和Python进行实现。

排序

排序的定义

假设含有n个记录的序列为，其相应的关键字分别是，需要确定1,2,...,n的一种排列p1,p2,...,pn，使其相应的关键字满足kp1

简单来说，排序就是使输入的序列变成符合一定规则（关键字）的有序序列（非递减或非递增）。大多数遇到的排序问题都是按数据元素值的大小规则进行排序的问题。所以本文为了方便起见，只讨论数据元素值大小比较的排序问题。

排序的稳定性

假设ki=kj（1

如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；

反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。

简单来概括稳定和不稳定[2]：

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b前面；

不稳定：如果a原本在b前面，而a=b，排序之后a可能在b的后面。

时间和空间复杂度

时间复杂度：对排序数据的总的操作次数。反应当n变化时，操作次数呈现什么规律

空间复杂度：算法在计算机内执行时所需要的存储空间的容量，它也是数据规模n的函数。

常见的排序算法

冒泡排序（Bubble Sort）

基本思想

比较相邻的两个元素，将值大的元素交换到右边（降序则相反）

步骤：

比较相邻的元素。如果第一个比第二个大，就交换它们两个；

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

针对所有的元素重复以上的步骤，除了最后一个；

重复步骤1~3，直到排序完成。

比如有n个元素，那么第一次比较迭代，需要比较n-1次（因为是相邻成对比较，最后一个元素没有与下一个相邻比较的对象，所以是n-1次），此次迭代完成后确定了最后一个元素为最大值；第二次比较迭代，需要比较n-2次，因为第一次迭代已经确定好了最后一个元素，所以不再需要比较；...；第 i次比较迭代，需要比较n-i次，此时确定后面i个元素是有序的较大元素；...；第n-1次比较迭代，需要比较n-(n-1)次，此时完成冒泡排序操作。

时间复杂度：o(n^2) = (n-1)*(n-1)

动图演示：

过程演示：

待排序数组：，升序排序

---------------------------------------

第一次循环：

第一次比较5和4，5>4，交换位置：

第二次比较5和7，5

第三次比较7和1，7>1，交换位置：

第四次比较7和6，7>6，交换位置：

第五次比较7和2，7>2，交换位置：

第一次循环完成结果：

----------------------------------------

第二次循环：

第一次比较4和5，4

第二次比较5和1，5>1，交换位置：

第三次比较5和6，5

第四次比较6和2，6>2，交换位置：

第五次比较6和7，6

第二次循环完成结果：

----------------------------------------

第三次循环：

第一次比较4和1，4>1，交换位置：

第二次比较4和5，4

第三次比较5和2，5>2，交换位置：

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：

----------------------------------------

第四次循环：

第一次比较1和4，1

第二次比较4和2，4>2，交换位置：

第三次比较4和5，4

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：

----------------------------------------

第五次循环：

第一次比较1和2，1

第二次比较2和4，2

第三次比较4和5，4

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：

相信看完上面的演示过程，你对冒泡排序过程及原理有了完全的理解，但是细心的朋友应该会发现其实在第四次循环就已经得到了最终的结果，这么来看第五次循环完全是多余的，于是就有冒泡排序的改进版本：当某一轮循环当中没有交换位置的操作，说明已经排好序了，就没必要再循环了，break退出循环即可。

复杂度分析：

时间复杂度：若给定的数组刚好是排好序的数组，采用改进后的冒泡排序算法，只需循环一次就行了，此时是最优时间复杂度：O(n)，若给定的是倒序，此时是最差时间复杂度：O(n^2) ，因此综合平均时间复杂度为：O(n^2)

空间复杂度：因为每次只需开辟一个temp的空间，因此空间复杂度是：O(1)

代码实现

C++代码

Python代码

参考

2 https://zhuanlan.zhihu.com/p/37077924

3 https://www.cnblogs.com/onepixel/p/7674659.html