python查找與排序演算法實例程式碼分析-Python教學-PHP中文網

查找

二分查找

#二分搜尋是一種在有序數組中尋找某一特定元素的搜尋演算法。搜尋過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜尋過程結束；如果某一特定元素大於或小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。

python查找與排序演算法實例程式碼分析

# 返回 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
 
# 测试数组
arr = [ 2, 3, 4, 10, 40]
x = int(input(&#39;请输入元素：&#39;))
# 函数调用
result = binarySearch(arr, 0, len(arr)-1, x)
 
if result != -1:
    print("元素在数组中的索引为 %d" % result)
else:
    print("元素不在数组中")

登入後複製

運行結果：

#請輸入元素：4
元素在陣列中的索引為2

請輸入元素：5
元素不在數組中

#線性查找

線性查找：指以一定的順序檢查數組中每一個元素，直到找到所要尋找的特定值為止。

def search(arr, n, x):
    for i in range (0, n):
        if (arr[i] == x):
            return i
    return -1
 
# 在数组 arr 中查找字符 D
arr = [ &#39;A&#39;, &#39;B&#39;, &#39;C&#39;, &#39;D&#39;, &#39;E&#39; ]
x = input("请输入要查找的元素：")
n = len(arr)
result = search(arr, n, x)
if(result == -1):
    print("元素不在数组中")
else:
    print("元素在数组中的索引为", result)

登入後複製

運作結果：

請輸入要尋找的元素：A
元素在陣列中的索引為0

#請輸入要尋找的元素：a
元素不在陣列中

排序

插入排序

插入排序（Insertion Sort）：是一種簡單直覺的排序演算法。它的工作原理是透過建立有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

python查找與排序演算法實例程式碼分析

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("排序后的数组:")
print(arr)

登入後複製

運行結果：

排序後的陣列:
[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個子序列，然後遞歸地排序兩個子序列。

步驟為：

挑選基準值：從數列中挑出一個元素，稱為"基準" （pivot）;
分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成;
遞歸排序子序列：遞歸地將小於基準值元素的子序列和大於基準值元素的子序列排序。

遞歸到最底部的判斷條件是數列的大小是零或一，此時該數列顯然已經有序。

選取基準值有數種具體方法，此選取方法對排序的時間效能有決定性影響。

python查找與排序演算法實例程式碼分析

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[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引
 
# 快速排序函数
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("排序后的数组:")
print(quickSort(arr, 0, n-1))

登入後複製

運作結果：

排序後的陣列:
[1, 5, 7, 8 , 9, 10]

選擇排序

選擇排序（Selection sort）：是一種簡單直覺的排序演算法。它的工作原理如下。

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末端。以此類推，直到所有元素都排序完畢。

python查找與排序演算法實例程式碼分析

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("排序后的数组：")
print(A)

登入後複製

運行結果：

排序後的陣列：
[11, 12, 22, 25 , 64]

冒泡排序

冒泡排序（Bubble Sort）：也是一種簡單直覺的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

python查找與排序演算法實例程式碼分析

def bubbleSort(arr):
    n = len(arr)
    # 遍历所有数组元素
    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("排序后的数组:")
print(bubbleSort(arr))

登入後複製

運行結果：

排序後的陣列:
[11, 12, 22, 25 , 34, 64, 90]

归并排序

归并排序（Merge sort，或mergesort）：，是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治法:

分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

python查找與排序演算法實例程式碼分析

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
 
    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)
 
    # 拷贝数据到临时数组 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]
 
    # 归并临时数组到 arr[l..r]
    i = 0     # 初始化第一个子数组的索引
    j = 0     # 初始化第二个子数组的索引
    k = l     # 初始归并子数组的索引
 
    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 ("给定的数组")
arr = [12, 11, 13, 5, 6, 7, 13]
print(arr)
n = len(arr)
mergeSort(arr, 0, n-1)
print("排序后的数组")
print(arr)

登入後複製

运行结果：

给定的数组
[12, 11, 13, 5, 6, 7, 13]
排序后的数组
[5, 6, 7, 11, 12, 13, 13]

堆排序

堆排序（Heapsort）：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

python查找與排序演算法實例程式碼分析

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("排序后的数组")
print(heapSort(arr))

登入後複製

运行结果：

排序后的数组
[5, 6, 7, 12, 11, 13, 13, 18]

计数排序

计数排序：的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

python查找與排序演算法實例程式碼分析

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("字符数组排序 %s" %("".join(ans)))

登入後複製

运行结果：

字符数组排序 ccdemnooorwwww

希尔排序

希尔排序：也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

python查找與排序演算法實例程式碼分析

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]

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。拓扑排序是一种将集合上的偏序转换为全序的操作。

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）：

每个顶点出现且只出现一次；若A在序列中排在B的前面，则在图中不存在从B到A的路径。

python查找與排序演算法實例程式碼分析

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()

登入後複製

运行结果：