1、序言

本文使用Python實(shí)現(xiàn)了一些常用的排序方法。文章結(jié)構(gòu)如下：

1.直接插入排序

2.希爾排序

3.冒泡排序

4.快速排序

5.簡單選擇排序

6.堆排序

7.歸并排序

8.基數(shù)排序

上述所有的排序均寫在一個(gè)Python自定義類中，作為成員函數(shù)。

2、排序方法詳細(xì)介紹

1.直接插入排序

直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法，它的基本操作是一個(gè)值插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。如下圖所示：

由上圖可知若最初始的有序表即為數(shù)組的第一個(gè)元素。用Python實(shí)現(xiàn)如下：

defstraight_insertion_sort(self, value_list):"""直接插入排序

:param value_list: 無序列表

:return:"""

return self.__straight_insert(value_list)

@staticmethoddef __straight_insert(value_list):

sorted_list=[]

sorted_list.append(value_list.pop(0))for i inrange(0, len(value_list)):

tail= True #是否在尾部插入

insert_loc =0for j inrange(len(sorted_list)):if value_list[i] <=sorted_list[j]:

tail=False

insert_loc=jbreaksorted_list.append(value_list[i])#先將值插入尾部

if nottail:#移動值

for j in range(len(sorted_list) - 1, insert_loc, -1):

temp=sorted_list[j]

sorted_list[j]= sorted_list[j - 1]

sorted_list[j- 1] =tempreturn sorted_list

2.希爾排序

希爾排序（Shell’s Sort）又稱“縮小增量排序”（Diminishing Incerement Sort），它也是一種數(shù)插入排序的方法，但在時(shí)間效率上較前面的排序方法有較大的改進(jìn)。它的基本思想是：先將整個(gè)待排記錄序列分割成若干個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。如下圖所示：

即根據(jù)增量將原序列分割成多個(gè)子序列進(jìn)行直接插入排序。增量應(yīng)不斷減小，且最后一個(gè)增量為1。用Python實(shí)現(xiàn)如下：

defshells_sort(self, value_list):"""希爾排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""gap= len(value_list) // 2

while gap >= 1:

i=0while(i + gap)

start=i

gap_list=[]while start

gap_list.append(value_list[start])

start= start +gap

gap_list= self.__straight_insert(gap_list)

start=iwhile start

value_list[start]=gap_list.pop(0)

start+=gap

i+= 1gap//= 2sorted_list=value_listreturn sorted_list

3.冒泡排序

冒泡排序（Bubble Sort）的過程很簡單。首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若逆序（與需要的順序相反），則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，以此類推。為第一趟冒泡結(jié)束，接著對前n-1個(gè)記錄繼續(xù)進(jìn)行上述的過程。這樣重復(fù)的過程直至n-1=1結(jié)束。排序過程如下所示：

用Python實(shí)現(xiàn)如下：

@staticmethoddefbubble_sort(value_list):"""冒泡排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""

for i in range(len(value_list) - 1):for j in range(i + 1, len(value_list)):if value_list[i] >value_list[j]:

value_list[i], value_list[j]=value_list[j], value_list[i]

sorted_list=value_listreturn sorted_list

4.快速排序

快速排序（Quick Sort）是對冒泡排序的一種改進(jìn)。它的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，已達(dá)到整個(gè)序列有序。其排序思想如下：

首先任意選取一個(gè)記錄（通常可選第一個(gè)記錄）作為樞軸，然后按下述原則重新排列記錄：將所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它大的記錄都安置在它的位置之后。一趟快速排序的具體做法是：設(shè)兩個(gè)指針low和high，他們的初值分別為最低位置的下一個(gè)位置和最高位，設(shè)最低位置樞軸的關(guān)鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于pivotkey的記錄的樞軸記錄互相交換。發(fā)生了交換后才從low所指向的位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換。重復(fù)這兩步直至low=how為止

如下圖所示：

特別要注意換方向的時(shí)機(jī)是發(fā)生了交換后，用Python實(shí)現(xiàn)如下：

