排序算法 | 冒泡排序(含C++/Python代码实现)

导言

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

排序

排序的定义

假设含有n个记录的序列为{r1,r2,...,rn},其相应的关键字分别是{k1,k2,...,kn},需要确定1,2,...,n的一种排列p1,p2,...,pn,使其相应的关键字满足kp1<=kp2<=...<=kpn 非递减(或非递增)的关系,即使得序列成为一个按关键字有序的序列{rp1,rp2,...,rpn},这样的操作就称为排序[1]。

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

排序的稳定性

假设ki=kj(1<=i《=n,1<=j<=n,i!=j),且在排序前的序列中ri领先于rj(即i<j)。

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

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

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b前面;
  • 不稳定:如果a原本在b前面,而a=b,排序之后a可能在b的后面。

时间和空间复杂度

  • 时间复杂度:对排序数据的总的操作次数。反应当n变化时,操作次数呈现什么规律
  • 空间复杂度:算法在计算机内执行时所需要的存储空间的容量,它也是数据规模n的函数。

常见的排序算法

冒泡排序(Bubble Sort)

基本思想

比较相邻的两个元素,将值大的元素交换到右边(降序则相反)

步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤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, 7, 1, 6, 2},升序排序

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

第一次循环:

第一次比较5和4,5>4,交换位置:{4,5,7,1,6,2}

第二次比较5和7,5

第三次比较7和1,7>1,交换位置:{4,5,1,7,6,2}

第四次比较7和6,7>6,交换位置:{4,5,1,6,7,2}

第五次比较7和2,7>2,交换位置:{4,5,1,6,2,7}

第一次循环完成结果:{4,5,1,6,2,7}

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

第二次循环:

第一次比较4和5,4

第二次比较5和1,5>1,交换位置:{4,1,5,6,2,7}

第三次比较5和6,5

第四次比较6和2,6>2,交换位置:{4,1,5,2,6,7}

第五次比较6和7,6

第二次循环完成结果:{4,1,5,2,6,7}

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

第三次循环:

第一次比较4和1,4>1,交换位置:{1,4,5,2,6,7}

第二次比较4和5,4

第三次比较5和2,5>2,交换位置:{1,4,2,5,6,7}

第四次比较5和6,5

第五次比较6和7,6

第三次循环完成结果:{1,4,2,5,6,7}

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

第四次循环:

第一次比较1和4,1

第二次比较4和2,4>2,交换位置:{1,2,4,5,6,7}

第三次比较4和5,4

第四次比较5和6,5

第五次比较6和7,6

第三次循环完成结果:{1,2,4,5,6,7}

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

第五次循环:

第一次比较1和2,1

第二次比较2和4,2

第三次比较4和5,4

第四次比较5和6,5

第五次比较6和7,6

第三次循环完成结果:{1,2,4,5,6,7}

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

复杂度分析

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

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

