溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
記錄python幾個算法的實例分析，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。
（一）插入排序
插入排序原址排序輸入的數，算法在數組A中重排這些數，
在任何時候，最多只有常數個數字存儲在數組外部。
插入排序是原地排序，基本無需外部空間。
從第二個元素開始，依次遍歷全部數組。
其中，前半截為已排好的有序數組而后半截為待排序的無序數組。
每個元素從后向前依次對比，直到找到自己的位置。
插入排序是穩定排序。
def insert_sort(list1):
for j in range(1,len(list1)): # 從第二個元素開始遍歷，依次將元素放在指定位置
key = list1[j] #記錄當前值
i = j -1 #將當前值從當前位置之前逆序依次比較
while i>=0 and list1[i] >key:#如果當前值小于之前值，則說明當前值位于之前值的前面
list1[i+1] = list1[i] #將大于當前值的元素依次后移一位，給當前值留位置
i -=1
list1[i+1] = key # 將當前值插入第一個小于它的值的后面
return list1
if __name__ == "__main__":
list1 = [380,22,64,75,327,98]
list2 = ["wang","zhe","tian","jin","da","xue"]
ordered_list1 = insert_sort(list1)
ordered_list2 = insert_sort(list2)
print(ordered_list1) #[2,3,4,5,6,7]
print(ordered_list2) #['da']
（2）冒泡排序
冒泡排序原址排序輸入的數，算法在數組A中重排這些數，
在任何時候，最多只有常數個數字存儲在數組外部。
冒泡排序是原地排序，基本無需外部空間。
冒泡排序依次循環數組，每輪循環從前向后依次比較兩個元素，排列使得后一個元素總是大于前一個元素。
因此，每輪循環可以保證當前未排序的列表中最大的元素放置在列表末尾。
即每輪循環后，可以使得未排序的列表長度減1。
重復直到列表僅剩唯一一個元素。
冒泡排序是穩定排序。
Python實現代碼如下：
# -*- coding: utf-8 -*-
def bubbleSort(bubbleList):
listLength = len(bubbleList) #計算排序列表的長度
while listLength > 0:
for i in range(listLength - 1):
if bubbleList[i] > bubbleList[i+1]:
temp = bubbleList[i+1]
bubbleList[i+1] = bubbleList[i]
bubbleList[i] = temp #交換bubbleList[i]與bubbleList[i+1]的值
listLength -= 1 #每輪排序結束后，最后一個元素已經是最大的。因此只需要排前N-1個元素即可。
return bubbleList
if __name__ == '__main__':
list1 = [3,2,4,6,7,5]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = bubbleSort(list1)
ordered_list2 = bubbleSort(list2)
print(ordered_list1) #[2, 3, 4, 5, 6, 7]
print(ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
（3）
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
歸并排序是通過遞歸和合并來實現的。
即首先將一個列表分為兩個字列表，字列表長度為1。然后在依次合并，使得合成的列表有序。
歸并排序的時間復雜度是nlogn。空間復雜度是n。
歸并排序是穩定排序。
Python的實現代碼如下：
# -*- coding: utf-8 -*-
def mergeSort(lists):
if len(lists) <= 1: #當數組長度為1時，則無需排序。
return lists
num = int(len(lists) / 2) #將一個數組分為兩個部分
left = mergeSort(lists[:num]) #分別對左右兩個部分進行排序
right = mergeSort(lists[num:])
return merge(left, right) #將左右兩個有序數組合并為一個有序數組
def merge(left, right):
r, l = 0, 0 #初始化左右索引為0
result = [] #初始化結果列表
while l < len(left) and r < len(right): #當左右索引都尚未達到列表長度時。
if left[l] < right[r]: #如果左列表的值小于右列表的值
result.append(left[l]) #將左列表當前值存入結果列表中
l += 1 #左列表索引加1
else:
result.append(right[r]) #否則將右列表當前值存入結果列表中
r += 1 #右列表索引加1
result += right[r:] #將剩余元素存入結果列表中
result += left[l:]
return result
if __name__ == '__main__':
list1 = [3,2,4,6,7,5]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = mergeSort(list1)
ordered_list2 = mergeSort(list2)
print (ordered_list1) #[2, 3, 4, 5, 6, 7]
print (ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
（4）
快速排序是指：
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
快速排序在平均情況下時間復雜度為nlogn。
但是在最壞情況（本身為正序或者逆序時），時間復雜度為n*n。
快速排序是不穩定排序。即對于本身值相同的元素，在經過快速排序后，元素的先后位置可能會發生變化。
一趟快速排序的算法是：
1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；
4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
5）重復第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
Python的實現方式如下：
# -*- coding: utf-8 -*-
def quickSortFunction(L, low, high):
i = low #i表示被排序列表的起點
j = high #j表示被排序列表的終點
if i >= j: #若當起點和終點重合或起點在終點后時，則無需進一步排序
return L
key = L[i] #將起點元素選為被對比元素
while i < j: #當起點與終點尚未重合時
while i < j and L[j] >= key: #找到第一個小于key的元素的位置
j -= 1
L[i] = L[j] #將第一個小于key元素的值放入key元素的位置
while i < j and L[i] <= key: #找到第一個大于key元素值，放入剛才小于key元素的位置
i += 1
L[j] = L[i]
L[i] = key #當i和j重合時，將key元素放置在重合位置。表示該位置前的元素都小于該元素，而該位置后的元素都大于該元素。
quickSortFunction(L, low, i-1) #利用歸并的方法繼續對low到i-1和j+1到high的部分進行排序
quickSortFunction(L, j+1, high)
return L
def quickSort(list1): #調用quickSortFunction進行快速排序
return quickSortFunction(list1, 0, len(list1)-1) #low和high分別為0和len-1，表示對列表整體進行快速排序
if __name__ == '__main__':
list1 = [3,2,4,6,7,5,1,8,10,9]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = quickSort(list1)
ordered_list2 = quickSort(list2)
print (ordered_list1) #[2, 3, 4, 5, 6, 7]
print (ordered_list2) #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
（5）堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。
可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即A[PARENT[i]] >= A[i]。
在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
堆排序首先將待排序的數組存入堆中，并將堆構造為最大/最小堆。再依次從堆中取出堆頂元素，從而得到有序數組。
構造堆時，所用的方法為從最底層有子節點的節點開始依次向上處理。
取出頂元素恢復堆時則是先將末尾元素與頂元素交換位置，在對頂元素進行下沉處理即可。
堆排序是不穩定排序。即相同的元素再經過堆排序后，其先后位置可能發生變化。
堆排序的時間復雜度為N*logN。
Python的代碼實現如下：
[python] view plain copy
# -*- coding: utf-8 -*-
#用列表表示一個堆，其中列表中索引為0的位置為空。從索引1開始存放元素。
def parent(i): #在堆中，某個節點的父節點為其索引值整除2。例如索引為4的父節點的索引為2。索引為9的父節點的索引為4。
return i/2
def left(i): #某個節點的左子節點的索引為i*2
return i*2
def right(i): #某個節點的右子節點的索引為i*2+1
return i*2+1
class Heap: #堆的數據結構類
def __init__(self, heapList=[None]): #對堆進行初始化。沒有給堆初始列表時，初始化為僅包含一個None元素的列表。
self.heapList = [None] + heapList #有初始化列表時，堆列表為初始化列表前插入None元素
def max_heapfy(self, i): #表明對i節點進行最大堆恢復
if (i*2) > self.length-1: #該元素沒有子節點時
maxIndex = i
elif (i*2+1) > self.length-1: #該元素只有左節點時
maxIndex = left(i)
elif self.heapList[left(i)] > self.heapList[right(i)]: #該元素同時有左右節點，且左節點的值大于右節點時
maxIndex = left(i)
else: #該元素同時有左右節點，且左節點的值小于右節點時
maxIndex = right(i)
if self.heapList[i] < self.heapList[maxIndex]: #當其子節點值大于其節點值時：
self.heapList[i], self.heapList[maxIndex] = self.heapList[maxIndex], self.heapList[i]
#交換其子節點的值和其值
self.max_heapfy(maxIndex) #并對其子節點進行最大堆化
def build_max_heap(self): #構建最大堆
self.length = len(self.heapList) #計算堆的大小（包含第一個空元素）
for i in range(self.length/2, 0, -1): #從包含子節點的節點開始依次向上遍歷
self.max_heapfy(i)
def insert(self, k): #向堆內插入元素
self.length += 1 #堆的規模加1
self.heapList.append(float("-inf")) #向堆內插入一個負無窮的數
self.increase_key(self.length, k) #增加元素
def maxinum(self): #查詢堆內最大元素，即為索引為1的元素值。
return self.heapList[1]
def extract_max(self): #彈出堆內最大元素。
maxValue = self.heapList[1] #取得最大元素值
self.heapList[1] = self.heapList[self.length] #將末尾元素移至堆頭
del self.heapList[self.length] #刪除末尾元素
self.length -= 1 #將堆的規模減1
self.max_heapfy(1) #對堆頂元素最大堆化
return maxValue
def increase_key(self, x, k): #增加元素
self.heapList[x] = k #將新增的負無窮位置賦予插入值
while x > 1 and self.heapList[parent(x)] < self.heapList[x]: #當元素索引大于1且其值大于其父節點值
self.heapList[parent(x)], self.heapList[x] = self.heapList[x], self.heapList[parent(x)]
#交換其值和其父節點的值
x = parent(x) #繼續對其父節點進行判斷
def show(self): #展示堆
print "the length of queue is", self.length - 1
print "the heapList is", self.heapList[1:]
def heapSort(unsortedList):
heap = Heap(unsortedList) #將亂序列表轉換為堆
heap.build_max_heap() #將堆構建為最大堆
print heap.heapList
print "*************heap has been build up*********"
for i in range(len(unsortedList), 1, -1):
heap.heapList[i], heap.heapList[1] = heap.heapList[1], heap.heapList[i] #將末尾節點與根節點進行交換，
#交換完成后，i位置的節點為當前堆中最大的元素。即每次循環中得到的i索引的元素為已有序的列表。
heap.length -= 1 #未排序的堆的規模減小1
heap.max_heapfy(1) #此時，根節點不滿足最大堆的要求，需要對堆進行最大堆恢復
return heap.heapList[1:]
if __name__ == '__main__':
list1 = [3,2,4,6,7,5,1,8,10,9]
list2 = ["wang", "zhe", "tian", "jin", "da", "xue"]
ordered_list1 = heapSort(list1)
ordered_list2 = heapSort(list2)
print ordered_list1 #[2, 3, 4, 5, 6, 7]
print ordered_list2 #['da', 'jin', 'tian', 'wang', 'xue', 'zhe']
看完上述內容，你們掌握記錄python幾個算法的實例分析的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
