Python十大經典排序算法

現(xiàn)在很多的事情都可以用算法來解決胸哥,在編程上橘忱,算法有著很重要的地位赴魁,將算法用函數(shù)封裝起來,使程序能更好的調用钝诚,不需要反復編寫尚粘。

Python十大經典算法:

一、插入排序

  1. 算法思想
    從第二個元素開始和前面的元素進行比較敲长,如果前面的元素比當前元素大郎嫁,則將前面元素 后移,當前元素依次往前祈噪,直到找到比它小或等于它的元素插入在其后面泽铛,然后選擇第三個元素,重復上述操作辑鲤,進行插入盔腔,依次選擇到最后一個元素,插入后即完成所有排序月褥。
  2. 代碼實現(xiàn)
def insertion_sort(arr):
    #插入排序
    # 第一層for表示循環(huán)插入的遍數(shù)
    for i in range(1, len(arr)):
        # 設置當前需要插入的元素
        current = arr[i]
        # 與當前元素比較的比較元素
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 當比較元素大于當前元素則把比較元素后移
            arr[pre_index + 1] = arr[pre_index]
            # 往前選擇下一個比較元素
            pre_index -= 1
        # 當比較元素小于當前元素弛随,則將當前元素插入在 其后面
        arr[pre_index + 1] = current
    return arr

二、選擇排序

  1. 算法思想
    設第一個元素為比較元素宁赤,依次和后面的元素比較舀透,比較完所有元素找到最小的元素,將它和第一個元素互換决左,重復上述操作愕够,我們找出第二小的元素和第二個位置的元素互換,以此類推找出剩余最小元素將它換到前面佛猛,即完成排序惑芭。
  2. 代碼實現(xiàn)
def selection_sort(arr):
    #選擇排序
    # 第一層for表示循環(huán)選擇的遍數(shù)
    for i in range(len(arr) - 1):
        # 將起始元素設為最小元素
        min_index = i
        # 第二層for表示最小元素和后面的元素逐個比較
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                # 如果當前元素比最小元素小,則把當前元素角標記為最小元素角標
                min_index = j
        # 查找一遍后將最小元素與起始元素互換
        arr[min_index], arr[i] = arr[i], arr[min_index]
    return arr

三继找、冒泡排序

  1. 算法思想
    從第一個和第二個開始比較遂跟,如果第一個比第二個大,則交換位置婴渡,然后比較第二個和第三個幻锁,逐漸往后,經過第一輪后最大的元素已經排在最后缩搅,所以重復上述操作的話第二大的則會排在倒數(shù)第二的位置越败。,那重復上述操作n-1次即可完成排序硼瓣,因為最后一次只有一個元素所以不需要比較究飞。
  2. 代碼實現(xiàn)
def bubble_sort(arr):
    #冒泡排序
    # 第一層for表示循環(huán)的遍數(shù)
    for i in range(len(arr) - 1):
        # 第二層for表示具體比較哪兩個元素
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                # 如果前面的大于后面的置谦,則交換這兩個元素的位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

四、快速排序

  1. 算法思想
    找出基線條件亿傅,這種條件必須盡可能簡單媒峡,不斷將問題分解(或者說縮小規(guī)模),直到符合基線條件葵擎。
  2. 代碼實現(xiàn)
def quick_sort(arr):
  if len(arr) < 2:
    # 基線條件:為空或只包含一個元素的數(shù)組是“有序”的
    return arr
  else:
    # 遞歸條件
    pivot = arr[0]
    # 由所有小于基準值的元素組成的子數(shù)組
    less = [i for i in arr[1:] if i <= pivot]
    # 由所有大于基準值的元素組成的子數(shù)組
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print(quick_sort([10, 5, 2, 3]))

五谅阿、歸并排序

  1. 算法思想
    歸并排序是分治法的典型應用。分治法(Divide-and-Conquer):將原問題劃分成 n 個規(guī)模較小而結構與原問題相似的子問題酬滤;遞歸地解決這些問題签餐,然后再合并其結果,就得到原問題的解盯串,分解后的數(shù)列很像一個二叉樹氯檐。

具體實現(xiàn)步驟:
1.使用遞歸將源數(shù)列使用二分法分成多個子列
2.申請空間將兩個子列排序合并然后返回
3.將所有子列一步一步合并最后完成排序
注:先分解再歸并

  1. 代碼實現(xiàn)
def merge_sort(arr):
    #歸并排序
    if len(arr) == 1:
        return arr
    # 使用二分法將數(shù)列分兩個
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    # 使用遞歸運算
    return marge(merge_sort(left), merge_sort(right))


def marge(left, right):
    #排序合并兩個數(shù)列
    result = []
    # 兩個數(shù)列都有值
    while len(left) > 0 and len(right) > 0:
        # 左右兩個數(shù)列第一個最小放前面
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 只有一個數(shù)列中還有值,直接添加
    result += left
    result += right
    return result

六体捏、希爾排序

  1. 算法思想
    希爾排序的整體思想是將固定間隔的幾個元素之間排序冠摄,然后再縮小這個間隔。這樣到最后數(shù)列就成為了基本有序數(shù)列几缭。