代码实现

  • C++代码
  1. /* Summary: 冒泡排序
  2. * Author: Amusi
  3. * Date: 208-05-27
  4. *
  5. * Reference:
  6. * http://en.wikipedia.org/wiki/Bubble_sort
  7. * https://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
  8. * https://zhuanlan.zhihu.com/p/37077924
  9. *
  10. * 冒泡排序说明:比较相邻的两个元素,将值大的元素交换到右边(降序则相反)
  11. *
  12. */
  13. #include <iostream>
  14. // 冒泡函数
  15. namespace alg{
  16. template<typename T>
  17. static void BubbleSort(T list[], int length)
  18. {
  19. #if 1
  20. // 版本1:两层for循环
  21. for (int i = 0; i < length-1; ++i)
  22. {
  23. for (int j = 0; j < length - i -1; ++j)
  24. {
  25. // 两两相邻元素比较大小,从小到大排序
  26. // if (list[j] < list[j + 1]) : 从大到小排序
  27. if (list[j] > list[j + 1])
  28. {
  29. int temp = list[j + 1];
  30. list[j + 1] = list[j];
  31. list[j] = temp;
  32. }
  33. }
  34. }
  35. #else
  36. // 版本2:while+一层for循环
  37. bool swapped = false;
  38. while (!swapped)
  39. {
  40. swapped = true;
  41. for (int i = 0; i < length - 1; ++i)
  42. {
  43. // 两两相邻元素比较大小,从小到大排序
  44. // if (list[j] < list[j + 1]) : 从大到小排序
  45. if (list[i] > list[i + 1])
  46. {
  47. int temp = list[i + 1];
  48. list[i + 1] = list[i];
  49. list[i] = temp;
  50. }
  51. swapped = false;
  52. }
  53. length--;
  54. }
  55. #endif
  56. }
  57. }
  58. using namespace std;
  59. using namespace alg;
  60. int main()
  61. {
  62. int a[8] = { 5, 2, 5, 7, 1, -3, 99, 56 };
  63. BubbleSort<int>(a, 8);
  64. for (auto e : a)
  65. std::cout << e << " ";
  66. return 0;
  67. }
  • Python代码
  1. ''' Summary: 冒泡排序
  2. * Author: Amusi
  3. * Date: 208-05-27
  4. *
  5. * Reference:
  6. * http://en.wikipedia.org/wiki/Bubble_sort
  7. * https://github.com/xtaci/algorithms/blob/master/include/bubble_sort.h
  8. * https://zhuanlan.zhihu.com/p/37077924
  9. *
  10. * 冒泡排序说明:比较相邻的两个元素,将值大的元素交换到右边(降序则相反)
  11. *
  12. '''
  13. def BubbleSort(array):
  14. lengths = len(array)
  15. for i in range(lengths-1):
  16. for j in range(lengths-1-i):
  17. if array[j] > array[j+1]:
  18. array[j+1], array[j] = array[j], array[j+1]
  19. return array
  20. array = [1,3,8,5,2,10,7,16,7,4,5]
  21. print("Original array: ", array)
  22. array = BubbleSort(array)
  23. print("BubbleSort: ", array)

参考

1 http://baijiahao.baidu.com/s?id=1585931471155461767&wfr=spider&for=pc

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

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

原文发布于微信公众号 - CVer(CVerNews)

原文发表时间:2018-07-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

C/C++ sizeof(上)

sizeof是C/C++中的一个操作符(operator),其作用是返回一个对象或者类型所占的内存字节数,使用频繁,有必须对其有个全面的了解。

751
来自专栏java工会

Java基础第一阶段知识点,招实习的面试官都在问这些

2119
来自专栏技术墨客

JVM与字节码——2进制流字节码解析 原

本位将详细介绍字节码的2进制结构和JVM解析2进制流的规范。规范对字节码有非常严格的结构要求,其结构可以用一个JSON来描述:

882
来自专栏IT可乐

Java关键字(四)——final

  对于Java中的 final 关键字,我们首先可以从字面意思上去理解,百度翻译显示如下:

893
来自专栏Java 源码分析

Java面向对象基础

     面向对象一直是一种很流行的思想,他的精髓也就在于他的三大特性:封装,继承和多态。本文就在这三个方面简单的谈一谈Java的面向对象基础。 1.封装:  ...

3395
来自专栏java工会

Java基础第一阶段知识点,招实习的面试官都在问这些

a) 答:Java源文件被编译成字节码的形式,无论在什么系统环境下,只要有java虚

1201
来自专栏Java帮帮-微信公众号-技术文章全总结

第十三天 面向对象-final static 匿名对象内部类包代码块【悟空教程】

1394
来自专栏数据科学与人工智能

【Python环境】12道 Python面试题总结

1、Python是如何进行内存管理的? Python的内存管理主要有三种机制:引用计数机制、垃圾回收机制和内存池机制。 a. 引用计数 当给一个对象分配一个新名...

2485
来自专栏程序员互动联盟

【专业技术】你必须注意的11个C++要点

下面的这些要点是对所有的C++程序员都适用的。我之所以说它们是最重要的,是因为这些要点中提到的是你通常在C++书中或网站上无法找到的。如:指向成员的指针,这是许...

2735
来自专栏C/C++基础

如何禁止函数的传值调用

按照参数形式的不同,C++应该有三种函数调用方式:传值调用、引用调用和指针调用。对于基本数据类型的变量作为实参进行参数传递时,采用传值调用与引用调用和指针调用的...

681

扫码关注云+社区