歡迎您光臨本站 註冊首頁

python語言中有算法嗎

←手機掃碼閱讀     e36605 @ 2020-06-17 , reply:0

瞭解算法之前,我們先看一下什麼是算法

定義:算法(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直到某一指針達到序列尾;

將另一序列剩下的所有元素直接複製到合併序列尾。


[e36605 ] python語言中有算法嗎已經有135次圍觀

http://coctec.com/docs/python/shhow-post-238852.html