python用排序算法 函数实现,用Python排序

　　一、排序的基本概念和分类

　　排序是根据一个或一些关键字的大小，将一串记录按升序或降序排列的操作。排序算法就是如何按照要求排列记录。

　　排序的稳定性：

　　经过某种排序后，如果两条记录的序号相同，且两条记录在原始无序记录中的顺序不变，则称所用的排序方法是稳定的，反之亦然。

　　内部排序和外部排序

　　内部排序：在排序过程中，所有要排序的记录都存储在内存中。

　　外部排序：在排序过程中，使用外部存储。

　　通常，讨论的是内部排序。

　　影响内部排序算法性能的三个因素：

　　时间复杂度：即时间性能。有效的排序算法应该具有尽可能少的关键字比较和记录的移动。空间复杂度：主要是执行算法需要的辅助空间。越少越好。算法的复杂度。主要是指代码的复杂度。

　　根据分拣过程中的主要操作，内部分拣可分为：

　　插入排序交换排序选择排序合并排序

　　根据算法的复杂程度，可以分为两类：

　　简单算法：包括冒泡排序、简单选择排序和直接插入排序。改进算法：包括希尔排序、堆排序、归并排序和快速排序。

　　以下七种排序算法只是所有排序算法中最经典的，并不是全部。

　　二、 冒泡排序

　　冒泡排序：时间复杂度o(n ^ 2)

　　一种交换。其核心思想是：两两比较相邻记录的关键词，如果逆序就交换，直到没有逆序的记录。

　　其实现细节可以有所不同，如以下三种：

　　最简单的排序实现：bubble_sort_simple。

　　冒泡排序：冒泡_排序

　　改进的冒泡排序3360 bubble _ sort _ advance

　　#!/usr/bin/env python #-*-coding : utf-8-*-# author 3360 Liujiang # python 3.5 #冒泡排序算法classSQList:

　　def__init__(self，lis=None):

　　nbsp;self.r=lisdefswap(self,i,j):

　　"""定义一个交换元素的方法，方便后面调用。"""

　　temp=self.r[i]

　　self.r[i]=self.r[j]

　　self.r[j]=tempdefbubble_sort_simple(self):

　　"""

　　最简单的交换排序，时间复杂度O(n^2)

　　"""

　　lis=self.r

　　length=len(self.r)foriinrange(length):forjinrange(i+1,length):iflis[i]>lis[j]:

　　self.swap(i,j)defbubble_sort(self):

　　"""

　　冒泡排序，时间复杂度O(n^2)

　　"""

　　lis=self.r

　　length=len(self.r)foriinrange(length):

　　j=length-2

　　whilej>=i:iflis[j]>lis[j+1]:

　　self.swap(j,j+1)

　　j-=1

　　defbubble_sort_advance(self):

　　"""

　　冒泡排序改进算法，时间复杂度O(n^2)

　　设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。

　　对于比较规整的元素集合，可提高一定的排序效率。

　　"""

　　lis=self.r

　　length=len(self.r)

　　flag=True

　　i=0

　　whilei<lengthandflag:

　　flag=False

　　j=length-2

　　whilej>=i:iflis[j]>lis[j+1]:

　　self.swap(j,j+1)

　　flag=True

　　j-=1

　　i+=1

　　def__str__(self):

　　ret=""

　　foriinself.r:

　　ret+="%s"%ireturnretif__name__=='__main__':

　　sqlist=SQList([4,1,7,3,8,5,9,2,6])#sqlist.bubble_sort_simple()

　　#sqlist.bubble_sort()

　　sqlist.bubble_sort_advance()

　　print(sqlist)简单选择排序（simple selection sort）:时间复杂度O(n^2)
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n)个记录进行交换。

　　通俗的说就是，对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于，每一轮中比较了很多次，但只交换一次。因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。

#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#简单选择排序classSQList:
　　def__init__(self,lis=None):
　　self.r=lisdefswap(self,i,j):
　　"""定义一个交换元素的方法，方便后面调用。"""
　　temp=self.r[i]
　　self.r[i]=self.r[j]
　　self.r[j]=tempdefselect_sort(self):
　　"""
　　简单选择排序，时间复杂度O(n^2)
　　"""
　　lis=self.r
　　length=len(self.r)foriinrange(length):
　　minimum=iforjinrange(i+1,length):iflis[minimum]>lis[j]:
　　minimum=jifi!=minimum:
　　self.swap(i,minimum)def__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%ireturnretif__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0])
　　sqlist.select_sort()
　　print(sqlist)

