Python 3中的排序

引言

在編程中，排序是最常見也是最重要的問題之一。排序是將一組無序數據按照某個規則重新排列的過程。

Python 3中提供了多種排序演算法，以便不同的數據結構選擇最適合的排序演算法。在本文中，我們將介紹幾種最常用的排序演算法，並提供示例代碼。

演算法說明

冒泡排序

冒泡排序是一種簡單的排序演算法。它不斷地交換相鄰元素，將較大的元素逐漸「浮」到數列的頂部。

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

冒泡排序的時間複雜度是O(n^2)

快速排序

快速排序是一種分治法的排序演算法。它使用遞歸的方式將數列劃分成左右兩個較小的子序列，在子序列中分別進行排序，最後將兩個有序子序列合併成一個有序數列。

def partition(arr, low, high):
    i = (low-1)
    pivot = arr[high]

    for j in range(low, high):

        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)


def quickSort(arr, low, high):
    if len(arr) == 1:
        return arr
    if low < high:

        pi = partition(arr, low, high)

        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

快速排序的平均時間複雜度為O(nlogn)。

選擇排序

選擇排序是一種簡單的排序演算法。該演算法的主要思想是從未排序的序列中選擇最小的數放到已排序序列的末尾。

def selectionSort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
                
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

選擇排序的時間複雜度為O(n^2)。

插入排序

插入排序是一種簡單穩定的排序演算法。它的主要思想是將一個記錄插入到已經排好序的有序序列中，從而得到一個新的、記錄數增加1的有序序列。

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

插入排序的時間複雜度為O(n^2)。

歸併排序

歸併排序是一種分治法的排序演算法。它將數列分成兩個有序序列，遞歸地將它們排序，並將結果歸併到一個新的、更大的有序序列中。

def mergeSort(arr):
    if len(arr) >1:
        mid = len(arr)//2 
        L = arr[:mid] 
        R = arr[mid:] 

        mergeSort(L) 
        mergeSort(R) 

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

歸併排序的時間複雜度為O(nlogn)。

結論

以上是Python 3中五種常用的排序演算法，分別是冒泡排序、快速排序、選擇排序、插入排序和歸併排序。它們各自有其優點和適用範圍，根據具體情況選擇最合適的演算法可以提高程序的效率，減少資源的消耗。