具體步驟:

1.計算一個增量(間隔)值

2.對元素進行增量元素進行比較河泳,比如增量值為7,那么就對0,7,14,21…個元素進行插入排序

3.然后對1,8,15…進行排序年栓,依次遞增進行排序

4.所有元素排序完后拆挥,縮小增量比如為3,然后又重復上述第2韵洋,3步

5.最后縮小增量至1時竿刁,數(shù)列已經基本有序黄锤,最后一遍普通插入即可

  1. 代碼實現(xiàn)
def shell_sort(arr):
    #希爾排序
    # 取整計算增量(間隔)值
    gap = len(arr) // 2
    while gap > 0:
        # 從增量值開始遍歷比較
        for i in range(gap, len(arr)):
            j = i
            current = arr[i]
            # 元素與他同列的前面的每個元素比較搪缨,如果比前面的小則互換
            while j - gap >= 0 and current < arr[j - gap]:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = current
        # 縮小增量(間隔)值
        gap //= 2
    return arr

七、基數(shù)排序

  1. 算法思想
    基數(shù)排序(radix sort)屬于“分配式排序”(distribution sort)鸵熟,又稱“桶子法”(bucket sort)或bin sort副编,顧名思義,它是透過鍵值的部份資訊流强,將要排序的元素分配至某些“桶”中痹届,藉以達到排序的作用,基數(shù)排序法是屬于穩(wěn)定性的排序打月,其時間復雜度為O (nlog(r)m)队腐,其中r為所采取的基數(shù),而m為堆數(shù)奏篙,在某些時候柴淘,基數(shù)排序法的效率高于其它的穩(wěn)定性排序法迫淹。
  2. 代碼實現(xiàn)
    2.1由桶排序改造,從最低位到最高位依次桶排序为严,最后輸出最后排好的列表敛熬。
def RadixSort(list,d):
    for k in range(d):#d輪排序
        # 每一輪生成10個列表
        s=[[] for i in range(10)]#因為每一位數(shù)字都是0~9,故建立10個桶
        for i in list:
            # 按第k位放入到桶中
            s[i//(10**k)%10].append(i)
        # 按當前桶的順序重排列表
        list=[j for i in s for j in i]
    return list

2.2簡單實現(xiàn)

from random import randint
def radix_sort():
  A = [randint(1, 99999999) for _ in xrange(9999)]
  for k in xrange(8):
    S = [ [] for _ in xrange(10)]
    for j in A:
      S[j / (10 ** k) % 10].append(j)
    A = [a for b in S for a in b]
  for i in A:
    print i

八第股、計數(shù)排序

  1. 算法思想
    對每一個輸入元素x应民,確定小于x的元素個數(shù)。利用這一信息夕吻,就可以直接把x 放在它在輸出數(shù)組上的位置上了诲锹,運行時間為O(n),但其需要的空間不一定涉馅,空間浪費大辕狰。
  2. 代碼實現(xiàn)
from numpy.random import randint
def Conuting_Sort(A):
    k = max(A)          # A的最大值,用于確定C的長度
    C = [0]*(k+1)       # 通過下表索引控漠,臨時存放A的數(shù)據(jù)
    B = (len(A))*[0]    # 存放A排序完成后的數(shù)組
    for i in range(0, len(A)):
        C[A[i]] += 1    # 記錄A有哪些數(shù)字蔓倍,值為A[i]的共有幾個
    for i in range(1, k+1):
        C[i] += C[i-1]  # A中小于i的數(shù)字個數(shù)為C[i]
    for i in range(len(A)-1, -1, -1):
        B[C[A[i]]-1] = A[i] # C[A[i]]的值即為A[i]的值在A中的次序
        C[A[i]] -= 1    # 每插入一個A[i],則C[A[i]]減一
    return B

九盐捷、堆排序

  1. 算法思想
    堆分為最大堆和最小堆偶翅,是完全二叉樹。堆排序就是把堆頂?shù)淖畲髷?shù)取出碉渡,將剩余的堆繼續(xù)調整為最大堆,具體過程在第二塊有介紹聚谁,以遞歸實現(xiàn) ,剩余部分調整為最大堆后,再次將堆頂?shù)淖畲髷?shù)取出滞诺,再將剩余部分調整為最大堆,這個過程持續(xù)到剩余數(shù)只有一個時結束形导。
  2. 代碼實現(xiàn)
import time,random
def sift_down(arr, node, end):
    root = node
    #print(root,2*root+1,end)
    while True:
        # 從root開始對最大堆調整
        child = 2 * root +1  #left child
        if child  > end:
            #print('break',)
            break
        print("v:",root,arr[root],child,arr[child])
        print(arr)
        # 找出兩個child中交大的一個
        if child + 1 <= end and arr[child] < arr[child + 1]: #如果左邊小于右邊
            child += 1 #設置右邊為大
        if arr[root] < arr[child]:
            # 最大堆小于較大的child, 交換順序
            tmp = arr[root]
            arr[root] = arr[child]
            arr[child]= tmp
            # 正在調整的節(jié)點設置為root
            #print("less1:", arr[root],arr[child],root,child)
            root = child #
            #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
            #print("less2:", arr[root],arr[child],root,child)
        else:
            # 無需調整的時候, 退出
            break
    #print(arr)
    print('-------------')
 
