欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python查找與排序算法詳解(示圖+代碼)

 更新時間:2022年07月26日 16:43:27   作者:knighthood2001  
這篇文章主要介紹了python查找與排序算法詳解(示圖+代碼),文章通過二分查找展開主題詳細(xì)內(nèi)容,需要的朋友可以參考一下

查找

二分查找

二分搜索是一種在有序數(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)值小的元素擺放在基準(zhǔn)前面,所有比基準(zhǔn)值大的元素擺在基準(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)排序完成。這個算法的名字由來是因為越小的元素會經(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è)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu),并同時滿足堆積的性質(zhì):即子結(jié)點的鍵值或索引總是小于(或者大于)它的父節(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))

運(yùn)行結(jié)果:   

排序后的數(shù)組
[5, 6, 7, 12, 11, 13, 13, 18]

計數(shù)排序

計數(shù)排序:的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序,計數(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]

拓?fù)渑判?/h3>

對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判颍菍中所有頂點排成一個線性序列,使得圖中任意一對頂點u和v,若邊(u,v)∈E(G),則u在線性序列中出現(xiàn)在v之前。通常,這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列,簡稱拓?fù)湫蛄?。簡單的說,由某個集合上的一個偏序得到該集合上的一個全序,這個操作稱之為拓?fù)渑判颉?/p>

在圖論中,由一個有向無環(huán)圖的頂點組成的序列,當(dāng)且僅當(dāng)滿足下列條件時,稱為該圖的一個拓?fù)渑判颍ㄓ⒄Z: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("拓?fù)渑判蚪Y(jié)果:")
g.topologicalSort()

運(yùn)行結(jié)果:   

拓?fù)渑判蚪Y(jié)果:
[5, 4, 2, 3, 1, 0]

總結(jié)

到此這篇關(guān)于python查找與排序算法詳解(示圖+代碼)的文章就介紹到這了,更多相關(guān)python算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • python中input()的用法及擴(kuò)展

    python中input()的用法及擴(kuò)展

    這篇文章主要介紹了python中input()的用法及擴(kuò)展,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-05-05
  • Python基于pip實現(xiàn)離線打包過程詳解

    Python基于pip實現(xiàn)離線打包過程詳解

    這篇文章主要介紹了Python基于pip實現(xiàn)離線打包過程詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-05-05
  • Python基礎(chǔ)之numpy庫的使用

    Python基礎(chǔ)之numpy庫的使用

    這篇文章主要介紹了Python基礎(chǔ)之numpy庫的使用,文中有非常詳細(xì)的代碼示例,對正在學(xué)習(xí)python基礎(chǔ)的小伙伴們有非常好的幫助,需要的朋友可以參考下
    2021-04-04
  • PyQt信號和槽機(jī)制的具體使用

    PyQt信號和槽機(jī)制的具體使用

    信號和槽機(jī)制是一種通信機(jī)制,在PyQt中,信號是一種特殊的函數(shù),它可以傳遞任何類型的數(shù)據(jù),而槽則是一種接收信號的函數(shù),本文就介紹了PyQt信號和槽機(jī)制的具體使用,感興趣的可以了解一下
    2023-08-08
  • 詳解python字節(jié)碼

    詳解python字節(jié)碼

    本篇文章給大家總結(jié)了關(guān)于python字節(jié)碼的相關(guān)知識點以及知識點分析,對此有需要的朋友參考學(xué)習(xí)下。
    2018-02-02
  • Python隨機(jī)生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點

    Python隨機(jī)生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點

    這篇文章主要為大家詳細(xì)介紹了Python隨機(jī)生成均勻分布在三角形內(nèi)或者任意多邊形內(nèi)的點,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-12-12
  • python一秒搭建FTP服務(wù)器

    python一秒搭建FTP服務(wù)器

    今天給大家分享一篇教程關(guān)于python一秒搭建FTP服務(wù)器的教程,在搭建過程中需要用到pyftpdlib模塊,對python FTP服務(wù)器搭建過程感興趣的朋友跟隨小編一起看看吧
    2021-05-05
  • 在python帶權(quán)重的列表中隨機(jī)取值的方法

    在python帶權(quán)重的列表中隨機(jī)取值的方法

    今天小編就為大家分享一篇在python帶權(quán)重的列表中隨機(jī)取值的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-01-01
  • Python切片用法實例教程

    Python切片用法實例教程

    這篇文章主要介紹了Python切片用法,可以有效的提高Python程序設(shè)計的效率,更加靈活的進(jìn)行Python循環(huán)操作,需要的朋友可以參考下
    2014-09-09
  • 利用Python計算KS的實例詳解

    利用Python計算KS的實例詳解

    這篇文章主要介紹了利用Python計算KS的實例詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-03-03

最新評論