数据结构&算法实践——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 2 3 |
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
伪代码:
1 2 3 4 5 6 7 8 9 10 11 12 |
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] } } } |
鸡尾酒排序是冒泡排序的变种——双向冒泡排序
从伪代码可以看到,每一轮循环,从前到后一次正向冒泡,之后从后往前再进行一次逆向冒泡(每一轮存在两个数被排序)
可以看到的表现是两边先排序好,逐渐向中间有序
示例:
1 2 3 4 5 |
->[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] 第二轮逆向,无交换,结束 |
详细比较过程:
1 |
[50, 10, 30, 20, 60, 40, 1] |
第一轮 正向
1 2 3 4 5 6 7 8 9 10 11 |
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, y">, 20, 50, 40, 60, Β序 |梳排序 |地精排序(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:
基本概念: 维基百科http://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F 伪代码:
鸡尾酒排序是冒泡排序的变种——双向冒泡排序 从伪代码可以看到,每一轮循环,从前到后一次正向冒泡,之后从后往前再进行一次逆向冒泡(每一轮存在两个数被排序) 可以看到的表现是两边先排序好,逐渐向中间有序 示例:
详细比较过程:
第一轮 正向
|