defquick_sort(self, value_list):"""快速排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""low=0

high= len(value_list) - 1self.__qsort(value_list, low, high)

sorted_list=value_listreturnsorted_listdef __qsort(self, val_list, low, high):"""快速排序輔助函數(shù)

:param val_list: 無序列表

:param low: 低位

:param high: 高位

:return:"""

if low >=high:returnpivot_key=low

temp_low=pivot_key

temp_high=highwhile low

while low

temp=val_list[high]

val_list[high]=val_list[pivot_key]

val_list[pivot_key]=temp

pivot_key=highbreak #發(fā)生交換后，就換方向

else:

high-= 1

while low val_list[pivot_key]:

temp=val_list[low]

val_list[low]=val_list[pivot_key]

val_list[pivot_key]=temp

pivot_key=lowbreak #發(fā)生交換后，就換方向

else:

low+= 1self.__qsort(val_list, temp_low, pivot_key - 1)

self.__qsort(val_list, pivot_key + 1, temp_high)

5.簡單選擇排序

選擇排序（Selection Sort）是一種簡單直觀的排序算法。它的基本思想是：每一趟在n-i+1(i=1,2,...,n-1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個(gè)記錄。簡單選擇排序：通過n-1次關(guān)鍵字的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i(1≤i≤n)個(gè)記錄交換之。如下圖所示：

用Python實(shí)現(xiàn)如下：

@staticmethoddefsimple_selection_sort(value_list):"""簡單選擇排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""

for i inrange(len(value_list)):

min_val= 9999999

for j inrange(i, len(value_list)):if min_val >value_list[j]:

min_val=value_list[j]

count= 0 #如果有多個(gè)相同的最小值

for j inrange(i, len(value_list)):if min_val ==value_list[j]:

value_list[j], value_list[i+ count] = value_list[i +count], value_list[j]

sorted_list=value_listreturn sorted_list

6.堆排序

堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆的定義如下：

n個(gè)元素的序列{k1,k2,...,kn}當(dāng)且僅當(dāng)滿足一下關(guān)系時(shí)，稱之為堆。

若將序列看成是一個(gè)完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端節(jié)點(diǎn)均不大于（或不小于）其左、右孩子節(jié)點(diǎn)的值。由此，若序列是堆，則堆頂元素必為序列中的最小值（或最大值）。如下圖所示：

至此，我們可以給出堆排序的過程：若在輸出堆頂?shù)淖钚≈岛?#xff0c;使得剩余n-1個(gè)元素的序列又建成一個(gè)堆，則得到n個(gè)元素中的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列。

故整個(gè)堆排序可以大致分為兩個(gè)過程：

·將無序序列建成堆。

·輸出堆頂元素后，用類似建堆的方法調(diào)整堆。

如下兩個(gè)圖所示：

根據(jù)堆排序的特點(diǎn)總結(jié)出兩點(diǎn)注意事項(xiàng)：

1.利用把堆看成完全二叉樹的特點(diǎn)，用完全二叉樹的性質(zhì)解決算法問題。

2.建堆的過程是從樹種的最后一個(gè)非終端節(jié)點(diǎn)逆序開始調(diào)整的。

3.每調(diào)整一次需要檢查前后是否依然保持堆的特征。

本文利用了二叉樹的孩子兄弟表示法來生成二叉樹（堆）的。代碼如下：

classCldSibNode(object):"""私有內(nèi)部類：孩子兄弟二叉鏈表節(jié)點(diǎn)"""

def __init__(self, val):

self.value=val

self.child=None

self.sibling=Nonedefheap_sort(self, value_list):"""堆排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""sorted_list=[]

root_node=self.CldSibNode(None)

self.__child_sibling(root_node, value_list, 0)for ct in range(1, len(value_list) // 2 + 1): #建堆

self.__adjust_heap(root_node, len(value_list) // 2 + 1 - ct, 1)for i in range(1, len(value_list) + 1): #堆排序

sorted_list.append(root_node.value) #輸出堆頂元素

head =root_node

self.__shrink_heap(root_node, len(value_list) + 1 - i, 1, head)

self.__adjust_heap(root_node, 1, 1) #調(diào)整堆

returnsorted_listdef __child_sibling(self, node, value_list, ind):"""創(chuàng)建完全二叉樹的左孩子右兄弟二叉鏈表