　　直接插入排序（Straight Insertion Sort）:时间复杂度O(n^2)
基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#直接插入排序classSQList:
　　def__init__(self,lis=None):
　　self.r=lisdefinsert_sort(self):
　　lis=self.r
　　length=len(self.r)#下标从1开始
　　foriinrange(1,length):iflis[i]<lis[i-1]:
　　temp=lis[i]
　　j=i-1
　　whilelis[j]>tempandj>=0:
　　lis[j+1]=lis[j]
　　j-=1
　　lis[j+1]=tempdef__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%ireturnretif__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0])
　　sqlist.insert_sort()
　　print(sqlist)

　　五、希尔排序

　　希尔排序（Shell Sort）是插入排序的改进版本，其核心思想是将原数据集合分割成若干个子序列，然后再对子序列分别进行直接插入排序，使子序列基本有序，最后再对全体记录进行一次直接插入排序。

　　这里最关键的是跳跃和分割的策略，也就是我们要怎么分割数据，间隔多大的问题。通常将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过：increment = int(increment/3)+1来确定“增量”的值。

　　相关推荐：《Python视频教程》

　　希尔排序的时间复杂度为：O(n^(3/2))

#!/usr/bin/envpython
　　#-*-coding:utf-8-*-
　　#Author:LiuJiang
　　#Python3.5
　　#希尔排序classSQList:
　　def__init__(self,lis=None):
　　self.r=lisdefshell_sort(self):
　　"""希尔排序"""
　　lis=self.r
　　length=len(lis)
　　increment=len(lis)
　　whileincrement>1:
　　increment=int(increment/3)+1
　　foriinrange(increment+1,length):
　　iflis[i]<lis[i-increment]:
　　temp=lis[i]
　　j=i-increment
　　whilej>=0andtemp<lis[j]:
　　lis[j+increment]=lis[j]
　　j-=increment
　　lis[j+increment]=temp
　　def__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%i
　　returnret
　　if__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0,123,22])
　　sqlist.shell_sort()
　　print(sqlist)

　　堆是具有下列性质的完全二叉树：
每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；
每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；
因此，其根节点一定是所有节点中（最小）的值。

　　如果按照层序遍历的方式（广度优先）给节点从1开始编号，则节点之间满足如下关系：

　　堆排序（Heap Sort）就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。（下面采用大顶堆的方式）

　　其核心思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的值就是堆的根节点。将它与堆数组的末尾元素交换，然后将剩余的n-1个序列重新构造成一个大顶堆。反复执行前面的操作，最后获得一个有序序列。

#!/usr/bin/envpython
　　#-*-coding:utf-8-*-
　　#Author:LiuJiang
　　#Python3.5
　　#堆排序classSQList:
　　def__init__(self,lis=None):
　　self.r=lis
　　defswap(self,i,j):
　　"""定义一个交换元素的方法，方便后面调用。"""
　　temp=self.r[i]
　　self.r[i]=self.r[j]
　　self.r[j]=temp
　　defheap_sort(self):
　　length=len(self.r)
　　i=int(length/2)#将原始序列构造成一个大顶堆
　　#遍历从中间开始，到0结束，其实这些是堆的分支节点。
　　whilei>=0:
　　self.heap_adjust(i,length-1)
　　i-=1
　　#逆序遍历整个序列，不断取出根节点的值，完成实际的排序。
　　j=length-1
　　whilej>0:#将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处
　　self.swap(0,j)#将发生变化的序列重新构造成大顶堆
　　self.heap_adjust(0,j-1)
　　j-=1
　　defheap_adjust(self,s,m):
　　"""核心的大顶堆构造方法，维持序列的堆结构。"""
　　lis=self.r
　　temp=lis[s]
　　i=2*s
　　whilei<=m:
　　ifi<mandlis[i]<lis[i+1]:
　　i+=1
　　iftemp>=lis[i]:
　　break
　　lis[s]=lis[i]
　　s=i
　　i*=2
　　lis[s]=tempdef__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%i
　　returnret
　　if__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0,123,22])
　　sqlist.heap_sort()
　　print(sqlist)

　　堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。

　　空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此，堆排序也是一种不稳定的排序方法。

　　此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。

　　七、归并排序

　　归并排序（Merging Sort）：建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

