python中幾種常用的排序算法

這篇文章主要介紹“python中幾種常用的排序算法”，在日常操作中，相信很多人在python中幾種常用的排序算法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”python中幾種常用的排序算法”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

排序算法的運用非常廣泛。各種語言都有自己內置的排序函數，在面試過程中也經常會有排序算法的考題。總結幾種排序算法的實現。

這個問題的顯示表示是：請詳細描述如何將一組數字按從小到大的順序排列。

我首先想到的是：

1. 找出數組中最小的一個；

2. 把這個數放到另一數組的最后面；

3. 把這個數從原來的數組中剔除；

4. 重復

重復的過程通常涉及到遍歷和遞歸，上面這個解法叫「選擇排序」，用 Python 實現如下：

def select_sort(arr):
    new_arr = []
     # 重復
    for i in range(len(arr)):
        small_index = find_smallest(arr)
         # 把這個數從原來的數組中剔除；
        smallest = arr.pop(small_index)
         # 把這個數放到另一數組的最后面；
        new_arr.append(smallest)
    return new_arr
def find_smallest(arr):
     """找出數組中最小的一個；"""
    smallest = arr[0]
    index = 0
    for e in range(1,len(arr)):
        if arr[e] < smallest:
            smallest = arr[e]
            index = e
    return index

可以看出來，代碼實現基本上就是用編程語言寫出解題思路。所以很多編程進階書都提到一個解決問題的辦法就是離開鍵盤，去上個廁所，在紙上畫一畫。只要是解題思路很詳細，基本上是可以用來當偽代碼使用的，可以全部放入代碼的注釋當中。

冒泡排序（Bubble Sort）

1. 比較前一個數和后一個數，如果前比后大，對換他們的位置；

2. 循環執行

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                tmp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = tmp
    return arr

快速排序

上面兩種算法要操作的步驟很多，當數組太多時就會造成性能過低，我們可以想辦法減少要操作的步驟，從而降低算法的復雜度，提高執行效率。減少步驟的很多算法都是將數據分成幾部分來處理，也就是通常說的「分治」，從而不斷減少沒部分需要處理的步驟，選擇排序就是這樣一種算法：
1.選出第一個元素
2.遍歷每個元素，也就是從第二個開始拿，如果比第一個元素小，放到一個新數組里；如果比它大，放到另一個數組；
3.對兩個新數組執行同樣的操作；
那什么時候不需要執行這樣的操作了呢？當數組的元素個數小于2的時候，不需要比較了，分治策略就結束。

「分治」是一種非常常見的解題思路。因為它能不斷的將問題變成更簡單的問題，最后變成一個顯而易見的事。也就是說它有兩個條件：

• 基準條件。也就是沒有辦法再分了，足夠簡單了。

• 分治條件或者叫遞歸條件。能夠進一步縮小需要解決的問題的規模。

分治法在算法中非常普遍，不是因為他能降低算法的復雜度，而是他能一步步將復雜的問題變得越來越簡單，規模越來越小，最后變成一個超級簡單的問題，如果能進一步抽象這種過程，就能考執行同樣的抽象步驟解出來來。分治法經常和遞歸用在一起，這就衍生了一種變成方式——函數式編程，如果能多接觸一些遞歸的案例，對于函數式變成和抽象是非常有幫助的。軟件設計就是講一個非常復雜的問題抽象的過程，所以掌握函數式編程和遞歸概念對于抽象能力和軟件設計應該是很有幫助的。

下面實現快速排序：

def quick(arr):
    if len(arr) < 2:
        return arr
    else:
        base = arr[0]
        less = [i for i in arr[1:] if i < base]
        greater = [i for i in arr[1:] if i >= base]
        return quick(less) + [base] + quick(greater)

歸并排序

歸并排序和選擇排序一樣是一種分治遞歸策略：

1. 從中間分成兩組

2. 將兩個已經排序好的列表進行合并，合并成的列表就是排序好的
   那怎么對上述兩個列表排序呢？對兩個列表再執行分組策略
   什么時候不能繼續了呢？當元素個數小于 2 的時候

具體實現：

def merge_sort(arr):
    # divide to two
    if len(arr) < 2:
        return arr
    mid = int(len(arr)/2)
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
def merge(left, right):
    result = []
    j = 0
    i = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # add the larger part both left and right
    result += left[i:]
    result += right[j:]
    return result

到此，關于“python中幾種常用的排序算法”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！