1、基于python的七種經(jīng)典排序算法一、排序的基本概念和分類所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序的穩(wěn)定性：經(jīng)過(guò)某種排序后，如果兩個(gè)記錄序號(hào)同等，且兩者在原無(wú)序記錄中的先后秩序依然保持不變，則稱所使用的排序方法是穩(wěn)定的，反之是不穩(wěn)定的。內(nèi)排序和外排序內(nèi)排序：排序過(guò)程中，待排序的所有記錄全部放在內(nèi)存中外排序：排序過(guò)程中，使用到了外部存儲(chǔ)。通常討論的都是內(nèi)排序。影響內(nèi)排序算法性能的三個(gè)因素： 時(shí)間復(fù)雜度：即時(shí)間性能，高效率的排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和記錄的移動(dòng)次數(shù) 空間復(fù)雜度：主要是

2、執(zhí)行算法所需要的輔助空間，越少越好。 算法復(fù)雜性。主要是指代碼的復(fù)雜性。根據(jù)排序過(guò)程中借助的主要操作，可把內(nèi)排序分為： 插入排序 交換排序 選擇排序 歸并排序按照算法復(fù)雜度可分為兩類： 簡(jiǎn)單算法：包括冒泡排序、簡(jiǎn)單選擇排序和直接插入排序 改進(jìn)算法：包括希爾排序、堆排序、歸并排序和快速排序以下的七種排序算法只是所有排序算法中最經(jīng)典的幾種，不代表全部。二、冒泡排序冒泡排序(、Bubblesort):時(shí)間復(fù)雜度O(nA2)交換排序的一種。其核心思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。其實(shí)現(xiàn)細(xì)節(jié)可以不同，比如下面3種:1.最簡(jiǎn)單排序?qū)崿F(xiàn)：bubble_sort_simp

3、le2.冒泡排序：bubble_sort3.冒泡排序算法改進(jìn)的冒泡排序:bubble_sort_advance#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#classSQListIldef_init_(self,lis=None):self.rj|=lisIldefswap(self,i,j):定義一個(gè)交換元素的方法，方便后面調(diào)用。temp=self.riself.ri=self.rjself.rj=tempdefbubble_sort_simple(self):最簡(jiǎn)單的交換排序，時(shí)間復(fù)雜度O(nA2)len

