下圖是各種排序方法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性，大牛編程吧教你如何編程提升。

1.直接插入排序。

直接插入的基本思想是每一步將一個(gè)數(shù)插入到已排序的有序數(shù)列中。

python代碼實(shí)現(xiàn)：

def direct_insert_sort(l):for i in range(1,len(l)):key = l[i]j = i-1while j>=0:if key<l[j]:l[j+1] = l[j]l[j] = keyj -= 1return l a = [2,3,1,5,4,4]

2.Shell排序（希爾排序）。

希爾排序是直接插入排序的改進(jìn)版本希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

python代碼實(shí)現(xiàn)：

def shell_sort(l):c = len(l)step = len(l)//2while step>0:for i in range(step):j = i+stepwhile j<c:key = l[j]p = j-stepwhile p>=0:if key<l[p]:l[p+step] = l[p]l[p] = keyp -= stepj += stepstep = step//2return l a = [2,3,1,5,4,4] print(shell_sort(a))

3.直接選擇排序。

直接選擇排序是每次找到未排序元素中最小的元素放到最前面具體實(shí)現(xiàn)是第一趟將第一個(gè)元素與后面所有元素比較，小的放前面，第二趟得到第二個(gè)元素，這樣直至排序完成。

python代碼實(shí)現(xiàn)：

def direct_choice_sort(l):for i in range(len(l)-1):for j in range(i+1,len(l)):if l[j]<l[i]:l[i],l[j] = l[j],l[i]return l a = [3,1,4,5,2,2] print(direct_choice_sort(a))

4.堆排序。

堆排序是一種選擇排序，是用堆結(jié)構(gòu)來(lái)完成排序的一種算法，升序用大頂堆，降序用小頂堆；構(gòu)造大頂堆：一個(gè)結(jié)點(diǎn)i的左右葉子結(jié)點(diǎn)為2i+1,2i+2,最后一個(gè)非葉子結(jié)點(diǎn)為len(l)//2-1,從最后一個(gè)非葉子結(jié)點(diǎn)起，開始調(diào)整，將大的元素放到父結(jié)點(diǎn)上。

python代碼實(shí)現(xiàn)：

def heap_sort(l):for j in range(len(l),0,-1):#j為堆的長(zhǎng)度，c為堆的最大非葉子結(jié)點(diǎn)索引c = (j//2)-1#從最大非葉子結(jié)點(diǎn)開始調(diào)整堆for i in range(c,-1,-1):if (2*i+1)<=(j-1) and l[2*i+1]>l[i]:l[i],l[2*i+1] = l[2*i+1],l[i]if (2*i+2)<=(j-1) and l[2*i+2]>l[i]:l[i],l[2*i+2] = l[2*i+2],l[i]#交換堆頂與最后一個(gè)結(jié)點(diǎn)l[0],l[j-1] = l[j-1],l[0]return l a = [67,65,77,38,97,3,33,49,33] #heap(a) print(heap_sort(a))

5.冒泡排序。

冒泡排序是從后向前每次比較相鄰的2個(gè)元素大小，大的放后面，這樣一次遍歷第一個(gè)元素就是最小的，第二次遍歷第二個(gè)元素就是剩下中最小的，這樣直到排序完成。

python代碼實(shí)現(xiàn)：

def Bubble_sort(l):c = len(l)for i in range(1,c):for j in range(c-1,i-1,-1):if l[j] < l[j-1]:l[j],l[j-1] = l[j-1],l[j]return l a = [3,1,4,5,2,2] print(Bubble_sort(a))

6.快速排序。

快速排序的思想是每次任意取一個(gè)元素，如第一個(gè)，將剩下比它小的元素的放到它的前面，大的放到它的后面，這樣這個(gè)元素就已經(jīng)在最終排序完成的位置上了，然后對(duì)小的元素和大的元素繼續(xù)進(jìn)行快速排序，這樣直至排序完成。

python代碼實(shí)現(xiàn)：

quick_sort = lambda l:l if len(l)<=1 else quick_sort([i for i in l[1:] if i<=l[0]])+[l[0]]+quick_sort([i for i in l[1:] if i>l[0]]) a = [3,1,4,5,2,2] print(quick_sort(a))

7.歸并排序。

歸并排序是一個(gè)典型的基于分治的遞歸算法。先將原數(shù)組分成n個(gè)小數(shù)組然后兩兩歸并。

歸并過(guò)程：先比較l1,l2的第一個(gè)元素大小，如果l1大則將l2的第一個(gè)元素添加到輸出數(shù)組o中，然后l2指向第二個(gè)元素繼續(xù)比較，這樣直至排序完成。

python代碼實(shí)現(xiàn)：

def merge(l1,l2):o = []a1 = 0;a2 = 0if l1==[]:return l2if l2==[]:return l1for i in range(len(l1)+len(l2)):if a1 == len(l1):for j in l2[a2:]:o.append(j)elif a2 == len(l2):for j in l1[a1:]:o.append(j)else:if l1[a1]>=l2[a2]:o.append(l2[a2])a2 += 1else:o.append(l1[a1])a1 += 1return o def sort(l):if len(l)<=1:return lc = len(l)//2return merge(sort(l[:c]),sort(l[c:])) a = [67,65,77,38,97,3,33,33] print(sort(a))

基數(shù)排序?qū)懖怀鰜?lái)。。

轉(zhuǎn)載于:https://blog.51cto.com/13962326/2173186

總結(jié)

以上是生活随笔為你收集整理的今天来谈谈Python中的各种排序总结，含实现代码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。