常用排序算法的python实现和性能分析

290112011

　　一年一度的换工作高峰又到了，HR大概每天都塞几份简历过来，基本上一天安排两个面试的话，当天就只能加班干活了。趁着面试别人的机会，自己也把一些基础算法和一些面试题整了一下，可以阶段性的留下些脚印——没办法，平时太忙，基本上没有时间写博客。面试测试开发的话，这些也许能帮得上一些。
　　这篇是关于排序的，把常见的排序算法和面试中经常提到的一些问题整理了一下。这里面大概有3个需要提到的问题：

• 虽然专业是数学，但是自己还是比较讨厌繁琐的公式，所以基本上文章所有的逻辑，我都尽可能的用大白话说，希望能说明白；
  
• 语言使用的是Python，原因是写的快一些，当然会尽可能的抛开一些Python的特点，比如数组处理的时候尽可能的不使用一些tuple交换等方式；
  
• 测试算法的时候会用到一些Python编程的技巧，这里只是简单的提一下，不做深入介绍；
  

　　
　　常用的排序算法（主要指面试中）包含两大类，一类是基础比较模型的，也就是排序的过程，是建立在两个数进行对比得出大小的基础上，这样的排序算法又可以分为两类：一类是基于数组的，一类是基于树的；基础数组的比较排序算法主要有：冒泡法，插入法，选择法，归并法，快速排序法；基础树的比较排序算法主要有：堆排序和二叉树排序；基于非比较模型的排序，主要有桶排序和位图排序（个人认为这两个属于同一思路的两个极端）。
　　对于上面提到的这些排序算法，个人认为并没有优劣之分，主要看关注点，也就是需求。综合去看待这些算法，我们可以通过以下几个方面（不完全）判断：时间复杂度，空间复杂度，待排序数组长度，待排序数组特点，程序编写复杂度，实际程序运行环境，实际程序可接受水平等等。说白了就是考虑各种需求和限制条件，程序快不快，占得空间，排序的数多不多，规律不规律，数据重合的多不多，程序员水平，运行的机器高配还是低配，客户或者用户对运行时间的底线等等。
　　抛开主观的这些因为，从技术上讲，时间复杂度和空间复杂度，是最为关心的，下面是这些排序算法的一个总结和特点——分类和总结完全是个人体会，请不要拿教科书上的东西较真。
　　冒泡法：对比模型，原数组上排序，稳定，慢
　　插入法：对比模型，原数组上排序，稳定，慢
　　选择法：对比模型，原数组上排序，稳定，慢
　　归并法：对比模型，非原数组上排序，稳定，快
　　快速法：对比模型，原数组上排序，不稳定，快
　　堆排序：对比模型，原数组上排序，不稳定，快
　　二叉树排序：对比模型，非数组上排序，不稳定，快
　　桶排序：非对比模型，非原数组上排序，不稳定，快
　　位图排序：非对比模型，非原数组上排序，不稳定，快
　　
　　现在开始正经的东西，逐一讨论一下这些排序算法；事实上，理解了算法本身的意义，伪代码很容易写出来，但是写代码是另外一回事——算法忽略常量，忽略对于复杂度影响不大的东西，但是写代码的时候，却必须关心这些：
　　
　　冒泡法
　　入门级算法，但是它的思路很具有特点：循环，两两向后比较。具体方法是针对循环中的每一元素，都对它后面的元素循环比较，交换大小值，每次循环“冒”一个最大值（或最小值）放在里层循环初始的地方；python中的代码如下：



def bubbleSort(L):
assert(type(L)==type(['']))
length = len(L)
if length==0 or length==1:
return L
for i in xrange(length):
for j in xrange(length-1-i):
if L[j] < L[j+1]:
temp = L[j]
L[j] = L[j+1]
L[j+1] = temp
return L
pass
　　
　　冒泡法的优点是稳定，不需要大量额外的空间开销，而且容易想到。很多面试人员知道快速排序，但是不知道冒泡法——大部分是培训学校出来的，快速排序稍微改动一些就不知道怎么办了，但是冒泡法，虽然不知道，但是解释和优化起来，确很容易。毕竟对于编程来说，嵌套一个循环和判断，是最基本的。
　　
　　选择排序
　　选择法也算是入门的一种排序算法，比起冒泡法，它的方法巧妙了一些，它的出发点在于“挑”，每次挑选数组的最值，与前置元素换位，然后继续挑选剩余元素的最值并重复操作。个人认为选择排序的意义不在于排序本身，而在于挑选和置换的方法，对于一些问题很有帮助。先看一下选择排序的python实现：



def selectSort(L):
assert(type(L)==type(['']))
length = len(L)
if length==0 or length==1:
return L
def _max(s):
largest = s
for i in xrange(s,length):
if L > L[largest]:
largest = i
return largest
for i in xrange(length):
largest = _max(i)
if i!=largest:
temp = L[largest]
L[largest] = L
L = temp
return L
pass
　　和冒泡排序一样，稳定，原位排序，同样比较慢。但是它的挑选和置换的方法，确实巧妙的，比如另一个面试提：0～100的已经排序的序列，如何随机打乱它的顺序，当然也可以变成如何最快的生成0～100的随机数。一种比较好的方法，就是随机在数组里挑选元素，然后置换这个数据和最后一个元素的位置，接下来在不包含最后一个元素的数组里继续找随机数，然后继续后置。
　　这个shuffle的方法，事实上难倒了很多面试的同学，甚至有些链表和树什么的都已经用到了。选择排序的思维可以轻松搞定这个问题。
　　
　　插入排序
　　冒泡，选择和插入，在排序算法中算最为入门的，虽然简单，但是也都各自代表着常用的编程方法。插入法和之前两个排序对比，并不在于如何按顺序的“取”，而在于如何按数序的“插”。具体方法是，顺序地从数组里获取数据，并在一个已经排序好的序列里，插入到对应的位置，当然，最好的放置已经排序的数据的容器，也是这个数组本身——它的长度是固定的，取了多少数据，就有多少空位。具体Python实现如下：