4、gth=len|(self.r)|foriinrange(length):forjin.range|(i+1,length):iflisilisjself.swap(i,j)defbubble_sort(self):冒泡排序，時(shí)間復(fù)雜度O(n2)lis=iself.rlength=len(self.r)|foriin匚range(length):j1=length|-2whilej=i:|iflisjlisj+1:|+1)|self.swap(j,jj-=1冒泡排序改進(jìn)算法，時(shí)間復(fù)雜度O(n2)設(shè)置flag,當(dāng)一輪比較中未發(fā)生交換動(dòng)作，則說(shuō)明后面的元素其實(shí)已經(jīng)有序排列了。對(duì)于比較規(guī)整的元素集合

5、，可提高一定的排序效率。lisself.rlength=len|(self.r)|flag=Truewhilei=i:|iflisjlisj+1:self.swap(j,j+1)flag1=Truej-=1i|+=匚1def_str_(self):retforiinself.r:ret+=%sreturnretmainif-_namesqlist=SQList(4,1,7,3,8,5,9,2,6)#sqlist.bubble_sort_simple()#sqlist.bubble_sort()sqlist.bubble_sort_advance()print(sqlist)三、簡(jiǎn)單選擇排序簡(jiǎn)單

6、選擇排序(simpleselectionsort):時(shí)間復(fù)雜度O(n、2)通過(guò)n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i(1=ilisj:minimumifi!=minimum:self.swap(i,minimum)def_str_(self):retforiinself.r:ret+=T,sreturnretif_name_M=r-_mainsqlist=SQList(4,1,7,3,8,5,9,2,6,0)sqlist.select_sort0print(sqlist)四、直接插入排序直接插入排序(StraightInsertionSort):時(shí)間復(fù)雜度

7、O(nA2)基本操作是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#直接插入排序classSQListdef_init_(self,lis=None):self.r|=lisdefinsert_sort(self):length=len(self.r)#下標(biāo)從1開始foriinrange(1,length):iflisitemp|andj|=口。:lisj+1=lisjlisj+1=tempdef_str_(self):retfori

8、inself.r:ret+=.%s：%ireturnretif_name_=_main匚sqlist=SQList(4,1,7,3,8,5,9,2,|6,0)sqlist.insert_sort0print(sqlist)O(n)。然而，這基本是幻想。該算法需要一個(gè)記錄的輔助空間。最好情況下，當(dāng)原始數(shù)據(jù)就是有序的時(shí)候，只需要一輪對(duì)比，不需要移動(dòng)記錄，此時(shí)時(shí)間復(fù)雜度為五、希爾排序希爾排序(ShellSort)是插入排序的改進(jìn)版本，其核心思想是將原數(shù)據(jù)集合分割成若干個(gè)子序列，然后再對(duì)子序列分別進(jìn)行直接插入排序，使子序列基本有序，最后再對(duì)全體記錄進(jìn)行一次直接插入排序。這里最關(guān)鍵的是跳躍和分割的策略，

9、也就是我們要怎么分割數(shù)據(jù)，間隔多大的問題。通常將相距某個(gè)增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。下面的例子中通過(guò):increment=int(increment/3)+1來(lái)確定增量”的值。希爾排序的時(shí)間復(fù)雜度為：O(n(3/2)希爾排序#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#classSQList:def_init_(self,lis=None):|self.r|=lis|FHdefshell_sort(self):加希爾排序|lis|

10、=|self.r|length=l1len(lis)|increment1=len(lis)whileincrementincrementint(increment/3)+1foriinrange(increment+1,length):iflisi=J|0jandpemp|=口0:-1Pself.heap_adjust(i,length#逆序遍歷整個(gè)序列，不斷取出根節(jié)點(diǎn)的值，完成實(shí)際的排序。=length-1whilej0:#將當(dāng)前根節(jié)點(diǎn)，也就是列表最開頭，下標(biāo)為0的值，交換到最后面j處self.swap(0,j)|#將發(fā)生變化的序列重新構(gòu)造成大頂堆self.heap_adjust(0,j-

11、1)defheap_adjust(self,s,m):核心的大頂堆構(gòu)造方法，維持序列的堆結(jié)構(gòu)。lisself.rtemp=liss2*sJLalwhileii=m:lissifim-landlisi=lisi:breaklisslisii*=f-2=tempdef_str_(self):|retforiin-jself.r:ret+=.%s口%iIreturnretmainsqlist=SQList(4,1,7,3,8,5,9,|2,|6,0,123,22)sqlist.heapsort0print(sqlist)堆排序的運(yùn)行時(shí)間主要消耗在初始構(gòu)建堆和重建堆的反復(fù)篩選上。其初始構(gòu)建堆時(shí)間復(fù)雜度

12、為O(n)。正式排序時(shí)，重建堆的時(shí)間復(fù)雜度為O(nlogn)所以堆排序的總體時(shí)間復(fù)雜度為O(nlogn)堆排序?qū)υ加涗浀呐判驙顟B(tài)不敏感，因此它無(wú)論最好、最壞和平均時(shí)間復(fù)雜度都是O(nlogn)。在性能上要好于冒泡、簡(jiǎn)單選擇和直接插入算法。空間復(fù)雜度上，只需要一個(gè)用于交換的暫存單元。但是由于記錄的比較和交換是跳躍式的，因此，堆排序也是一種不穩(wěn)定的排序方法。此外，由于初始構(gòu)建堆的比較次數(shù)較多，堆排序不適合序列個(gè)數(shù)較少的排序工作。七、歸并排序歸并排序(MergingSort):建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(DivideandConquer)的一個(gè)非常典型的應(yīng)用。將已有序

13、的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。#!/usr/bin/envpython#-*-coding:utf-8-*-#Author:LiuJiang#Python3.5#歸并排序classSQList匚二|definit(self,lis=None):self.rlisdefswap(self,i,j):定義一個(gè)交換元素的方法，方便后面調(diào)用。tempself.riI1=self.rjself.rjI1=tempdefmerge_sort(self):Iself.msort(Iself.r,Iself.r,10,

14、len(self.r)I1-1匚二|defmsort(self,list_sr,list_tr,s,t):temp=Noneforiinrange(0,len(list_sr)I)s=t:list_trs=list_srs|felse:|m=int|(s+t)|/2|)|self.msort(list_sr,temp,s,m)self.msort(list_sr,temp,m+1,t)self.mertdefmerge(self,list_sr,list_tr,i,m,n):m+1whilei|=m|andj|=n:|iflist_srilist_srj:list_trklist_srii+=

15、.1elselist_trk=list_srj|j+=1k+=|-1iflil=m:forlinrange(0,m-i+1):listtrk+l=listsri+lifj=n:forlin匚range|(0,n-j+1):|list_trk+l=list_srj+ldef_str_(self):retforiinself.r:ret+=n%s.%iIreturnretmainI-sqlist=SQList(4,1,7,3,8,5,9,2,6,0,12,77,34,23)sqlist.merge_sort()print(sqlist)O(nlogn)歸并排序?qū)υ夹蛄性胤植记闆r不敏感，其時(shí)間復(fù)

