基于python的七种经典排序算法课案

1、基于python的七种经典排序算法排序的基本概念和分类所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序的稳定性：经过某种排序后，如果两个记录序号同等，且两者在原无序记录中的先后秩序依然保持不变，则称所使用的排序方法是稳定的，反之是不稳定的。内排序和外排序内排序：排序过程中，待排序的所有记录全部放在内存中外排序：排序过程中，使用到了外部存储。通常讨论的都是内排序。影响内排序算法性能的三个因素:时间复杂度：即时间性能，高效率的排序算法应该是具有尽可能少的关键字比较次数和记录的移动次数空间复杂度：主要是执行算法

2、所需要的辅助空间，越少越好。算法复杂性。主要是指代码的复杂性。根据排序过程中借助的主要操作，可把内排序分为：插入排序交换排序选择排序归并排序按照算法复杂度可分为两类：简单算法：包括冒泡排序、简单选择排序和直接插入排序改进算法：包括希尔排序、堆排序、归并排序和快速排序以下的七种排序算法只是所有排序算法中最经典的几种，不代表全部。二、冒泡排序冒泡排序(Bubblesort):时间复杂度O(n人2)交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。其实现细节可以不同，比如下面3种:1.最简单排序实现:bubble_sort_simple2.冒泡排序:bub

3、ble_sort3.改进的冒泡排序:bubble_sort_advance#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#冒泡排序算法classSQList:definit(self,lis=None):I1o=self.r=lisdefswap(self,i,j):定义一个交换元素的方法，方便后面调用。二Itemp=self.riII口self.ri=self.rjIIIIIIself.rj=tempdefbubblesortsimple(self):最简单的交换排序，时间复杂度0(n2)IIlis=self

4、.rIinIilength=len(self.r)TOC o 1-5 h z HYPERLINK l bookmark14 o Current Document IIIIforiinrange(length): HYPERLINK l bookmark20 o Current Document IIOIIforjinrange(i+1,length):iflisilisj:self.swap(i,j)defbubble_sort(self):冒泡排序，时间复杂度O(n-2) HYPERLINK l bookmark28 o Current Document IIlis=self.riiniil

5、ength=len(self.r) HYPERLINK l bookmark16 o Current Document IIIIforiinrange(length):j=length-2IIoowhilej=i:II11Iiflisjlisj+1:self.swap(j,j+1)j-=1defbubblesortadvance(self):冒泡排序改进算法，时间复杂度0(n2)设置flag,当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。对于比较规整的元素集合，可提高一定的排序效率。IIlis=self.r|inIilength=len(self.r)flag=Truei=0

6、IrllII1whilei=i:II11Iiflisjlisj+1:IIself.swap(j,j+1)ZZ1Dflag=True=j-=1匚二”匚：二i+=1defstr(self):IIret=1o口foriinself.r:匚二二:二二口ret+=%s%iEZ3returnret口ifname=main:sqlistSQList(4,1,7,3,8,5,9,2,)#sqlist.bubblesortsimple()#sqlist.bubblesort()sqlist.bubblesortadvance()IIprint(sqlist)三、简单选择排序简单选择排序(simpleselect

7、ionsort):时间复杂度O(n2)通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1=ilisj:”二二二二口minimum=jifi!=minimum:self.swap(i,minimum)defstr(self):二】1二二二二1ret=TOC o 1-5 h z HYPERLINK l bookmark60 o Current Document I1foriinself.r: HYPERLINK l bookmark64 o Current Document IIret+=%s%iIZZIreturnretTOC o 1-5 h z HYPERLI

8、NK l bookmark138 o Current Document 口ifname=main:sqlist=SQList(4,1,7,3,8,5,9,2,6,0)sqlist.selectsort()IIprint(sqlist)直接插入排序(StraightInsertionSort):时间复杂度O(n2)基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#直接插入排序classSQList:definit(self,lis

9、=None):I1口=self.r=lisdefinsertsort(self):IIlis=self.rIinIilength=len(self.r)#下标从1开始1OIIforiinrange(1,length):=iflisitempandj=0:lisjj-=1iiniilisj+1=tempdef_str_(self):iinret=IIforiinself.r:二1口ret+=%s%iEZJreturnret口ifname=main:sqlistfSQList(4二17二3二8二5二9匚2匚6匚0)sqlist.insertsort()IIprint(sqlist)该算法需要一个记

