算法和数据结构2.1冒泡排序
2019-07-27 本文已影响0人
数字d
冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根根据结果交换两个数字的位置”这一操作的算法。
在这一操作过程中，数字会像泡泡一样，慢慢的从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”。
比如对如下的数组中的数字进行排序。
第一趟
[5, 9, 3, 1, 2, 8, 4, 7, 6 ]
第一次从序列的右侧比较6 和 7 的大小，将小的值放在左侧
第一次比较结果是：
[5, 9, 3, 1, 2, 8, 4, 6 ,7 ]
第二次是用6个4进行比较，结果是：
[5, 9, 3, 1, 2, 8, 4，6 ,7 ]
第三次次是用6个8进行比较，结果是：
[5, 9, 3, 1, 2, 4, 8，6 ,7 ]
....
....
第一趟排序结束：
[1,5, 9, 3, 2, 4, 8，6 ,7 ]
最左边数字已经归为。
第二趟，重复以上步骤
第二趟结束时候，结果：
[1,2, 5, 9, 3, 4, 6，8 ,7 ]
排序中 ....
排序结束
[1,2,3,4,5,6,7,8,9]
这里冒泡的操作可以反着来，就是说，从左到右开始比较，比较出来的最大值放在右侧。
时间：
在冒泡排序中，n个数据，第一趟需要比较n-1次，第二趟需要比较 n-2 次, ...第n-1趟需要比较1次。因此，总的比较次数为恒定值约等于 n2 / 2 次；
这个值和输入序列的杂乱顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设某种极端的情况，输入数据正好是从小到大的顺序，那么不需要任何操作。
而另一种极端情况是，输入数据正好是逆序的，那么每次比较之后都要进行交换位置操作，因此，冒泡排序的时间复杂度为O(n2)
