python中的常見算法

這篇文章主要介紹了python中的常見算法，具有一定借鑒價值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。

定義：算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。

python中的常見算法

冒泡排序

效率：O(n2)

原理：

比較相鄰的元素，如果第一個比第二個大，就交換他們兩個；

對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。做完以后，最后的元素會是最大的數，這里可以理解為走了一趟；

針對所有的元素重復以上的步驟，除了最后一個；

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，最后數列就是從大到小一次排列；

def bubble_sort(data):
    """
    冒泡排序
    :param data: 
    :return: 
    """
    for i in range(len(data)-1):  # 趟數
        for j in range(len(data)-i-1):  # 遍歷數據，依次交換
            if data[j]>data[j+1]:  # 當較大數在前面
                data[j],data[j+1]=data[j+1],data[j] #交換兩個數的位置

if __name__=='__main__':
    import random
    data_list=list(range(30))
    random.shuffle(data_list)
    print("pre:",data_list)
    bubble_sort(data_list)
    print("after:",data_list)
#結果：
#pre: [22, 11, 19, 16, 12, 18, 20, 28, 27, 4, 21, 10, 9, 7, 1, 6, 5, 29, 8, 0, 17, 26, 13, 14, 15, 24, 25, 23, 3, 2]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

選擇排序

效率：O(n2)

原理：

每一次從待排序的列表中選出一個元素，并將其與其他數依次比較，若列表中的某個數比選中的數小，則交換位置，把所有數比較完畢，則會選出最小的數，將其放在最左邊（這一過程稱為一趟）；

重復以上步驟，直到全部待排序的數據元素排完；

demo：

def select_sort(data):
    """
    選擇排序
    :param data: 待排序的數據列表
    :return: 
    """
    for i in range(len(data)-1):  #趟數
        min_index=i  # 記錄i趟開始最小的數的索引，我們從最左邊開始
        for j in range(i+1,len(data)): # 每一次趟需要循環的次數
            if data[j] < data[min_index]:  # 當數列中的某一個數比開始的數要小時候，更新最小值索引位置
                min_index=j
        data[i],data[min_index]=data[min_index],data[i]  # 一趟走完，交換最小值的位置，第一趟最小
if __name__=='__main__':
    import random
    data_list=list(range(30))
    random.shuffle(data_list)  # 打亂列表數據
    print("pre:",data_list)
    select_sort(data_list)
    print("after:",data_list)
#結果：
#pre: [20, 11, 22, 0, 18, 21, 14, 19, 7, 23, 27, 29, 24, 4, 17, 15, 5, 10, 26, 13, 25, 1, 8, 16, 3, 9, 2, 28, 12, 6]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

插入排序

效率：O(n2)

原理：

以從小到大排序為例，元素0為第一個元素，插入排序是從元素1開始，盡可能插到前面。

插入時分插入位置和試探位置，元素i的初始插入位置為i，試探位置為i-1，在插入元素i時，依次與i-1,i-2······元素比較，如果被試探位置的元素比插入元素大，那么被試探元素后移一位，元素i插入位置前移1位，直到被試探元素小于插入元素或者插入元素位于第一位。

重復上述步驟，最后完成排序

demo：

def insert_sort(data):
    """
    插入排序
    :param data: 待排序的數據列表
    :return: 
    """
    for i in range(1, len(data)): # 無序區域數據
        tmp = data[i] # 第i次插入的基準數
        for j in range(i, -1, -1):
            if tmp < data[j - 1]:  # j為當前位置，試探j-1位置
                data[j] = data[j - 1]  #  移動當前位置
            else:  # 位置確定為j
                break
        data[j] = tmp  # 將當前位置數還原

if __name__=='__main__':
    import random
    data_list=list(range(30))
    random.shuffle(data_list)  # 打亂列表數據
    print("pre:",data_list)
    insert_sort(data_list)
    print("after:",data_list)
#結果：
#pre: [7, 17, 10, 16, 23, 24, 13, 11, 2, 5, 15, 29, 27, 18, 4, 19, 1, 9, 3, 21, 0, 14, 12, 25, 22, 28, 20, 6, 26, 8]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

堆排序

堆定義：本質是一個完全二叉樹，如果根節點的值是所有節點的最小值稱為小根堆，如果根節點的值是所有節點的最大值，稱為大根堆。

效率：O(nlogn)

原理：

將待排序數據列表建立成堆結構(建立堆)；

通過上浮(shift_up)或下沉(shift_down)等操作得到堆頂元素為最大元素（已大根堆為例）；

去掉堆頂元素，將最后的一個元素放到堆頂，重新調整堆，再次使得堆頂元素為最大元素（相比第一次為第二大元素）；

重復3操作，直到堆為空，最后完成排序；

歸并排序

效率：O(nlogn)

空間復雜度：O(n)

原理：

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

重復步驟3直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復制到合并序列尾。

感謝你能夠認真閱讀完這篇文章，希望小編分享python中的常見算法內容對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，遇到問題就找億速云，詳細的解決方法等著你來學習!