#!/usr/bin/envpython
　　#-*-coding:utf-8-*-
　　#Author:LiuJiang
　　#Python3.5
　　#归并排序
　　classSQList:
　　def__init__(self,lis=None):
　　self.r=lis
　　defswap(self,i,j):
　　"""定义一个交换元素的方法，方便后面调用。"""
　　temp=self.r[i]
　　self.r[i]=self.r[j]
　　self.r[j]=temp
　　defmerge_sort(self):
　　self.msort(self.r,self.r,0,len(self.r)-1)
　　defmsort(self,list_sr,list_tr,s,t):
　　temp=[Noneforiinrange(0,len(list_sr))]
　　ifs==t:
　　list_tr[s]=list_sr[s]
　　else:
　　m=int((s+t)/2)
　　self.msort(list_sr,temp,s,m)
　　self.msort(list_sr,temp,m+1,t)
　　self.merge(temp,list_tr,s,m,t)
　　defmerge(self,list_sr,list_tr,i,m,n):
　　j=m+1
　　k=i
　　whilei<=mandj<=n:
　　iflist_sr[i]<list_sr[j]:
　　list_tr[k]=list_sr[i]
　　i+=1
　　else:
　　list_tr[k]=list_sr[j]
　　j+=1
　　k+=1
　　ifi<=m:
　　forlinrange(0,m-i+1):
　　list_tr[k+l]=list_sr[i+l]
　　ifj<=n:
　　forlinrange(0,n-j+1):
　　list_tr[k+l]=list_sr[j+l]
　　def__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%i
　　returnret
　　if__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0,12,77,34,23])
　　sqlist.merge_sort()
　　print(sqlist)

defmerge(lfrom,lto,low,mid,high):
　　"""
　　两段需要归并的序列从左往右遍历，逐一比较，小的就放到
　　lto里去，lfrom下标+1，lto下标+1，然后再取，再比，再放，
　　最后lfrom里的两段比完了，lto里留下的就是从小到大排好的一段。
　　:paramlfrom:原来的列表
　　:paramlto:缓存的列表
　　:paramlow:左边一段的开头下标
　　:parammid:左右两段的中间相隔的下标
　　:paramhigh:右边一段的最右下标
　　:return:
　　"""
　　i,j,k=low,mid,low
　　whilei<midandj<high:
　　iflfrom[i]<=lfrom[j]:
　　lto[k]=lfrom[i]
　　i+=1
　　else:
　　lto[k]=lfrom[j]
　　j+=1
　　k+=1
　　whilei<mid:
　　lto[k]=lfrom[i]
　　i+=1
　　k+=1
　　whilej<high:
　　lto[k]=lfrom[j]
　　j+=1
　　k+=1defmerge_pass(lfrom,lto,llen,slen):
　　"""
　　用来处理所有需要合并的段，这需要每段的长度，以及列表的总长。
　　最后的if语句处理表最后部分不规则的情况。
　　:paramlfrom:原来的列表
　　:paramlto:缓存的列表
　　:paramllen:列表总长
　　:paramslen:每段的长度
　　:return:
　　"""
　　i=0
　　whilei+2*slen<llen:
　　merge(lfrom,lto,i,i+slen,i+2*slen)
　　i+=2*slenifi+slen<llen:
　　merge(lfrom,lto,i,i+slen,llen)
　　else:
　　forjinrange(i,llen):
　　lto[j]=lfrom[j]
　　defmerge_sort(lst):
　　"""
　　主函数。
　　先安排一个同样大小的列表，作为辅助空间。
　　然后在两个列表直接做往复的归并，每归并一次slen的长度增加一倍，
　　逐渐向llen靠拢，当slen==llen时说明归并结束了。
　　归并完成后最终结果可能恰好保存在templist里，因此代码里做两次归并，
　　保证最后的结果体现在原始的lst列表里。
　　:paramlst:要排序的原始列表
　　:return:
　　"""
　　slen,llen=1,len(lst)
　　templist=[None]*llenwhileslen<llen:
　　merge_pass(lst,templist,llen,slen)
　　slen*=2
　　merge_pass(templist,lst,llen,slen)
　　slen*=2

　　归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为O(n+logn)。

　　归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。

　　总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。

　　八、快速排序

　　快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。

　　快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。

#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#快速排序classSQList:
　　def__init__(self,lis=None):
　　self.r=lisdefswap(self,i,j):
　　"""定义一个交换元素的方法，方便后面调用。"""
　　temp=self.r[i]
　　self.r[i]=self.r[j]
　　self.r[j]=tempdefquick_sort(self):
　　"""调用入口"""
　　self.qsort(0,len(self.r)-1)defqsort(self,low,high):
　　"""递归调用"""
　　iflow<high:
　　pivot=self.partition(low,high)
　　self.qsort(low,pivot-1)
　　self.qsort(pivot+1,high)defpartition(self,low,high):
　　"""
　　快速排序的核心代码。
　　其实就是将选取的pivot_key不断交换，将比它小的换到左边，将比它大的换到右边。
　　它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。
　　但在函数调用的过程中，pivot_key的值始终不变。
　　:paramlow:左边界下标
　　:paramhigh:右边界下标
　　:return:分完左右区后pivot_key所在位置的下标
　　"""
　　lis=self.r
　　pivot_key=lis[low]
　　whilelow<high:
　　whilelow<highandlis[high]>=pivot_key:
　　high-=1
　　self.swap(low,high)
　　whilelow<highandlis[low]<=pivot_key:
　　low+=1
　　self.swap(low,high)
　　returnlow
　　def__str__(self):
　　ret=""
　　foriinself.r:
　　ret+="%s"%i
　　returnret
　　if__name__=='__main__':
　　sqlist=SQList([4,1,7,3,8,5,9,2,6,0,123,22])
　　sqlist.quick_sort()
　　print(sqlist)

