您好,登錄后才能下訂單哦!
這篇文章主要介紹“python查找與排序算法實(shí)例代碼分析”的相關(guān)知識,小編通過實(shí)際案例向大家展示操作過程,操作方法簡單快捷,實(shí)用性強(qiáng),希望這篇“python查找與排序算法實(shí)例代碼分析”文章能幫助大家解決問題。
二分搜索是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結(jié)束;如果某一特定元素大于或者小于中間元素,則在數(shù)組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空,則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
# 返回 x 在 arr 中的索引,如果不存在返回 -1 def binarySearch (arr, l, r, x): # 基本判斷 if r >= l: mid = int(l + (r - l)/2) # 元素整好的中間位置 if arr[mid] == x: return mid # 元素小于中間位置的元素,只需要再比較左邊的元素 elif arr[mid] > x: return binarySearch(arr, l, mid-1, x) # 元素大于中間位置的元素,只需要再比較右邊的元素 else: return binarySearch(arr, mid+1, r, x) else: # 不存在 return -1 # 測試數(shù)組 arr = [ 2, 3, 4, 10, 40] x = int(input('請輸入元素:')) # 函數(shù)調(diào)用 result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print("元素在數(shù)組中的索引為 %d" % result) else: print("元素不在數(shù)組中")
運(yùn)行結(jié)果:
請輸入元素:4
元素在數(shù)組中的索引為 2
請輸入元素:5
元素不在數(shù)組中
線性查找:指按一定的順序檢查數(shù)組中每一個元素,直到找到所要尋找的特定值為止。
def search(arr, n, x): for i in range (0, n): if (arr[i] == x): return i return -1 # 在數(shù)組 arr 中查找字符 D arr = [ 'A', 'B', 'C', 'D', 'E' ] x = input("請輸入要查找的元素:") n = len(arr) result = search(arr, n, x) if(result == -1): print("元素不在數(shù)組中") else: print("元素在數(shù)組中的索引為", result)
運(yùn)行結(jié)果:
請輸入要查找的元素:A
元素在數(shù)組中的索引為 0
請輸入要查找的元素:a
元素不在數(shù)組中
插入排序(Insertion Sort):是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入。
def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key arr = [12, 11, 13, 5, 6, 7, 9, 9, 17] insertionSort(arr) print("排序后的數(shù)組:") print(arr)
運(yùn)行結(jié)果:
排序后的數(shù)組:
[5, 6, 7, 9, 9, 11, 12, 13, 17]
當(dāng)然也可以這樣寫,更簡潔
list1 = [12, 11, 13, 5, 6, 7, 9, 9, 17] for i in range(len(list1)-1, 0, -1): for j in range(0, i): if list1[i] < list1[j]: list1[i], list1[j] = list1[j], list1[i] print(list1)
快速排序;使用分治法(Divide and conquer)策略來把一個序列(list)分為較小和較大的2個子序列,然后遞歸地排序兩個子序列。
步驟為:
挑選基準(zhǔn)值:從數(shù)列中挑出一個元素,稱為"基準(zhǔn)"(pivot);
分割:重新排序數(shù)列,所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面,所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面(與基準(zhǔn)值相等的數(shù)可以到任何一邊)。在這個分割結(jié)束之后,對基準(zhǔn)值的排序就已經(jīng)完成;
遞歸排序子序列:遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。
遞歸到最底部的判斷條件是數(shù)列的大小是零或一,此時該數(shù)列顯然已經(jīng)有序。
選取基準(zhǔn)值有數(shù)種具體方法,此選取方法對排序的時間性能有決定性影響。
def partition(arr, low, high): i = (low-1) # 最小元素索引 pivot = arr[high] for j in range(low, high): # 當(dāng)前元素小于或等于 pivot if arr[j] <= pivot: i = i+1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] return (i+1) # arr[] --> 排序數(shù)組 # low --> 起始索引 # high --> 結(jié)束索引 # 快速排序函數(shù) def quickSort(arr, low, high): if low < high: pi = partition(arr, low, high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) return arr arr = [10, 7, 8, 9, 1, 5] n = len(arr) print("排序后的數(shù)組:") print(quickSort(arr, 0, n-1))
運(yùn)行結(jié)果:
排序后的數(shù)組:
[1, 5, 7, 8, 9, 10]
選擇排序(Selection sort):是一種簡單直觀的排序算法。它的工作原理如下。
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
A = [64, 25, 12, 22, 11] for i in range(len(A)): min_idx = i for j in range(i+1, len(A)): if A[min_idx] > A[j]: min_idx = j A[i], A[min_idx] = A[min_idx], A[i] print("排序后的數(shù)組:") print(A)
運(yùn)行結(jié)果:
排序后的數(shù)組:
[11, 12, 22, 25, 64]
冒泡排序(Bubble Sort):也是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢"浮"到數(shù)列的頂端。
def bubbleSort(arr): n = len(arr) # 遍歷所有數(shù)組元素 for i in range(n): # Last i elements are already in place for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr arr = [64, 34, 25, 12, 22, 11, 90] print("排序后的數(shù)組:") print(bubbleSort(arr))
運(yùn)行結(jié)果:
排序后的數(shù)組:
[11, 12, 22, 25, 34, 64, 90]
歸并排序(Merge sort,或mergesort):,是創(chuàng)建在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應(yīng)用。
分治法:
分割:遞歸地把當(dāng)前序列平均分割成兩半。
集成:在保持元素順序的同時將上一步得到的子序列集成到一起(歸并)。
def merge(arr, l, m, r): n1 = m - l + 1 n2 = r - m # 創(chuàng)建臨時數(shù)組 L = [0] * (n1) R = [0] * (n2) # 拷貝數(shù)據(jù)到臨時數(shù)組 arrays L[] 和 R[] for i in range(0, n1): L[i] = arr[l + i] for j in range(0, n2): R[j] = arr[m + 1 + j] # 歸并臨時數(shù)組到 arr[l..r] i = 0 # 初始化第一個子數(shù)組的索引 j = 0 # 初始化第二個子數(shù)組的索引 k = l # 初始?xì)w并子數(shù)組的索引 while i < n1 and j < n2: if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # 拷貝 L[] 的保留元素 while i < n1: arr[k] = L[i] i += 1 k += 1 # 拷貝 R[] 的保留元素 while j < n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr, l, r): if l < r: m = int((l+(r-1))/2) mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) return arr print ("給定的數(shù)組") arr = [12, 11, 13, 5, 6, 7, 13] print(arr) n = len(arr) mergeSort(arr, 0, n-1) print("排序后的數(shù)組") print(arr)
運(yùn)行結(jié)果:
給定的數(shù)組
[12, 11, 13, 5, 6, 7, 13]
排序后的數(shù)組
[5, 6, 7, 11, 12, 13, 13]
堆排序(Heapsort):是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu),并同時滿足堆積的性質(zhì):即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。
def heapify(arr, n, i): largest = i l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # 交換 def heapSort(arr): n = len(arr) # Build a maxheap. for i in range(n, -1, -1): heapify(arr, n, i) # 一個個交換元素 for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 交換 heapify(arr, i, 0) return arr arr = [12, 11, 13, 5, 6, 7, 13, 18] heapSort(arr) print("排序后的數(shù)組") print(heapSort(arr))
運(yùn)行結(jié)果:
排序后的數(shù)組
[5, 6, 7, 12, 11, 13, 13, 18]
計(jì)數(shù)排序:的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序,計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
def countSort(arr): output = [0 for i in range(256)] count = [0 for i in range(256)] ans = ["" for _ in arr] for i in arr: count[ord(i)] += 1 for i in range(256): count[i] += count[i-1] for i in range(len(arr)): output[count[ord(arr[i])]-1] = arr[i] count[ord(arr[i])] -= 1 for i in range(len(arr)): ans[i] = output[i] return ans arr = "wwwnowcodercom" ans = countSort(arr) print("字符數(shù)組排序 %s" %("".join(ans)))
運(yùn)行結(jié)果:
字符數(shù)組排序 ccdemnooorwwww
希爾排序:也稱遞減增量排序算法,是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序的基本思想是:先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,待整個序列中的記錄"基本有序"時,再對全體記錄進(jìn)行依次直接插入排序。
def shellSort(arr): n = len(arr) gap = int(n/2) while gap > 0: for i in range(gap, n): temp = arr[i] j = i while j >= gap and arr[j-gap] > temp: arr[j] = arr[j-gap] j -= gap arr[j] = temp gap = int(gap/2) return arr arr = [12, 34, 54, 2, 3, 2, 5] print("排序前:") print(arr) print("排序后:") print(shellSort(arr))
運(yùn)行結(jié)果:
排序前:
[12, 34, 54, 2, 3, 2, 5]
排序后:
[2, 2, 3, 5, 12, 34, 54]
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判颍菍中所有頂點(diǎn)排成一個線性序列,使得圖中任意一對頂點(diǎn)u和v,若邊(u,v)∈E(G),則u在線性序列中出現(xiàn)在v之前。通常,這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列,簡稱拓?fù)湫蛄?。簡單的說,由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓?fù)渑判颉?/p>
在圖論中,由一個有向無環(huán)圖的頂點(diǎn)組成的序列,當(dāng)且僅當(dāng)滿足下列條件時,稱為該圖的一個拓?fù)渑判颍ㄓ⒄Z:Topological sorting):
每個頂點(diǎn)出現(xiàn)且只出現(xiàn)一次;若A在序列中排在B的前面,則在圖中不存在從B到A的路徑。
from collections import defaultdict class Graph: def __init__(self, vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self, u, v): self.graph[u].append(v) def topologicalSortUtil(self, v, visited, stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i, visited, stack) stack.insert(0,v) def topologicalSort(self): visited = [False]*self.V stack = [] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i, visited, stack) print(stack) g= Graph(6) g.addEdge(5, 2) g.addEdge(5, 0) g.addEdge(4, 0) g.addEdge(4, 1) g.addEdge(2, 3) g.addEdge(3, 1) print("拓?fù)渑判蚪Y(jié)果:") g.topologicalSort()
運(yùn)行結(jié)果:
拓?fù)渑判蚪Y(jié)果:
[5, 4, 2, 3, 1, 0]
關(guān)于“python查找與排序算法實(shí)例代碼分析”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識,可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點(diǎn)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼
Copyright ? Yisu Cloud Ltd. All Rights Reserved. 2018 版權(quán)所有
廣州億速云計(jì)算有限公司粵ICP備17096448號-1 粵公網(wǎng)安備 44010402001142號增值電信業(yè)務(wù)經(jīng)營許可證編號:B1-20181529