def heap_sort(arr):
    # 從最后一個有子節(jié)點的孩子還是調整最大堆
    first = len(arr) // 2 -1
    for i in range(first, -1, -1):
        sift_down(arr, i, len(arr) - 1)
    #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
    print('--------end---',arr)
    # 將最大的放到堆的最后一個, 堆-1, 繼續(xù)調整排序
    for end in range(len(arr) -1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end - 1)
        #print(arr)

十、桶排序

  1. 算法思想
    為了節(jié)省空間和時間习霹,我們需要指定要排序的數(shù)據(jù)中最小以及最大的數(shù)字的值朵耕,來方便桶排序算法的運算。
  2. 代碼實現(xiàn)
#桶排序
def bucket_sort(the_list):
    #設置全為0的數(shù)組
    all_list = [0 for i in range(100)]
    last_list = []
    for v in the_list:
        all_list[v] = 1 if all_list[v]==0 else all_list[v]+1
    for i,t_v in enumerate(all_list):
        if t_v != 0:
            for j in range(t_v):
                last_list.append(i)
    return last_list

總結:

在編程中淋叶,算法都是相通的阎曹,算法重在算法思想,相當于將一道數(shù)學上的應用題的每個條件煞檩,區(qū)間处嫌,可能出現(xiàn)的結果進行分解,分步驟的實現(xiàn)它斟湃。算法就是將具體問題的共性抽象出來熏迹,將步驟用編程語言來實現(xiàn)。通過這次對排序算法的整理凝赛,加深了對各算法的了解注暗,具體的代碼是無法記憶的厨剪,通過對算法思想的理解,根據(jù)偽代碼來實現(xiàn)具體算法的編程友存,才是真正了解算法祷膳。

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市屡立,隨后出現(xiàn)的幾起案子直晨,更是在濱河造成了極大的恐慌,老刑警劉巖膨俐,帶你破解...
    沈念sama閱讀 216,744評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件勇皇,死亡現(xiàn)場離奇詭異,居然都是意外死亡焚刺,警方通過查閱死者的電腦和手機敛摘,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,505評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來乳愉,“玉大人兄淫,你說我怎么就攤上這事÷Γ” “怎么了捕虽?”我有些...
    開封第一講書人閱讀 163,105評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長坡脐。 經常有香客問我泄私,道長,這世上最難降的妖魔是什么备闲? 我笑而不...
    開封第一講書人閱讀 58,242評論 1 292
  • 正文 為了忘掉前任晌端,我火速辦了婚禮,結果婚禮上恬砂,老公的妹妹穿的比我還像新娘咧纠。我一直安慰自己,他們只是感情好觉既,可當我...
    茶點故事閱讀 67,269評論 6 389
  • 文/花漫 我一把揭開白布惧盹。 她就那樣靜靜地躺著,像睡著了一般瞪讼。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上粹断,一...
    開封第一講書人閱讀 51,215評論 1 299
  • 那天符欠,我揣著相機與錄音,去河邊找鬼瓶埋。 笑死希柿,一個胖子當著我的面吹牛诊沪,可吹牛的內容都是我干的。 我是一名探鬼主播曾撤,決...
    沈念sama閱讀 40,096評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼端姚,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了挤悉?” 一聲冷哼從身側響起渐裸,我...
    開封第一講書人閱讀 38,939評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎装悲,沒想到半個月后昏鹃,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經...
    沈念sama閱讀 45,354評論 1 311
  • 正文 獨居荒郊野嶺守林人離奇死亡诀诊,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,573評論 2 333
  • 正文 我和宋清朗相戀三年洞渤,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片属瓣。...
    茶點故事閱讀 39,745評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡载迄,死狀恐怖,靈堂內的尸體忽然破棺而出抡蛙,到底是詐尸還是另有隱情宪巨,我是刑警寧澤,帶...
    沈念sama閱讀 35,448評論 5 344
  • 正文 年R本政府宣布溜畅,位于F島的核電站捏卓,受9級特大地震影響,放射性物質發(fā)生泄漏慈格。R本人自食惡果不足惜怠晴,卻給世界環(huán)境...
    茶點故事閱讀 41,048評論 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望浴捆。 院中可真熱鬧蒜田,春花似錦、人聲如沸选泻。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,683評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽页眯。三九已至梯捕,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間窝撵,已是汗流浹背傀顾。 一陣腳步聲響...
    開封第一講書人閱讀 32,838評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留碌奉,地道東北人短曾。 一個月前我還...
    沈念sama閱讀 47,776評論 2 369
  • 正文 我出身青樓寒砖,卻偏偏與公主長得像,于是被迫代替她去往敵國和親嫉拐。 傳聞我的和親對象是個殘疾皇子哩都,可洞房花燭夜當晚...
    茶點故事閱讀 44,652評論 2 354

推薦閱讀更多精彩內容