10、录的辅助空间。最好情况下，当原始数据就是有序的时候，只需要一轮对比，不需要移动记录，此时时间复杂度为O(n)。然而，这基本是幻想。五、希尔排序希尔排序(ShellSort)是插入排序的改进版本，其核心思想是将原数据集合分割成若干个子序列，然后再对子序列分别进行直接插入排序，使子序列基本有序，最后再对全体记录进行一次直接插入排序。这里最关键的是跳跃和分割的策略，也就是我们要怎么分割数据，间隔多大的问题。通常将相距某个增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。下面的例子中通过：increment=int(increment/3)+1

11、来确定“增量”的值。希尔排序的时间复杂度为：O(n(3/2)#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#希尔排序classSQList:definit(self,lis=None):IIIZZ1self.r=lisdefshellsort(self):希尔排序IIlis=self.rIIIlength=len(lis)IIIIincrement=len(lis)TOC o 1-5 h z HYPERLINK l bookmark106 o Current Document IIIwhileincrement

12、1:口IIincrement=int(increment/3)+1TOC o 1-5 h zOIIIforiinrange(increment+1,length):temp=lisij=i-incrementwhilej=0andtemplisj:IlI11Ilisj+increment=lisjj-=increment1IIIIlisj-increment=tempdef_str_(self):iflisi_=0:self.heapadjust(i,length-1)i-=1#逆序遍历整个序列，不断取出根节点的值，完成实际的排序。j=length-11ODDwhilej0:#将当前根节点，也

13、就是列表最开头，下标为0的值，交换到最后面j处IIIIIIself.swap(0,j)#将发生变化的序列重新构造成大顶堆Inself.heapadjust(0,j-1)匚二”匚：二j-=1defheapadjust(self,s,m):核心的大顶堆构造方法，维持序列的堆结构。二:二二二Ilis=self.rtemp=liss1i=2*sIIowhilei=m:III11Iifimandlisi=lisi:breakliss=lisis=i匚二”匚：二i*=21二二二二二二:门匚二1liss=tempdefstr(self):ret=IIforiinself.r:l爲匚二二二二二1ret+=%s

14、%ireturnret口ifname=main:sqlist：SQList(4=i7=3=8=5=9,2,6,J=123,22)sqlist.heapsort()IIprint(sqlist)堆排序的运行时间主要消耗在初始构建堆和重建堆的反复筛选上。其初始构建堆时间复杂度为O(n)。正式排序时，重建堆的时间复杂度为O(nlogn)。所以堆排序的总体时间复杂度为O(nlogn)。堆排序对原始记录的排序状态不敏感，因此它无论最好、最坏和平均时间复杂度都是O(nlogn)。在性能上要好于冒泡、简单选择和直接插入算法。空间复杂度上，只需要一个用于交换的暂存单元。但是由于记录的比较和交换是跳跃式的，因此

15、，堆排序也是一种不稳定的排序方法。此外，由于初始构建堆的比较次数较多，堆排序不适合序列个数较少的排序工作。七、归并排序归并排序(MergingSort):建立在归并操作上的一种有效的排序算法,该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#归并排序classSQList:def_init_(self,lis=

16、None):IIIZZ1self.r=lisdefswap(self,i,j):定义一个交换元素的方法，方便后面调用。I1I1temp=self.riIIIlllself.rj=tempdefmerge_sort(self):iimmnnonself.msortSelf.r,self.r,0,len(self.r)-1)defmsort(self,list_sr,list_tr,s,t):ZOtemp=None口口IZZforiinrange(0,len(listsr)I二m口ifs=t:list_trs=list_srselse:II口m=int(s+t)/2)self.msort(list

17、sr,temp,s,m)IIself.msort(listsr,temp,m+1,t)self.merge(temp,listtr,s,m,t)defmerge(self,listsr,listtr,i,m,n):1口j=m+11口k=i【二”二二”1CZJoowhilei=mandj=n:iflist_srilist_srj:list_trk=list_srii+=1TOC o 1-5 h zIIelse:list_trk=list_srjj+=1【二二二二二二二Ik+=1ifi=m:iinrinnforlinrange(0,m-i+1):I1111Ilist_trk+l=list_sri+