16、雜度為歸并排序在計(jì)算過(guò)程中需要使用一定的輔助空間，用于遞歸和存放結(jié)果,因此其空間復(fù)雜度為O(n+logn)歸并排序中不存在跳躍，只有兩兩比較，因此是一種穩(wěn)定排序。總之，歸并排序是一種比較占用內(nèi)存，但效率高，并且穩(wěn)定的算法。八、快速排序快速排序(QuickSort)由圖靈獎(jiǎng)獲得者TonyHoare發(fā)明，被列為20世紀(jì)十大算法之一。冒泡排序的升級(jí)版，交換排序的一種。快速排序的時(shí)間復(fù)雜度為O(nlog(n)快速排序算法的核心思想：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后分別對(duì)這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)記錄集合的排序目的。#!/usr/bi

17、n/envpython#-*-:utf-8-*-#Author:LiuJiang#Python3.5#快速排序classSQList:def_init_(self,lis=None):|self.r=lis|I|defswap(self,i,j):定義一個(gè)交換元素的方法，方便后面調(diào)用。|temp1=self.riself.ri=self.rjself.rj|=temp|defquick_sort(self):調(diào)用入口self.qsort(0,len(self.r)|-1)I|defqsort(self,low,high):遞歸調(diào)用iflowhigh:pivot=self.partition(l

18、ow,high)self.qsort(low,pivot-1Pself.qsort(pivot+1,high)|defpartition(self,low,high):它自己也在交換中不斷變換自己的位右邊界下標(biāo):return:分“快速排序的核心代碼。其實(shí)就是將選取的pivot_key不斷交換，將比它小的換到左邊，將比它大的換到右邊。置，直到完成所有的交換為止。但在函數(shù)調(diào)用的過(guò)程中，pivot_key的值始終不變。：paramlow:左邊界下標(biāo)：paramhigh:完左右區(qū)后pivot_key所在位置的下標(biāo)Ilis1=-iself.rpivot_key=lislowIwhilelow=pivot

19、_key:whilelowhighandlishighhigh-=1self.swap(low,high)whilelowhighandlislowlishigh:self.swap(low,high)iflism|lishigh:(high,m)iflismlislow:self.swap(m,low)如果覺得這樣還不夠好，還可以將整個(gè)序列先劃分為3部分，每一部分求出個(gè)pivot_key,再對(duì)3個(gè)pivot_key再做一次上面的比較得出最終的pivot_key。這時(shí)的pivot_key應(yīng)該很大概率是一個(gè)比較靠譜的值。2.減少不必要的交換原來(lái)的代碼中pivot_key這個(gè)記錄總是再不斷的交換中

20、，其實(shí)這是沒必要的，完全可以將它暫存在某個(gè)臨時(shí)變量中，如下所示:defpartition(self,low,high):lis1=self.rm|=low|匚int|(high|-low)1/21)|iflislow|lishigh:iflismlishigh:self.swap(high,m)iflismlislow:self.swap(m,low)pivotkey=lislow#temp暫存pivot_key的值temp=pivot_keywhilelowhigh:whilelow=pivot_key:high|-=1#直接替換，而不交換了lislow=lishighwhilelow|hi

21、ghandlislow=pivot_key:low+=1lishigh1=lislowIlislow1=temp|returnlow3.優(yōu)化小數(shù)組時(shí)的排序快速排序算法的遞歸操作在進(jìn)行大量數(shù)據(jù)排序時(shí)，其開銷能被接受，速度較快。但進(jìn)行小數(shù)組排序時(shí)則不如直接插入排序來(lái)得快，也就是殺雞用牛刀，未必就比菜刀來(lái)得快。qsort方法:因此，一種很樸素的做法就是根據(jù)數(shù)據(jù)的多少，做個(gè)使用哪種算法的選擇而已，如下改寫defqsort(self,low,high):根據(jù)序列長(zhǎng)短，選擇使用快速排序還是簡(jiǎn)單插入排序#7是一個(gè)經(jīng)驗(yàn)值，可根據(jù)實(shí)際情況自行決定該數(shù)值。MAXLENGTHifhigh-lowMAX_LENGTH:iflow|high:|pivot=self.