Python 中的排序算法-Python教程-PHP中文网

Sorting Algorithms in 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)

登录后复制