本文首发地址：

欢迎关注我的博客【Together_CZ】，我是沂水寒城！

这里的目的是为了更加完整详尽的总结一下这些排序算法，为了复习基础的东西，从冒泡排序、直接插入排序、选择排序、归并排序、希尔排序、桶排序、堆排序。快速排序入手来分析和实现，在最后也给出来了简单的时间统计，重在原理、算法基础，其他的次之，这些东西的熟练掌握不算是对之后的工作或者接下来的准备面试都是很有帮助的，算法重在理解内在含义和理论基础，在实现的时候才能避开陷阱少出错误，这不是说练习的时候有错误不好而是说，有些不该出现的错误尽量还是少出现的好，毕竟好的编程习惯是离不开严格的约束的，好了，这里就不多说了，复习一下基础知识，共同学习吧，下面是具体实现，注释应该都很详细，就不解释了：

#!usr/bin/env python#encoding:utf-8 '''__Author__:沂水寒城功能： python实现八大排序算法，分析时间消耗情况'''import sysimport timeimport randomimport numpy as npimport matplotlib.pyplot as pltreload(sys)sys.setdefaultencoding('utf-8')time_dict={}def plotChuiZhiBar(data_list,trick_list,num=1000,pic_path='bar.png'): ''' 绘制垂直直方图 ''' x_list=np.arange(len(data_list)) plt.clf() plt.figure(figsize=(12,8)) plt.bar(x_list,data_list,alpha=0.5,width=0.6,color='b',edgecolor='g',lw=2) plt.legend(loc='best') plt.title('sort Algorithm Time Consume,Num: '+str(num)) plt.xticks(x_list,trick_list,rotation=90) plt.savefig(pic_path)def timeDecorator(sortFunc): ''' 时间计算的装饰器函数,可用于计算函数执行时间 ''' def wrapper(num_list): start=time.time() res=sortFunc(num_list) end=time.time() delta=str(end-start) time_dict[str(sortFunc).split(' ')[1].strip()]=delta print u'耗时为：',delta print u'结果为：', res return wrapperdef randomNumGenerator(minV=-100,maxV=1000,N=20): ''' 随机数列表生成器  ''' num_list=[] for i in range(N): num_list.append(random.randint(minV,maxV)) return num_list @timeDecoratordef bubbleSort(num_list): ''' 冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序 ''' for i in range(len(num_list)): for j in range(i,len(num_list)): if num_list[i]>num_list[j]: #这里是升序排序 num_list[i], num_list[j]=num_list[j], num_list[i] return num_list @timeDecoratordef insertSort(num_list): ''' 直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序 ''' for i in range(len(num_list)): for j in range(0,i): if num_list[i]<num_list[j]: #这里是升序排序,跟冒泡排序差别在于，冒泡是向后遍历，这个是向前遍历 num_list[i], num_list[j]=num_list[j], num_list[i] return num_list @timeDecoratordef selectSort(num_list): ''' 选择排序，时间复杂度O(n^2)，空间复杂度O(1)，不是稳定排序 ''' for i in range(len(num_list)): min_value_index=i  for j in range(i, len(num_list)): if num_list[j]<num_list[min_value_index]: min_value_index=j #乍一看，感觉冒泡，选择，插入都很像，选择跟冒泡的区别在于：冒泡是发现大 #小数目顺序不对就交换，而选择排序是一轮遍历结束后选出最小值才交换，效率更高 num_list[i], num_list[min_value_index]=num_list[min_value_index], num_list[i]  return num_list @timeDecoratordef mergeSort(num_list): ''' 归并排序，时间复杂度O(nlog₂n)，空间复杂度：O(1)，是稳定排序 ''' if len(num_list)==1: return num_list length=len(num_list)/2 list1=num_list[:length] list2=num_list[length:] result_list=[] while len(list1) and len(list2): if list1[0]<=list2[0]: result_list.append(list1[0]) del list1[0] #这里需要删除列表中已经被加入到加过列表中的元素，否则最后比较完后列表 else: #中剩余元素无法添加 result_list.append(list2[j]) del list1[0]  if len(list1): #遍历比较完毕后列表中剩余元素的添加 result_list+=list1  else: result_list+=list2  return result_list @timeDecoratordef shellSort(num_list):  ''' 希尔排序，时间复杂度：O(n)，空间复杂度：O(n^2),不是稳定排序算法 ''' new_list = []  for one_num in num_list:  new_list.append(one_num)  count=len(new_list)  step=count/2;  while step>0:  i=0  while i<count:  j=i+step  while j<count:  t=new_list.pop(j)  k=j-step  while k>=0:  if t>=new_list[k]:  new_list.insert(k+1, t)  break  k=k-step  if k<0:  new_list.insert(0, t)  j=j+step  i=i+1  step=step/2 #希尔排序是一个更新步长的算法  return new_list @timeDecoratordef tongSort(num_list):  ''' 桶排序，时间复杂度O(1)，空间复杂度与最大数字有关，可以认为是O(n)，典型的空间换时间的做法 ''' original_list = []  total_num=max(num_list) #获取桶的个数 for i in range(total_num+1): #要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始  original_list.append(0)  for num in num_list:  original_list[num] += 1  result_list = []  for j in range(len(original_list)):  if original_list[j] != 0:  for h in range(0,original_list[j]):  result_list.append(j)  return result_list@timeDecoratordef quickSort(num_list): quick_sort=lambda num_list: num_list if len(num_list)<=1 else \ quick_sort([item for item in num_list[1:] if item<=num_list[0]])+\ [num_list[0]]+quick_sort([item for item in num_list[1:] if item>num_list[0]]) return num_listdef heapAdjust(num_list, i, size): ''' 堆调整，插入数据后对不满足堆形式的情况进行调整 ''' left_child=2*i+1  right_child=2*i+2  max_temp=i  if left_child<size and num_list[left_child]>num_list[max_temp]:  max_temp = left_child  if right_child<size and num_list[right_child]>num_list[max_temp]:  max_temp = right_child  if max_temp != i:  num_list[i], num_list[max_temp] = num_list[max_temp], num_list[i]  heapAdjust(num_list, max_temp, size) #避免调整之后以max为父节点的子树不是堆  def createHeap(num_list,size):  ''' 递归方式来创建堆 ''' a=size/2-1  for i in range(a,-1,-1):  heapAdjust(num_list,i,size) @timeDecoratordef heapSort(num_list): ''' 堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序 ''' size=len(num_list)  createHeap(num_list,size)  i=size-1  while i>0:  num_list[0],num_list[i]=num_list[i],num_list[0]  size-=1  i-=1  heapAdjust(num_list,0,size)  return num_list def resultPloter(time_dict,num=1000,pic_path='1000.png'): ''' 结果可视化工具 ''' sorted_list=sorted(time_dict.items(),key=lambda e:e[1]) trick_list=[one[0] for one in sorted_list] data_list=[one[1] for one in sorted_list] plotChuiZhiBar(data_list,trick_list,num=num,pic_path=pic_path) if __name__ == '__main__': num_list=randomNumGenerator(minV=0,maxV=1000000,N=500) print num_list bubbleSort(num_list) insertSort(num_list) selectSort(num_list) mergeSort(num_list) shellSort(num_list) tongSort(num_list) heapSort(num_list) quickSort(num_list) print time_dict resultPloter(time_dict,num=500,pic_path='500.png')

上面的代码我将排序结果进行了可视化如下：

数据量为500时：

数据量为1000时：

数据量为10000时：

主要是分析一下随着数据量的增长不同排序算法的时间消耗增加情况，感兴趣的话可以实际跑一下上面的代码。