defquick_sort(nums):
　　#封装一层的目的是方便用户调用
　　defqsort(lst,begin,end):
　　ifbegin>=end:
　　return
　　i=begin
　　key=lst[begin]
　　forjinrange(begin+1,end+1):
　　iflst[j]<key:
　　i+=1
　　lst[i],lst[j]=lst[j],lst[i]
　　lst[begin],lst[i]=lst[i],lst[begin]
　　qsort(lst,begin,i-1)
　　qsort(lst,i+1,end)
　　qsort(nums,0,len(nums)-1)

　　下面是一个实例测试数据：

　　从数据中可见：

　　数据过万，冒泡算法基本不可用。测试时间忠实的反映了n平方的时间复杂度，数据扩大10倍，耗时增加100倍对于Python的列表，反序遍历比正序遍历还是要消耗一定的时间的快速排序在数据较大时，其威力显现，但不够稳定，总体还是维护了nlog(n)的复杂度。

　　基本的快速排序还有可以优化的地方：

　　1. 优化选取的pivot_key

　　前面我们每次选取pivot_key的都是子序列的第一个元素，也就是lis[low]，这就比较看运气。运气好时，该值处于整个序列的靠近中间值，则构造的树比较平衡，运气比较差，处于或最小位置附近则构造的树接近斜树。
为了保证pivot_key选取的尽可能适中，采取选取序列左中右三个特殊位置的值中，处于中间值的那个数为pivot_key，通常会比直接用lis[low]要好一点。在代码中，在原来的pivot_key = lis[low]这一行前面增加下面的代码：

m=low+int((high-low)/2)iflis[low]>lis[high]:
　　self.swap(low,high)iflis[m]>lis[high]:
　　self.swap(high,m)iflis[m]>lis[low]:
　　self.swap(m,low)

　　2. 减少不必要的交换

　　原来的代码中pivot_key这个记录总是再不断的交换中，其实这是没必要的，完全可以将它暂存在某个临时变量中，如下所示：

defpartition(self,low,high):
　　
　　lis=self.r
　　m=low+int((high-low)/2)
　　iflis[low]>lis[high]:
　　self.swap(low,high)
　　iflis[m]>lis[high]:
　　self.swap(high,m)
　　iflis[m]>lis[low]:
　　self.swap(m,low)
　　pivot_key=lis[low]#temp暂存pivot_key的值
　　temp=pivot_key
　　whilelow<high:
　　whilelow<highandlis[high]>=pivot_key:
　　high-=1
　　#直接替换，而不交换了
　　lis[low]=lis[high]
　　whilelow<highandlis[low]<=pivot_key:
　　low+=1
　　lis[high]=lis[low]
　　lis[low]=tempreturnlow

　　快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。
因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：

defqsort(self,low,high):
　　"""根据序列长短，选择使用快速排序还是简单插入排序"""
　　#7是一个经验值，可根据实际情况自行决定该数值。
　　MAX_LENGTH=7
　　ifhigh-low<MAX_LENGTH:
　　iflow<high:
　　pivot=self.partition(low,high)
　　self.qsort(low,pivot-1)
　　self.qsort(pivot+1,high)
　　else:#insert_sort方法是我们前面写过的简单插入排序算法
　　self.insert_sort()

　　可以采用尾递归的方式对整个算法的递归操作进行优化，改写qsort方法如下：

defqsort(self,low,high):
　　"""根据序列长短，选择使用快速排序还是简单插入排序"""
　　#7是一个经验值，可根据实际情况自行决定该数值。
　　MAX_LENGTH=7
　　ifhigh-low<MAX_LENGTH:#改用while循环
　　whilelow<high:
　　pivot=self.partition(low,high)
　　self.qsort(low,pivot-1)#采用了尾递归的方式
　　low=pivot+1
　　else:#insert_sort方法是我们前面写过的简单插入排序算法
　　self.insert_sort()

　　排序算法的分类：

　　没有十全十美的算法，有有点就会有缺点，即使是快速排序算法，也只是整体性能上的优越，也存在排序不稳定，需要大量辅助空间，不适于少量数据排序等缺点。

　　七种排序算法性能对比

　　如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。