数据结构&算法实践—【排序|交换排序】鸡尾酒排序

排序»交换排序»鸡尾酒排序

List:

0.概念+伪代码+示例分析
1.鸡尾酒排序实现
2.Question

0. start

基本概念:

维基百科http://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F

伪代码：

function cocktail_sort(A: list[1..n]){
    for i from 0 to n/2{
        for f from i to (n-i-2){
            if(A[a] > A[a+1])
                swap(A[a],A[a+1])
        }
        for b from  (n-i-2) to (i+1){
            if(A[b] < A[b-1])
                swap(A[b],A[b-1]
        }
    }
}

鸡尾酒排序是冒泡排序的变种——双向冒泡排序

从伪代码可以看到，每一轮循环，从前到后一次正向冒泡，之后从后往前再进行一次逆向冒泡(每一轮存在两个数被排序)

可以看到的表现是两边先排序好，逐渐向中间有序

示例：

->[50, 10, 30, 20, 60, 40, 1]
-> [10, 30, 20, 50, 40, 1, 60]  第一轮正向
-> [1, 10, 30, 20, 50, 40, 60]  第一轮逆向
-> [1, 10, 20, 30, 40, 50, 60]  第二轮正向
-> [1, 10, 20, 30, 40, 50, 60]  第二轮逆向，无交换，结束

详细比较过程:

[50, 10, 30, 20, 60, 40, 1]

第一轮 正向

l->r  cmp 50 10
change [10, 50, 30, 20, 60, 40, 1]
l->r  cmp 50 30
change [10, 30, 50, 20, 60, 40, 1]
l->r  cmp 50 20
change [10, 30, 20, 50, 60, 40, 1]
l->r  cmp 50 60
l->r  cmp 60 40
change [10, 30, 20, 50, 40, 60, 1]
l->r  cmp 60 1
change [10, 30, 20, 50, 40, 1, 60]

第一轮 逆向

r->l  cmp 1 40
change [10, 30, 20, 50, 1, 40, 60]
r->l  cmp 1 50
change [10, 30, 20, 1, 50, 40, 60]
r->l  cmp 1 20
change [10, 30, 1, 20, 50, 40, 60]
r->l  cmp 1 30
change [10, 1, 30, 20, 50, 40, 60]
r->l  cmp 1 10
change [1, 10, 30, 20, 50, 40, 60]

[1, 10, 30, 20, 50, 40, 60]

第二轮 正向

l->r  cmp 10 30
l->r  cmp 30 20
change [1, 10, 20, 30, 50, 40, 60]
l->r  cmp 30 50
l->r  cmp 50 40
change [1, 10, 20, 30, 40, 50, 60]

第二轮 逆向

r->l  cmp 40 30
r->l  cmp 30 20
r->l  cmp 20 10
[1, 10, 20, 30, 40, 50, 60] (上一轮逆向无交换，结束排序)
[1, 10, 20, 30, 40, 50, 60]

本数组共比较18次，而使用带标志冒泡排序需要21次

1. start

实现代码

:::python
def cocktail_sort(l):
    size = len(l)
    sign = 1  #用于判断上轮排序是否存在数据交换
    for i in range(size / 2):
        if sign:
            sign = 0
            #正向，冒泡   从   i 到    对称的位置-1
            for j in range(i, size - 1 - i):
                if l[j] > l[j + 1]:
                    l[j], l[j + 1] = l[j + 1], l[j]
            #逆向，冒泡  从正向排完最大数的前一个开始，到  i
            for k in range(size - 2 - i, i, -1):
                if l[k] < l[k - 1]:
                    l[k], l[k - 1] = l[k - 1], l[k]
                    sign = 1  #若是逆向存在交换，代表还没排序完成，否则，排序完成
        else:
            break
    print l

改换成while

:::python
def cocktail_sort2(l):
    size = len(l)
    sign = 1  #用于判断上轮排序是否存在数据交换
    i = 0
    while sign:
    sign = 0
    for j in range(i, size - 1 - i):
        if l[j] > l[j + 1]:
            l[j], l[j + 1] = l[j + 1], l[j]
    for k in range(size - 2 - i, i, -1):
        if l[k] < l[k - 1]:
            l[k], l[k - 1] = l[k - 1], l[k]
            sign = 1  #若是逆向存在交换，代表还没排序完成，否则，排序完成
    i += 1

也可以维护一个bottom和top，每次bottom+1,top-1

2. start

A.鸡尾酒排序概念，过程描述？

B.最差，平均，最优 时间复杂度？ 最差=平均=O(n^2) 最优=O(n)

C.空间复杂度？

D.是否是稳定排序？

E.存在什么方法可以更优化

F.适用场景，什么情况下最优，什么情况下最差？

—————————————– END ————————————————-

p.s.维基百科的动态排序图很赞&坑爹好几种排序无中文描述，只能啃英文版的百科了，到时候一块贴了