数据结构&算法实践—【排序|交换排序】冒泡排序及改进
排序»交换排序»冒泡排序
List:
0.概念+伪代码+示例分析
1.基本冒泡排序
2.冒泡排序改进1
3.冒泡排序改进2——局部冒泡排序
4.Question
- start
基本概念：
维基百科http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
伪代码：(来自百科)
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 1 {
for j from 0 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}
简要排序过程的示例：(基本冒泡排序)
初始数组
[50, 10, 30, 20, 40, 60]
第一轮：
cmp 50 10 -> change [10, 50, 30, 20, 40, 60]
cmp 50 30 -> change [10, 30, 50, 20, 40, 60]
cmp 50 20 -> change [10, 30, 20, 50, 40, 60]
cmp 50 40 -> change [10, 30, 20, 40, 50, 60]
cmp 50 60 -> nochange
第二轮:
[10, 30, 20, 40, 50, 60]
cmp 10 30 -> nochange
cmp 30 20 -> change [10, 20, 30, 40, 50, 60]
cmp 30 40 -> nochange
cmp 40 50 -> nochange
第三轮
[10, 20, 30, 40, 50, 60]
cmp 10 20 -> nochange
cmp 20 30 -> nochange
cmp 30 40 -> nochange
第四轮：
[10, 20, 30, 40, 50, 60]
cmp 10 20 -> nochange
cmp 20 30 -> nochange
第五轮：
[10, 20, 30, 40, 50, 60]
cmp 10 20 -> nochange
[10, 20, 30, 40, 50, 60]
cmp count 15
即共进行n-1=5轮冒泡，比较次数为 (n-1) + (n-2) + ……+1 =n*(n-1)/2=15
- start
基本冒泡排序python实现:
:::python
#冒泡排序，base
def bubble(l):
print l
for i in range(len(l)-1,0,-1):
#每一轮冒泡，第 i个 元素会是最大的(i<=size-1)
for j in range(i):
#从0到i-1,比较 current 和next,若current > next，对换
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
print l
- start
问题：在基本冒泡排序的示例中，第三轮结束时，其实已经排序完成了，但是还是一直会持续后面几轮的排序，这就带来了无谓的浪费.
改进：加入标志，判断，若是上一轮不存在数据交换，代表上一轮已经是排序的了，退出
比较次数:12
:::python
#改进1: 当某一轮跑完，不存在数据交换时，代表已排序完成，此时退出
def bubble_improve(l):
flag = 1 #初始标志，1
for i in range(len(l)-1,0,-1):
#若是上一轮存在数据交换，继续执行排序
if flag:
flag = 0 #每一轮初始，交换标志为0
for j in range(i):
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
flag = 1 #存在交换，标志置为1
print l
#否则，代表目前序列已经排序完毕了
else:
break
- start
局部冒泡排序：(资料不多，不知道自己理解对不对)
序列[ a b c d ] 冒泡到了b,此时a小于b，比较b c，若是 b 大于 c，交换b c 得到 [ a c b d ]
通常冒泡排序一直往前，继续比较b和d
其实，在完成一次数据交换时(b<->c)，可以反向增加一次比较，(a 和 c) ，若是a>c,再次交换得到[ c a b d] ——反向做一次冒泡
（百度百科有几行….凑合看）
定义：可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序 局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。 由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进 当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序 (查看百度百科，有张对比图)
简而言之，正向冒泡时，若存在数据交换，反向再进行一次冒泡比较。减少了比较次数
why?
假设在第二轮冒泡 到了50 <-> 30
[10, 20, 40, 50, 30, 60]
带标志位冒泡：cmp 50 30 ->change [10, 20, 40, 30, 50, 60] count+=1
第三轮 count+= 4 (10,20) (20,40) (40,30) (40,50)
第四轮count +3 (10,20) (20,30) (30,40) (无数据交换了，退出)
共 8次
局部冒泡: cmp 50 30 ->change [10, 20, 40, 30, 50, 60] count+=1
cmp 40 30 -> change [10, 20, 30, 40, 50, 60] count+=1
第三轮 count+=4(无数据交换了，退出)
共 6次
:::python
#改进2: 局部冒泡排序
def bubble_improve2(l):
print l
flag = 1
scope = len(l)-1
for i in range(scope,0,-1):
if flag:
flag = 0
for j in range(i):
inner_flag = 0 #本次是否存在数据交换标志，每次置空，不复用flag的原因是如果第一次就交换了，会造成不必要的局部冒泡
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
flag = 1
inner_flag = 1
#从前往后的冒泡，j与j+1发生数据交换了,反向冒泡 j-1 j
#若是本轮存在数据交换，局部排序处理 j-1 j j+1，保证是从小到大的
if inner_flag:
if j - 1 > 0:
if l[j-1] > l[j]:
l[j-1], l[j] = l[j],l[j-1]
print l
else:
break
局部冒泡排序一个示例过程：
[50, 10, 30, 20, 40, 60]
cmp 50 10 -> change [10, 50, 30, 20, 40, 60]
cmp 50 30 -> change [10, 30, 50, 20, 40, 60]
cmp 50 20 -> change [10, 30, 20, 50, 40, 60]
inner cmp 30 20
inner change [10, 20, 30, 50, 40, 60]
cmp 50 40 -> change [10, 20, 30, 40, 50, 60]
inner cmp 30 40
cmp 50 60 -> nochange
[10, 20, 30, 40, 50, 60]
cmp 10 20 -> nochange
cmp 20 30 -> nochange
cmp 30 40 -> nochange
cmp 40 50 -> nochange
[10, 20, 30, 40, 50, 60]
- start
仅是贴出来，权当复习，木有答案，后续补充
A.冒泡排序概念，过程描述？
B.最差，平均，最优 时间复杂度？
C.空间复杂度？
D.是否是稳定排序？
E.如何改进？
F.局部冒泡排序原理？
G.适用场景，什么情况下最优，什么情况下最差？
—————————————– END ————————————————-
P.S.
这是第一篇，有什么不对请指正哈，欢迎补充任何问题和答案
白天上班加班(SDET)，夜深敲代码(python,java…….)，会坚持写完的