数据结构&算法实践—鸡尾酒排序

数据结构&算法实践——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:

  1. start

基本概念:

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

伪代码:

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

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

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

示例:

详细比较过程:

第一轮 正向

第一轮 逆向

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

第二轮 正向

第二轮 逆向

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

  1. start

实现代码

改换成while

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

  1. start

A.鸡尾酒排序概念,过程描述?

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

C.空间复杂度?

D.是否是稳定排序?

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

F.适用场景,什么情况下最优,什么情况下最差?

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

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

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 2 收藏 1 评论

关于作者:wklken

Pythonista/vimer 个人主页 · 我的文章 · 37 ·   

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部