:param node: 當(dāng)前節(jié)點(diǎn)

:param value_list: 待排序的無序列表

:param ind:

:return:"""

if ind >=len(value_list):returnnode.value=value_list[ind]if ind * 2 + 1

node.child= self.CldSibNode(None) #孩子

self.__child_sibling(node.child, value_list, ind * 2 + 1)if ind * 2 + 2

node.child.sibling= self.CldSibNode(None) #兄弟

self.__child_sibling(node.child.sibling, value_list, ind * 2 + 2)def __adjust_heap(self, root_node, last_ind, now_ind):if not root_node or not root_node.child: #不為空且有孩子

return

if now_ind ==last_ind:#需要調(diào)整的非終端節(jié)點(diǎn)

temp =root_node

cg=Falsewhiletemp.child:if temp.value >temp.child.value:

temp.value, temp.child.value=temp.child.value, temp.value

cg= True #發(fā)生交換

iftemp.child.sibling:if temp.value >temp.child.sibling.value:ifcg:#如果發(fā)生過交換

temp.value, temp.child.value =temp.child.value, temp.value

temp.value, temp.child.sibling.value=temp.child.sibling.value, temp.value

temp=temp.child.siblingcontinue

else:ifcg:#如果發(fā)生過交換

temp =temp.childcontinue

break

#遞歸

self.__adjust_heap(root_node.child, last_ind, now_ind * 2)ifroot_node.child.sibling:

self.__adjust_heap(root_node.child.sibling, last_ind, now_ind * 2 + 1)def __shrink_heap(self, root_node, last_ind, now_ind, head):if not root_node or now_ind * 2 >last_ind:#為空

return

if last_ind == now_ind * 2 + 1:

head.value=root_node.child.sibling.value

root_node.child.sibling=NonereturnTrueif last_ind == now_ind * 2:

head.value=root_node.child.value

root_node.child=NonereturnTrueifroot_node.child:

self.__shrink_heap(root_node.child, last_ind, now_ind * 2, head)

self.__shrink_heap(root_node.child.sibling, last_ind, now_ind * 2 + 1, head)

7.歸并排序

歸并排序（Merging Sort），“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。假設(shè)初始序列有n個(gè)記錄，則可看成是n個(gè)有序的子序列，每個(gè)子序列的長度為1，然后兩兩歸并，得到[n/2]個(gè)長度為2或1的有序子序列；再兩兩歸并，……，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止，這種排序方法為2-路歸并排序。算法的基本思想如下圖所示：

其中兩個(gè)子序列的合并大有學(xué)問，基本思想就是：分別在兩個(gè)序列頭設(shè)置指針，比較兩個(gè)序列指針?biāo)傅闹档拇笮?#xff0c;將滿足要求的值提取出來形成新列表，并將指針右移。當(dāng)其中一個(gè)指針指向結(jié)尾之后時(shí)，表示其中一個(gè)列表已取盡，接著直接在新列表尾部連接另一個(gè)列表。如下圖所示：

用Python實(shí)現(xiàn)如下：

@staticmethoddefmerging_sort(self, value_list):"""歸并排序

:param value_list: 待排序的無序列表

