Python 中的排序演算法

什麼是排序？

排序是指根據資料項之間的線性關係，以特定順序（通常是升序或降序）排列資料的過程。

為什麼我們需要排序？

排序在處理結構化資料時至關重要，因為它可以實現高效的資料檢索、簡化資料分析並增強整體資料管理。

排序演算法

這篇文章涵蓋了以下排序演算法：冒泡排序、選擇排序、插入排序、合併排序和快速排序。

冒泡排序

冒泡排序重複遍歷數組，比較相鄰元素，如果順序錯誤則交換它們。這個過程一直持續到數組排序完畢，較大的元素“冒泡”到末尾。

演算法

第 1 步：開始
步驟 2：i = 0
步驟3：如果i 步驟 4：j = 0
步驟5：如果j＜； length(array) - i - 1，轉到步驟6；否則轉到步驟 3
步驟6：如果array[j]> array[j + 1]，請轉到步驟7；否則轉到步驟 8
步驟7：交換數組[j]和數組[j + 1]
步驟8：遞增j；轉到步驟 5
步驟9：增加i；轉到步驟 3
第10步：結束

程式碼

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

時間複雜度

最佳情況：O(n)
平均情況：O(n^2)
最壞情況：O(n^2)

選擇排序

選擇排序以尋找數組未排序部分中的最小值，並將其放置在該部分的開頭。

演算法

第 1 步：開始
步驟 2：i = 0
步驟3：如果i 步驟4：minimum_value = i; j = i + 1
步驟5：如果j＜1。 length(數組)，轉到步驟6；否則轉到步驟 9
步驟 6：如果 array[minimum_value] > array[j]，請轉到步驟7；否則請前往步驟 8
步驟 7：minimum_value = j
步驟8：遞增j；轉到步驟 5
步驟9：交換數組[minimum_value]和數組[i]
步驟10：增加i；轉到步驟 3
第11步：結束

程式碼

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

時間複雜度

最佳情況：O(n^2)
平均情況：O(n^2)
最壞情況：O(n^2)

插入排序

插入排序透過從未排序部分取出每個元素並將其插入到已排序部分的正確位置來建立排序數組，一次一個元素。

演算法

第 1 步：開始
步驟 2：i = 1
步驟3：如果i<； len(arr)，轉到步驟4；否則轉到步驟 12
第四步：key = arr[i]
步驟 5：j = i - 1
步驟6：如果j>=0且arr[j]>鍵，請轉到步驟7；否則轉到步驟 10
步驟7：arr[j + 1] = arr[j]
步驟 8：將 j 減 1
第9步：轉到第6步
第10步：arr[j + 1] = key
步驟11：i加1；轉到步驟 3
第12步：結束

程式碼

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

時間複雜度

最佳情況：O(n)
平均情況：O(n^2)
最壞情況：O(n^2)

歸併排序

合併排序是一種分而治之的演算法，它遞歸地將陣列分成更小的子數組，對它們進行排序，然後將它們合併在一起。

演算法

合併排序演算法

第 1 步：開始
步驟2：如果length(array) 第三步：mid_point = length(array) // 2
步驟 4：left_half = array[:mid_point]
步驟5：right_half = array[mid_point:]
步驟6：sorted_left = merge_sort(left_half)
步驟7：sorted_right = merge_sort(right_half)
步驟8：返回merge(sorted_left,sorted_right)
第9步：結束

合併函數

第 1 步：開始
步驟2：sorted_merge = []
步驟 3：l = 0，r = 0
步驟4：如果l 步驟5：若left[l] 步驟6：將left[l]加入sorted_merge中；將 l 加 1
步驟7：將right[r]加入sorted_merge；將 r 加 1
第8步：轉到第4步
步驟9：如果l 步驟10：將left[l]加入sorted_merge中；將 l 加 1
第11步：轉到第9步
步驟12：如果r＜1 len(右)，轉到步驟13；否則轉到步驟 15
步驟13：將right[r]加入sorted_merge中；將 r 加 1
第14步：轉到第12步
第15步：返回sorted_merge
第16步：結束

程式碼

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)

時間複雜度

最佳情況：O(n log n)
平均情況：O(n log n)
最壞情況：O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left <= right:
        if arr[left] > pivot and arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
        if arr[left] <= pivot:
            left += 1
        if arr[right] >= pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

以上是Python 中的排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！