python查找與排序算法詳解(示圖+代碼)
查找
二分查找
二分搜索是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大于或者小于中間元素，則在數(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ù)調用
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("元素在數(shù)組中的索引為 %d" % result)
else:
print("元素不在數(shù)組中")運行結果：
請輸入元素：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)運行結果：
請輸入要查找的元素：A
元素在數(shù)組中的索引為 0
請輸入要查找的元素：a
元素不在數(shù)組中
排序
插入排序
插入排序（Insertion Sort）：是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數(shù)據，在已排序序列中從后向前掃描，找到相應位置并插入。
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)運行結果：
排序后的數(shù)組:
[5, 6, 7, 9, 9, 11, 12, 13, 17]
當然也可以這樣寫，更簡潔
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個子序列，然后遞歸地排序兩個子序列。
步驟為：
- 挑選基準值：從數(shù)列中挑出一個元素，稱為"基準"（pivot）;
- 分割：重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數(shù)可以到任何一邊）。在這個分割結束之后，對基準值的排序就已經完成;
- 遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。
遞歸到最底部的判斷條件是數(shù)列的大小是零或一，此時該數(shù)列顯然已經有序。
選取基準值有數(shù)種具體方法，此選取方法對排序的時間性能有決定性影響。
def partition(arr, low, high):
i = (low-1) # 最小元素索引
pivot = arr[high]
for j in range(low, high):
# 當前元素小于或等于 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 --> 結束索引
# 快速排序函數(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))運行結果：
排序后的數(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)運行結果：
排序后的數(shù)組：
[11, 12, 22, 25, 64]
冒泡排序
冒泡排序（Bubble Sort）：也是一種簡單直觀的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到沒有再需要交換，也就是說該數(shù)列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數(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))運行結果：
排序后的數(shù)組:
[11, 12, 22, 25, 34, 64, 90]
歸并排序
歸并排序（Merge sort，或mergesort）：，是創(chuàng)建在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
分治法:
- 分割：遞歸地把當前序列平均分割成兩半。
- 集成：在保持元素順序的同時將上一步得到的子序列集成到一起（歸并）。
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# 創(chuàng)建臨時數(shù)組
L = [0] * (n1)
R = [0] * (n2)
# 拷貝數(shù)據到臨時數(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 # 初始歸并子數(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)運行結果：
給定的數(shù)組
[12, 11, 13, 5, 6, 7, 13]
排序后的數(shù)組
[5, 6, 7, 11, 12, 13, 13]
堆排序
堆排序（Heapsort）：是指利用堆這種數(shù)據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。
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))運行結果：
排序后的數(shù)組
[5, 6, 7, 12, 11, 13, 13, 18]
計數(shù)排序
計數(shù)排序：的核心在于將輸入的數(shù)據值轉化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復雜度的排序，計數(shù)排序要求輸入的數(shù)據必須是有確定范圍的整數(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)))運行結果：
字符數(shù)組排序 ccdemnooorwwww
希爾排序
希爾排序：也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wě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))運行結果：
排序前:
[12, 34, 54, 2, 3, 2, 5]
排序后:
[2, 2, 3, 5, 12, 34, 54]
拓撲排序
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
在圖論中，由一個有向無環(huán)圖的頂點組成的序列，當且僅當滿足下列條件時，稱為該圖的一個拓撲排序（英語：Topological sorting）：
每個頂點出現(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("拓撲排序結果：")
g.topologicalSort()運行結果：
拓撲排序結果：
[5, 4, 2, 3, 1, 0]
總結
到此這篇關于python查找與排序算法詳解(示圖+代碼)的文章就介紹到這了,更多相關python算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了python中input()的用法及擴展，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
這篇文章主要介紹了Python基于pip實現(xiàn)離線打包過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
這篇文章主要介紹了Python基礎之numpy庫的使用,文中有非常詳細的代碼示例,對正在學習python基礎的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04
信號和槽機制是一種通信機制,在PyQt中,信號是一種特殊的函數(shù),它可以傳遞任何類型的數(shù)據,而槽則是一種接收信號的函數(shù),本文就介紹了PyQt信號和槽機制的具體使用,感興趣的可以了解一下2023-08-08
本篇文章給大家總結了關于python字節(jié)碼的相關知識點以及知識點分析，對此有需要的朋友參考學習下。2018-02-02
這篇文章主要為大家詳細介紹了Python隨機生成均勻分布在三角形內或者任意多邊形內的點，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-12-12
今天給大家分享一篇教程關于python一秒搭建FTP服務器的教程，在搭建過程中需要用到pyftpdlib模塊，對python FTP服務器搭建過程感興趣的朋友跟隨小編一起看看吧2021-05-05
今天小編就為大家分享一篇在python帶權重的列表中隨機取值的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了Python切片用法,可以有效的提高Python程序設計的效率,更加靈活的進行Python循環(huán)操作,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了利用Python計算KS的實例詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-03-03