:return: 排序后的新列表"""i=0while np.power(2, i)

count= np.power(2, i)

start=0

outer_temp=[]while start

other = start +count

temp=[]if other >=len(value_list):#另一邊不存在：直接合并

outer_temp.extend(value_list[start: start +count])breakleft, right=0, 0while left < count or right =len(value_list):#右邊提前結(jié)束

temp.extend(value_list[start + left: start +count])break

elif value_list[start + left] < value_list[other +right]:#左邊更小

temp.append(value_list[start +left])

left+= 1

if left ==count:#左邊遍歷結(jié)束

temp.extend(value_list[other + right: other +count])break

else:#右邊更小

temp.append(value_list[other +right])

right+= 1

if right ==count:#右邊遍歷結(jié)束

temp.extend(value_list[start + left: start +count])breakouter_temp.extend(temp)

start+= count * 2value_list=outer_temp

i+= 1sorted_list=value_listreturn sorted_list

8.基數(shù)排序

基數(shù)排序（Radix Sort）是一種非比較整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

排序時(shí)有兩點(diǎn)需要注意：

1.每完成一趟排序，要清空隊(duì)列。

2.隊(duì)列的連接要找到第一個(gè)不為空的隊(duì)列作為頭，和繞開所有空隊(duì)列。

用Python實(shí)現(xiàn)如下：

@staticmethoddefradix_sort(value_list):"""基數(shù)排序

:param value_list: 待排序的無序列表

:return: 排序后的新列表"""i=0

max_num=max(value_list)

n=len(str(max_num))while i

bucket_list = [[] for _ in range(10)]for x invalue_list:#找到位置放入桶數(shù)組

bucket_list[int(x / (10 ** i)) % 10].append(x)

value_list.clear()for x inbucket_list:#放回原序列

for y inx:

value_list.append(y)

i+= 1sorted_list=value_listreturn sorted_list

測試代碼：

編寫測試代碼運(yùn)行結(jié)果如下：

if __name__ == '__main__':

li= list(np.random.randint(1, 1000, 30))

my_sort=MySort()print("original sequence:", li)print("*" * 100)print("1.straight_insertion_sort:", my_sort.straight_insertion_sort(li.copy()))print("2.shells_sort:", my_sort.shells_sort(li.copy()))print("3.bubble_sort:", my_sort.bubble_sort(li.copy()))print("4.quick_sort:", my_sort.quick_sort(li.copy()))print("5.simple_selection_sort:", my_sort.simple_selection_sort(li.copy()))print("6.heap_sort:", my_sort.heap_sort(li.copy()))print("7.merging_sort:", my_sort.merging_sort(li.copy()))print("8.radix_sort:", my_sort.radix_sort(li.copy()))

測試運(yùn)行結(jié)果：

original sequence: [424, 381, 234, 405, 554, 742, 527, 876, 27, 904, 169, 566, 854, 448, 65, 508, 226, 477, 12, 670, 408, 520, 774, 99, 159, 565, 393, 288, 149, 711]****************************************************************************************************

1.straight_insertion_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]2.shells_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]3.bubble_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]4.quick_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]5.simple_selection_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]6.heap_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]7.merging_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]8.radix_sort: [12, 27, 65, 99, 149, 159, 169, 226, 234, 288, 381, 393, 405, 408, 424, 448, 477, 508, 520, 527, 554, 565, 566, 670, 711, 742, 774, 854, 876, 904]

總結(jié)

各個(gè)排序效率見下圖：

可以得出以下幾個(gè)結(jié)論：

1.從平均時(shí)間性能而言，快速排序最佳。

2.堆排序適用于n較大的數(shù)據(jù)。

3.基數(shù)排序是穩(wěn)定的，時(shí)間復(fù)雜度較大的簡單排序方法也是穩(wěn)定的。

4.穩(wěn)定性是由方法本身決定的。

5.沒有最好的排序方法，視情況而定。

#! /usr/bin/env python3#-*- coding:utf-8 -*-

#Author : MaYi#Blog : http://www.cnblogs.com/mayi0312/#Date : 2020-01-06#Name : mySort#Software : PyCharm#Note : 八大排序算法

importnumpy as npclassMySort(object):"""自定義一個(gè)排序的類"""

defstraight_insertion_sort(self, value_list):"""直接插入排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""

return self.__straight_insert(value_list)

@staticmethoddef __straight_insert(value_list):

sorted_list=[]

sorted_list.append(value_list.pop(0))for i inrange(0, len(value_list)):

tail= True #是否在尾部插入

insert_loc =0for j inrange(len(sorted_list)):if value_list[i] <=sorted_list[j]:

tail=False

insert_loc=jbreaksorted_list.append(value_list[i])#先將值插入尾部

