若干排序算法的Python实现方法及原理
今天突然想到了一个问题:让你立即把堆排、快排等等排序算法写出来会不会,并且不能犯逻辑错误?
我说:不会,至少需要思考一下,并且可能还需要时间调试。
之前总是觉得,不就是排序算法吗?有什么大不了的?网上、书上一查一大堆。但是换个角度想:1+1 = ? 你会不会?
排序算法应是作为最基本的工具一样,是信手捏来的,所以我把《算法导论》上的几个排序问题看了并且实现了一遍;在此做分享:
冒泡排序:
冒泡排序应该算是比较简单并且使用广泛的排序算法之一了吧,但是它的效率并不怎么高,我们可以先看一下实现:
def bubbleSort(A):
length = len(A);
for i in range(0, length):
for j in range(length - 1, i, -1):
if A[j] < A[j - 1]:
(A[j], A[j - 1]) = (A[j - 1], A[j]);
return A;
a = [5, 0, 1, 3, 6, 2, 4, 9, 12, 11, 18, 20, 7, 8, 19, 13, 14, 17, 16, 10];
a = bubbleSort(a);
print(a);
顾名思义,冒泡排序就像泡沫一样一层一层往上冒,需要一个一个比较;
比较次数(n-1)n / 2, 数据交换次数最坏情况3(n-1)*n/2,最好情况0,所以其时间复杂度O(n^2);
插入排序:
def insertionSort(A):
for i in range(1, len(A)):
key = A[i];
j = i - 1;
while (j >= 0) and (A[j] > key):
A[j + 1] = A[j];
j = j - 1;
A[j+1] = key;
return A;
a = [5, 0, 1, 3, 6, 2, 4, 9, 12, 11, 18, 20, 7, 8, 19, 13, 14, 17, 16, 10];
a = insertionSort(a);
print(a);
要理解插入排序,可以想象打扑克的时候是怎么拿牌的,我们摸一张牌,然后从左往右(或从右往左)按顺序比较,再把牌插入相应位置,插入排序就是这种思想。
时间复杂度O(n^2)
归并排序:
记得大二学习《数据结构》第一次写这个算法的时候想了好久,因为使用递归的思想,有些地方总是转不过弯来。
def merge(A):
length = len(A);
if length <= 1 : return A;
n1 = length / 2;
n2 = length - n1;
L = [];
R = [];
for i in range(0, n1):
L.append(A[i]);
for i in range(0, n2):
R.append(A[n1 + i]);
if n1 > 1 : merge(L);
if n2 > 1 : merge(R);
i = 0;
j = 0;
for k in range(0, length):
if L[i] < R[j]:
A[k] = L[i];
i = i + 1;
if i >= n1:
for i in range(j, n2):
k = k + 1;
A[k] = R[i];
break;
else:
A[k] = R[j]
j = j + 1;
if j >= n2:
for j in range(i, n1):
k = k + 1;
A[k] = L[j];
break;
return A;
a = [5, 0, 1, 3, 6, 2, 4, 9, 12, 11, 18, 20, 7, 8, 19, 13, 14, 17, 16, 10];
a = merge(a);
print(a);
如果你能很好的理解递归的思想的话,想必归并排序也是很简单的。其核心思想在于怎么把问题分解成一系列类型一样的小问题。我们可以这样想:
两个排好序的数列怎么合并成一个序列?
两个序列的数据一个一个比较,将小的存入新的队列,直至这两个数列一个为空,则将另外一个数列剩余数据插入队列。如果你把这两个数列想象成扑克的话或许更好理解。如果这两个序列都只有一个数据的话,是不是会很简单的就排完了?
[1, 3, 5], [2, 4, 6, 7] ======> [1, 2, 3, 4, 5, 6, 7]
归并排序通过递归方法,最终将一个待排序序列换成若干组待排序的包含一个数据的数列。
时间复杂度O(nlog(n))
堆排序:
曾经,第一次写堆排,用C链表,自信满满地构建了一颗二叉树!原来堆排序不需要构建一颗视觉上的二叉树!!!运用原址排序(只操作下标和对应的元素)解决!!!
parent = lambda i : (i - 1) / 2;
left = lambda i : 2 * i + 1;
right = lambda i : 2 * i + 2;
exchange = lambda a, b : (b, a);
def maxHeapfy(A, i, length):
l = left(i);
r = right(i);
if l < length and A[l] > A[i]:
large = l;
else:
large = i;
if r < length and A[r] > A[large]:
large = r;
if large != i:
(A[i], A[large]) = exchange(A[i], A[large]);
maxHeapfy(A, large, length);
return A;
def buildHeap(A, length):
for i in range(length / 2 - 1, -1, -1):
maxHeapfy(A, i, length);
def heapSort(A):
length = len(A);
buildHeap(A, length);
for i in range(len(A) - 1, 0, -1):
(A[0], A[i]) = exchange(A[0], A[i]);
length = length - 1;
maxHeapfy(A, 0, length);
return A;
a = [5, 0, 1, 3, 6, 2, 4, 9, 12, 11, 18, 20, 7, 8, 19, 13, 14, 17, 16, 10];
a = heapSort(a);
print(a);
堆排的思想在于理解最大(小)堆的概念:对于一个二叉树,父节点总是不小(大)于子节点的,即
A[parent(i)] >= A[i] ......①
后面便于称述不过于冗余,只讨论最大堆。
所以堆排的第一目的是建立一个满足条件的最大堆,要建立最大堆,就需要有最大堆的判定条件,即①式。建立最大堆之后,将根节点找到、保存并剔除、对剩下的序列继续做最大堆,重复上述过程即可完成排序。
时间复杂度O(nlog(n))
快速排序:
注意也是原址排序!!!
def partition(A, p, r):
x = A[r];
i = p - 1;
for j in range(p, r):
if A[j] <= x:
i = i + 1;
(A[i], A[j]) = (A[j], A[i]);
(A[i + 1], A[r]) = (A[r], A[i + 1]);
return i + 1;
def quickSort(A, p, r):
if p < r:
q = partition(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
return A;
a = [5, 0, 1, 3, 6, 2, 4, 9, 12, 11, 18, 20, 7, 8, 19, 13, 14, 17, 16, 10];
a = quickSort(a, 0, len(a) - 1);
print(a);
快排的思想在于将序列分成三部分A[0,i-1],A[i],A[i+1,n],并且满足条件A[0, i-1]中所有元素小于等于A[i],A[i+1,n]中所有元素大于等于A[i]。同样可以使用递归的方法实现。不理解的可以参考归并排序。
时间复杂度O(nlog(n))
最新文章
- Ubuntu 14.04 LTS 下升级 gcc 到 gcc-4.9、gcc-5 版本
- APPCAN开发笔记:html页面之间的参数传递:使用js获取url中的参数,以及在APPCAN中不能使用的解决方法
- 设计模式学习之备忘录模式(Memento,行为型模式)(19)
- knockout 学习实例4 css
- RTMP命令亲自测试记录
- hadoop分布式的环境搭建
- phpwind9.0 顶部和底部版权信息永久性修改
- python如何使用 os.path.exists()--Learning from stackoverflow 分类: python 2015-04-23 20:48 139人阅读 评论(0) 收藏
- c/c++字符数组和字符串大揭秘
- Codeforces Round #253 (Div. 1) (A, B, C)
- filter by date in Sphinx
- Redis的发布订阅及.NET客户端实现
- slideToggle+slideup实现手机端折叠菜单效果
- Django入门实战【3步曲】
- C#基础(string)
- SQL记录-资源正忙online或nowait
- TwemProxy Redis架构
- Codeforces 510 E. Fox And Dinner
- BackBone及其实例探究
- jQuery源码分析之整体框架
热门文章
- 【转载】Linux Cache Mechanism Summary(undone)
- python redis模块的常见的几个类 Redis 、StricRedis和ConnectionPool
- Sending forms through JavaScript
- 推荐Python、Django中文文档地址
- C#将一个枚举里面所有描述和value绑定到下拉列表的方法
- laravel项目使用twemproxy部署redis集群
- Java开源生鲜电商平台-盈利模式详解(源码可下载)
- Pycharm快捷键记录
- 腾讯云Unubtu 16.04 (gunicorn+supervisor+ngnix+mongodb)部署Flask应用
- 再探Circuit Breaker之使用Polly