18、lEZJ口ifj=n:TOC o 1-5 h z HYPERLINK l bookmark102 o Current Document IIforlinrange(0,n-j+1):I1111Ilist_trk+l=list_srj+ldefstr(self):IIret= HYPERLINK l bookmark108 o Current Document IIforiinself.r:匚二二:二二口ret+=%s%iEZJreturnret口nifname=main:sqlist口口SQList(4,1,7,3,8,5,9,2,6,0,12,77,34,23)sqlist.mergesor

19、t()print(sqlist)归并排序对原始序列元素分布情况不敏感，其时间复杂度为0(nlogn)。归并排序在计算过程中需要使用一定的辅助空间，用于递归和存放结果，因此其空间复杂度为0(n+logn)。归并排序中不存在跳跃，只有两两比较，因此是一种稳定排序。总之，归并排序是一种比较占用内存，但效率高，并且稳定的算法。八、快速排序快速排序(QuickSort)由图灵奖获得者TonyHoare发明，被列为20世纪十大算法之一。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n)。快速排序算法的核心思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一

20、部分记录的关键字小，然后分别对这两部分继续进行排序，以达到整个记录集合的排序目的。#!/usr/bin/envpython#-*-:utf-8-*-#Author:LiuJiang#Python3.5#快速排序classSQList:definit(self,lis=None):IIIZZ1self.r=lisdefswap(self,i,j):定义一个交换元素的方法，方便后面调用。I1I1temp=self.riIIIself.rj=tempdefquick_sort(self):self.swap(low,high)调用入口|1Iinself.qsort0,len(self.r)-1)de

21、fqsort(self,low,high):递归调用TOC o 1-5 h z HYPERLINK l bookmark196 o Current Document I1I111iflowhigh: HYPERLINK l bookmark198 o Current Document IIIIpivot=self.partition(low,high)IIself.qsort(low,pivot-1)IIIIself.qsort(pivot+1,high)defpartition(self,low,high):快速排序的核心代码。其实就是将选取的pivot_key不断交换，将比它小的换到左边，

22、将比它大的换到右边。它自己也在交换中不断变换自己的位置，直到完成所有的交换为止。但在函数调用的过程中，pivot_key的值始终不变。：paramlow左边界下标：paramhigh右边界下标：return:分完左右区后pivot_key所在位置的下标，,，TOC o 1-5 h z HYPERLINK l bookmark206 o Current Document IIlis=self.rpivot_key=lislow HYPERLINK l bookmark208 o Current Document IIII1whilelowhigh:IIIIIIIlI-whilelow=pivot

23、key:high-=1TOC o 1-5 h zIII11IIIIIwhilelowhighandlislowlishigh:III11self.swap(low,high)iflismlishigh:III11(high,m)iflismlislow:IIself.swap(m,low)如果觉得这样还不够好，还可以将整个序列先划分为3部分，每一部分求出个pivot_key，再对3个pivot_key再做一次上面的比较得出最终的pivot_key。这时的pivot_key应该很大概率是一个比较靠谱的值。2.减少不必要的交换原来的代码中pivot_key这个记录总是再不断的交换中，其实这是没必要

24、的，完全可以将它暂存在某个临时变量中，如下所示:defpartition(self,low,high):IIlis=self.rI11II11Im=low+int(high-low)/2)iflislowlishigh:iflismlishigh:self.swap(high,m)iflismlislow:self.swap(m,low)pivot_key=lislow#temp暂存pivot_key的值temp=pivotkeyirmizziwhilelowhigh:IIIIIIIlIlwhilelow=pivotkey:1highF#直接替换，而不交换了lislow=lishighTOC o 1-5 h zIII11IIIIIwhilelowhighandlislow=pivotkey:Illow+=1lishigh=lislow【mi”二mzirznlislow=tempEZJreturnlow快速排序算法的递归操作在进行大量数据排序时，其开销能被接受，速度较快。但进行小数组排序时则不如直接插入排序来得快，也就是杀鸡用牛刀，未必就比菜刀来得快。因此，一种很朴素的做法就是根据数据的多少，做个使用哪种算法的选择而已，如下改写qsort方法：defqsort(self,low,high):根据序列长短，选择使用