if nottail:#移動值

for j in range(len(sorted_list) - 1, insert_loc, -1):

sorted_list[j], sorted_list[j- 1] = sorted_list[j - 1], sorted_list[j]returnsorted_listdefshells_sort(self, value_list):"""希爾排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""gap= len(value_list) // 2

while gap >= 1:

i=0while(i + gap)

start=i

gap_list=[]while start

gap_list.append(value_list[start])

start= start +gap

gap_list= self.__straight_insert(gap_list)

start=iwhile start

value_list[start]=gap_list.pop(0)

start+=gap

i+= 1gap//= 2sorted_list=value_listreturnsorted_list

@staticmethoddefbubble_sort(value_list):"""冒泡排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""

for i in range(len(value_list) - 1):for j in range(i + 1, len(value_list)):if value_list[i] >value_list[j]:

value_list[i], value_list[j]=value_list[j], value_list[i]

sorted_list=value_listreturnsorted_listdefquick_sort(self, value_list):"""快速排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""low=0

high= len(value_list) - 1self.__qsort(value_list, low, high)

sorted_list=value_listreturnsorted_listdef __qsort(self, val_list, low, high):"""快速排序輔助函數(shù)

:param val_list: 無序列表

:param low: 低位

:param high: 高位

:return:"""

if low >=high:returnpivot_key=low

temp_low=pivot_key

temp_high=highwhile low

while low

temp=val_list[high]

val_list[high]=val_list[pivot_key]

val_list[pivot_key]=temp

pivot_key=highbreak #發(fā)生交換后，就換方向

else:

high-= 1

while low val_list[pivot_key]:

temp=val_list[low]

val_list[low]=val_list[pivot_key]

val_list[pivot_key]=temp

pivot_key=lowbreak #發(fā)生交換后，就換方向

else:

low+= 1self.__qsort(val_list, temp_low, pivot_key - 1)

self.__qsort(val_list, pivot_key + 1, temp_high)

@staticmethoddefsimple_selection_sort(value_list):"""簡單選擇排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""

for i inrange(len(value_list)):

min_val= 9999999

for j inrange(i, len(value_list)):if min_val >value_list[j]:

min_val=value_list[j]

count= 0 #如果有多個(gè)相同的最小值

for j inrange(i, len(value_list)):if min_val ==value_list[j]:

value_list[j], value_list[i+ count] = value_list[i +count], value_list[j]

sorted_list=value_listreturnsorted_listclassCldSibNode(object):"""私有內(nèi)部類：孩子兄弟二叉鏈表節(jié)點(diǎn)"""

def __init__(self, val):

self.value=val

self.child=None

self.sibling=Nonedefheap_sort(self, value_list):"""堆排序

:param value_list: 待排序的無序列表

:return: 排序后的列表"""sorted_list=[]

root_node=self.CldSibNode(None)

