排序算法总结-python实现
最近在复习软考,把看到的排序算法整理了一下,之所以用python写,是因为python写起来简单....好吧,后来写的时候发现有些地方用C写还方便些。python虽然简洁,但用起来效率感觉还是有些低,不过这不是重点啦。。。
# -*- coding: utf-8 -*- def bubbleSort(Data): ‘‘‘冒泡排序: 时间复杂度最好O(n),平均O(n*n),最坏O(n*n),辅助空间 O(1),算法稳定 n个数,每次从第一个数开始和相邻的数比较,将大的冒泡到后面去。第一趟将最大的冒泡到最后, 然后第二次只需比较0~n-1,将其中最大的冒泡到n-1,依次下去...总共进行n-1趟排序即可 ‘‘‘ if Data: for i in range(len(Data)): for j in range(len(Data)-i-1): if Data[j]>Data[j+1]: Data[j],Data[j+1]=Data[j+1],Data[j] return Data def quickSort(Data,low,high): ‘‘‘快速排序:O(n*logn),O(n*logn),O(n*n),O(n*logn),不稳定 冒泡的改进,被认为是当前最优秀的内部排序算法,实现基于分治法:分解-解决-合并。 基本思想: 1.从数列中取出一个基数, 2.将数列中比他大的放在右边,小的在左边。 3.两边区间重复2,直到各区间只有一个数。 整个算法中的基数就是个坑,跳来跳去,总之比他小始终放一边,大的放另一边就行 参考:http://blog.csdn.net/morewindows/article/details/6684558 ‘‘‘ if low < high: left,right,base=low,high,Data[low] while left <right: #从后往前找比base小的数 while left <right and Data[right] >=base: right-=1 if left < right: Data[left]=Data[right] #left+=1 这里直接+1更快,因为Data[left]必然小于base,下次循环不用算 #从前往后找比base大的数 while left <right and Data[left] < base: left+=1 if left <right: Data[right]=Data[left] #right-=1 #left=right时一趟循环终止,base填回坑里去 Data[left]=base quickSort(Data,low,left-1) #递归左边 quickSort(Data,left+1,high) #递归右边 def insertSort(Data): ‘‘‘插入排序: 时间复杂度最好O(n),平均O(n*n),最坏O(n*n),辅助空间 O(1),算法稳定 如果Data不为空则开始比较。Data[0]~Data[j]是排好的序列L1,key是未排待插入数据 如果key小于L1的最大值则将进行插入操作,while循环找到比key小的index并将key插入 在index后面。while循环用来寻找插入位置并将比key大的数后移,如果key本身比L1的 最大值还大则无需插入,直接for循环比较下一个 ‘‘‘ if Data: for i in range(1,len(Data)): key,j = Data[i],i-1 while j>=0 and Data[j] > key: Data[j+1]=Data[j] j-=1 Data[j+1]=key return Data def selectSort(Data): ‘‘‘选择排序: 时间复杂度最好O(n*n),平均O(n*n),最坏O(n*n),辅助空间 O(1),算法不稳定 n个数,每一趟从待排序列L2中选择最大(或最小)数顺序放在已排好序列L1后面(或前面) 总共经过n-1趟可排好,与插入排序相比,都是将数据分为已排和未排序列并将未排元素整理 到已排序列中,不同的是插入排序在未排序列中按序整理,选排则是按大小选择整理。 ‘‘‘ if Data: for i in range(len(Data)-1): minnum=i for j in range(i+1,len(Data)):#在L2中寻找最小值 if Data[j]<Data[minnum]: minnum=j if minnum != i:#如果找到直接交换,插入在L1后面 Data[i],Data[minnum]=Data[minnum],Data[i] return Data def shellSort(Data): ‘‘‘希尔排序: 时间复杂度最好未知,平均O(pow(n,1.25),最坏未知,辅助空间 O(1),不稳定 插入排序的改进,将数据分组,每组m个(m叫步长)每次对每组的第i个元素排序, 然后再分组,再排序,直到步长为1.至于分组的方法需要理论推导,此处每次步长都取n/2减半 更好的步长选择方法见wiki:http://zh.wikipedia.org/wiki/希尔排序 其他实现方法:http://blog.csdn.net/morewindows/article/details/6668714 ‘‘‘ n=len(Data) if n > 1: gap=n/2 while gap > 0: for i in range(gap):#按步长插入排序 for j in range(i+gap,n,gap): if Data[j] < Data[j-gap]: key = Data[j] k=j-gap while k >=0 and Data[k] > key: Data[k+gap]=Data[k] k-=gap Data[k+gap]=key gap/=2 return Data if __name__ =="__main__": Data=[3,5,1,56,3,7,34,21,8] print Data #insertSort(Data) #bubbleSort(Data) #selectSort(Data) #shellSort(Data) quickSort(Data,0,len(Data)-1) print Data
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。