def insertSort(L):
assert(type(L)==type(['']))
length = len(L)
if length==0 or length==1:
return L
for i in xrange(1,length):
value = L
j = i-1
while j>=0 and L[j]0):
if left[0]>right[0]:
L = left.pop(0)
else:
L = right.pop(0)
s+=1
while(len(left)>0):
L = left.pop(0)
s+=1
while(len(right)>0):
L = right.pop(0)
s+=1
pass
if start L[child]:
L[root],L[child] = L[child],L[root]
root = child
else:
break
for start in range((len(L)-2)/2,-1,-1):
sift_down(L,start,len(L)-1)
for end in range(len(L)-1,0,-1):
L[0],L[end] = L[end],L[0]
sift_down(L,0,end-1)
return L
　　由于堆排序的堆的高度为log2N，而它每次调整的时候需要对比的次数趋向于N，所以整体的时间复杂度是N*log2N，但是它并不稳定的一种算法，依赖于给定的待排序数组。另外，堆排序是在原来的数组（二叉树）上进行调整和换位，并没有申请多余的空间。和冒泡一类两两相比的排序算法比较，堆排序主要是使用二叉树构建堆的方式，传递的排序结果。
　　但是事实上，每次根节点和后面元素置换的同时，二叉树其他节点并没有改变，所以我们可以使用额外的空间来记录这些节点的排列情况，提高排序速度。
　　
　　二叉树排序
　　这是另一个使用树进行排序的方法，和堆排序不同的是，这种方法需要这正的构建二叉树，而不是使用数组的二叉树形式。它的核心在与构建二叉树时的顺序以及输入二叉树时的顺序。
　　具体方法是，依次读取待排序数组的元素，并将其添加为一个二叉树的节点；添加的时候，按值的大小放在节点的左右，如果左右节点已经被占用，则递归到子节点进行添加。二叉树输出的时候，采取前序遍历或者后序遍历的方式输出。具体的Python代码如下：



def binaryTreeSort(l):
assert(type(l)==type(['']))
length = len(l)
if length==0 or length==1:
return l
class Node:
def __init__(self,value=None,left=None,right=None):
self.__value = value
self.__left = left
self.__right = right
@property
def value(self):
return self.__value
@property
def left(self):
return self.__left
@property
def right(self):
return self.__right
class BinaryTree:
def __init__(self,root=None):
self.__root = root
self.__ret=[]
@property
def result(self):
return self.__ret
def add(self,parent,node):
if parent.value>node.value:
if not parent.left:
parent.left = node
else:
self.add(parent.left,node)
pass
else:
if not parent.right:
parent.right = node
else:
self.add(parent.right,node)
def Add(self,node):
if not self.__root:
self.__root = node
else:
self.add(self.__root, node)
def show(self,node):
if not node:
return
if node.right:
self.show(node.right)
self.__ret.append(node.value)
if node.left:
self.show(node.left)
def Show(self):
self.show(self.__root)
b = BinaryTree()
for i in l:
b.Add(Node(i))
b.Show()
return b.result
　　按之前提到的，我们需要构建节点和二叉树的对象或者结构，然后进行遍历排序。本身需要构建二叉树和遍历输入，所以复杂度不如好的直接排序算法；如果不考虑空间开销和输出遍历，它整体的复杂度还是N*log2N的。所以整体的复杂度介于冒泡算法等普通排序算法和快速排序等高级排序算法之间。
　　
　　文中要讨论的基于比较模型的排序算法暂时只讨论这么多，最后讨论二叉树排序，是为了引深一个问题——比较模型的排序算法复杂度还能在优化吗？答案是不行的，纯比较模型的排序算法，最好的时间复杂度就是N*log2N了。我们可以改造二叉树排序来证明这一点，当然还是以大白话为主，我不喜欢繁琐的公式。
　　这个问题的证明，是需要一套模型理论的，即决策树。我们抛开各种理论，可以简单的认为，这就是一个二叉树。这个二叉树的最终展开，就是所有的决策，在这里就是一个待排序数组的所有数序集合，一个N个元素的所有排序个数为N!个。也就是说，从这个二叉树的根节点开始，最终会有N!个子节点。那么这个二叉树的深度，也就是最终执行的次数。实际上，也就是2^h=N!，通过数学推导，可以得到h0:
ret.append(x)
tem-=1
map(lambda x:count(x),l)
map(lambda x:pop(x),xrange(m,0,-1))
return ret
　　
　　这种计数排序的方法并不是用于数序很大的情况，而且数据越紧凑排序效果越好。当然这样的算法还有可以提高的地方，那就是除了找到待排序数组的最大值以外，还可以找到它的最小值，以缩短申请的空间。但是提高的效果有限。这样的算法对环境要求很高，但是如果满足这样的环境，它的排序效果，非常高效。比如百度百科中的一个例子：
　　--------------------------------------------

海量数据

一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。

分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)&asymp;1.112亿。但是我们发现，这些数据都有特殊的条件： 100=>SHIFT] &= ~(1SHIFT] |=(1