self.__child_sibling(root_node, value_list, 0)for ct in range(1, len(value_list) // 2 + 1): #建堆

self.__adjust_heap(root_node, len(value_list) // 2 + 1 - ct, 1)for i in range(1, len(value_list) + 1): #堆排序

sorted_list.append(root_node.value) #輸出堆頂元素

head =root_node

self.__shrink_heap(root_node, len(value_list) + 1 - i, 1, head)

self.__adjust_heap(root_node, 1, 1) #調(diào)整堆

returnsorted_listdef __child_sibling(self, node, value_list, ind):"""創(chuàng)建完全二叉樹的左孩子右兄弟二叉鏈表

:param node: 當(dāng)前節(jié)點(diǎn)

:param value_list: 待排序的無序列表

:param ind:

:return:"""

if ind >=len(value_list):returnnode.value=value_list[ind]if ind * 2 + 1

node.child= self.CldSibNode(None) #孩子

self.__child_sibling(node.child, value_list, ind * 2 + 1)if ind * 2 + 2

node.child.sibling= self.CldSibNode(None) #兄弟

self.__child_sibling(node.child.sibling, value_list, ind * 2 + 2)def __adjust_heap(self, root_node, last_ind, now_ind):if not root_node or not root_node.child: #不為空且有孩子

return

if now_ind ==last_ind:#需要調(diào)整的非終端節(jié)點(diǎn)

temp =root_node

cg=Falsewhiletemp.child:if temp.value >temp.child.value:

temp.value, temp.child.value=temp.child.value, temp.value

cg= True #發(fā)生交換

iftemp.child.sibling:if temp.value >temp.child.sibling.value:ifcg:#如果發(fā)生過交換

temp.value, temp.child.value =temp.child.value, temp.value

temp.value, temp.child.sibling.value=temp.child.sibling.value, temp.value

temp=temp.child.siblingcontinue

else:ifcg:#如果發(fā)生過交換

temp =temp.childcontinue

break

#遞歸

self.__adjust_heap(root_node.child, last_ind, now_ind * 2)ifroot_node.child.sibling:

self.__adjust_heap(root_node.child.sibling, last_ind, now_ind * 2 + 1)def __shrink_heap(self, root_node, last_ind, now_ind, head):if not root_node or now_ind * 2 >last_ind:#為空

return

if last_ind == now_ind * 2 + 1:

head.value=root_node.child.sibling.value

root_node.child.sibling=NonereturnTrueif last_ind == now_ind * 2:

head.value=root_node.child.value

root_node.child=NonereturnTrueifroot_node.child:

self.__shrink_heap(root_node.child, last_ind, now_ind * 2, head)

self.__shrink_heap(root_node.child.sibling, last_ind, now_ind * 2 + 1, head)

@staticmethoddefmerging_sort(value_list):"""歸并排序

:param value_list: 待排序的無序列表

:return: 排序后的新列表"""i=0while np.power(2, i)

count= np.power(2, i)

start=0

outer_temp=[]while start

other = start +count

temp=[]if other >=len(value_list):#另一邊不存在：直接合并

outer_temp.extend(value_list[start: start +count])breakleft, right=0, 0while left < count or right =len(value_list):#右邊提前結(jié)束

temp.extend(value_list[start + left: start +count])break

elif value_list[start + left] < value_list[other +right]:#左邊更小

temp.append(value_list[start +left])

left+= 1

if left ==count:#左邊遍歷結(jié)束

temp.extend(value_list[other + right: other +count])break

else:#右邊更小

temp.append(value_list[other +right])

right+= 1

if right ==count:#右邊遍歷結(jié)束

temp.extend(value_list[start + left: start +count])breakouter_temp.extend(temp)

start+= count * 2value_list=outer_temp

i+= 1sorted_list=value_listreturnsorted_list

@staticmethoddefradix_sort(value_list):"""基數(shù)排序

:param value_list: 待排序的無序列表

:return: 排序后的新列表"""i=0

max_num=max(value_list)

n=len(str(max_num))while i

bucket_list = [[] for _ in range(10)]for x invalue_list:#找到位置放入桶數(shù)組

bucket_list[int(x / (10 ** i)) % 10].append(x)

value_list.clear()for x inbucket_list:#放回原序列

for y inx:

value_list.append(y)

i+= 1sorted_list=value_listreturnsorted_listif __name__ == '__main__':

li= list(np.random.randint(1, 1000, 30))

my_sort=MySort()print("original sequence:", li)print("*" * 100)print("1.straight_insertion_sort:", my_sort.straight_insertion_sort(li.copy()))print("2.shells_sort:", my_sort.shells_sort(li.copy()))print("3.bubble_sort:", my_sort.bubble_sort(li.copy()))print("4.quick_sort:", my_sort.quick_sort(li.copy()))print("5.simple_selection_sort:", my_sort.simple_selection_sort(li.copy()))print("6.heap_sort:", my_sort.heap_sort(li.copy()))print("7.merging_sort:", my_sort.merging_sort(li.copy()))print("8.radix_sort:", my_sort.radix_sort(li.copy()))

完整代碼

總結(jié)

以上是生活随笔為你收集整理的用python排序算法_Python - 八大排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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