数据结构&算法实践—鸡尾酒排序，,未经作者许可，禁止转载！
数据结构&算法实践—鸡尾酒排序，,未经作者许可，禁止转载！
本文作者： 编橙之家 - wklken 。未经作者许可，禁止转载！欢迎加入编橙之家 专栏作者。
数据结构&算法实践——Python
第一部分列表(目录主要来自于维基百科)
模块一：经典排序实现
交换排序法
冒泡排序 |鸡尾酒排序 |奇偶排序 |梳排序 |地精排序(gnome_sort) |Bogo排序|快速排序
选择排序法
选择排序 | 堆排序
插入排序法
插入排序 | 希尔排序 | 二叉查找树排序 | Library sort | Patience sorting
归并排序法
归并排序 | Strand sort
非比较排序法
基数排序 | 桶排序 | 计数排序 | 鸽巢排序 | Burstsort | Bead sort
其他
拓扑排序 | 排序网络 | Bitonic sorter | Batcher odd-even mergesort | Pancake sorting
低效排序法
Bogosort | Stooge sort
模块二：经典查找
模块三：数据结构(后续补充完整，树和图是大头，包含很多分类和经典算法)
线性表 队列 栈 堆 树 图
————————————–目录 END————————————————
写在前面
毕业迄今也接近一年了，发现很多学校的东西似乎生疏了.
最近重新拿起数据结构，算法导论，离散数学，决定用代码敲些东西，权当复习
大部分的地方我只会给出例子和具体的代码实现，顺带给出一些百科的链接，概念和理论性的东西网上都有，不赘述了 之所以选择用python来写，主要是python的可读性非常好，即使不写注释，也能很轻松读懂.
我把这个过程大概切成三个部分：
1.经典数据结构和算法的实现
实现基本的经典算法，包括经典排序，经典查找，索引等，基本实现及改进
实现基本的数据结构，包括线性表，队列，栈，堆，树，图等，包含扩展
使用实现类似Java的数据结构，至始至终都认为java的api最为优美，使用Python实现之，包括Map,List,Set等，提供相同的API，同时希望会循序渐进，先用简单直观的方法实现，给出优化，涉及的知识主要是python面向对象，继承，重写内置方法，封装，（要对Python和java数据结构实现的底层源码有了解，需要看源代码）
2.笔试题面试题数据结构和算法实现
笔试&面试题的python处理
使用Python搞定笔试题&面试题中出现的算法和数据结构题目
包含大规模数据处理的详细例子
3.challenge
挑战一些大个的东西，深入实现一些较为复杂的算法
不罗嗦，先列下目录，已经写完一部分了，逐步发出来，更新目录(挪到前头去了) 先列这些，逐渐补充.
每天上完班回来，啃这堆砖头，然后敲出来，累却充实.
敲代码，调试代码其实是一件十分快乐的事情
My daytime job is SDET,平时敲自己喜欢的代码的时间并不会太多，业余时间有限
但做事贵善始善终，会坚持搞完的哈! The End!
wklken@yeah.net
2012-05-10
排序>>交换排序>>鸡尾酒排序
List:
0.概念+伪代码+示例分析 1.鸡尾酒排序实现 2.Question
- 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次
- start
实现代码
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
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
- start
A.鸡尾酒排序概念，过程描述？
B.最差，平均，最优 时间复杂度？
最差=平均=O(n^2) 最优=O(n)
C.空间复杂度？
D.是否是稳定排序？
E.存在什么方法可以更优化
F.适用场景，什么情况下最优，什么情况下最差？
—————————————– END ————————————————-
p.s.维基百科的动态排序图很赞&坑爹好几种排序无中文描述，只能啃英文版的百科了，到时候一块贴了
打赏支持我写出更多好文章，谢谢！
打赏作者
打赏支持我写出更多好文章，谢谢！
任选一种支付方式
相关内容
- 暂无相关文章
评论关闭