用 Python 实现十大经典排序算法("Python 编程实现十大经典排序算法详解")

原创

ithorizon 4周前 (10-21) 阅读数 21 #后端开发

Python 编程实现十大经典排序算法详解

一、冒泡排序（Bubble Sort）

冒泡排序是一种单纯的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序谬误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。


def bubble_sort(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]
    return arr

二、选择排序（Selection Sort）

选择排序是一种单纯直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。


def selection_sort(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]
    return arr

三、插入排序（Insertion Sort）

插入排序是一种单纯直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。


def insertion_sort(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
    return arr

四、敏捷排序（Quick Sort）

敏捷排序是一种高效的排序算法，它采用分而治之的策略将一个序列分为两个子序列。步骤为：1. 从数列中挑出一个元素，称为 "基准"（pivot）。2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。3. 递归地（分别）在基准前后的子序列中重复步骤1和2。


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

五、归并排序（Merge Sort）

归并排序是一种分治算法。它将一个数组分成两半，对它们递归地应用归并排序，然后将排序好的两半合并成一个最终的排序数组。归并排序是稳定的排序方法。


def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
def merge(left, right):
    result = []
    i = j = 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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

六、堆排序（Heap Sort）

堆排序是一种基于比较的排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。


def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

七、希尔排序（Shell Sort）

希尔排序是一种基于插入排序的算法，它通过比较较远距离的元素来工作，其核心理念是使数组中任意间隔为h的元素都是有序的。h的选择是算法的关键。


def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

八、计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于小范围整数的排序，其核心思想是使用一个额外的数组来计算每个元素的出现次数，然后选用出现次数来排序。


def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for a in arr:
        count[a] += 1
    i = 0
    for (a, c) in enumerate(count):
        for _ in range(c):
            arr[i] = a
            i += 1
    return arr

九、基数排序（Radix Sort）

基数排序是一种非比较的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较排序。基数排序的时间繁复度可以是O(n)，它是稳定的排序算法。


def counting_sort_for_radix(arr, position):
    output = [-1] * len(arr)
    count = [0] * 10
    for num in arr:
        index = num // position % 10
        count[index] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    i = len(arr) - 1
    while i >= 0:
        index = arr[i] // position % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
    for i in range(len(arr)):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    position = 1
    while max_val // position > 0:
        counting_sort_for_radix(arr, position)
        position *= 10
    return arr

十、桶排序（Bucket Sort）

桶排序是计数排序的升级版，它将元素分到有限数量的桶里，每个桶再个别排序（有大概再使用别的排序算法或是以递归对策继续使用桶排序进行排序）。


def bucket_sort(arr):
    if len(arr) == 0:
        return arr
    min_val, max_val = min(arr), max(arr)
    bucket_range = (max_val - min_val) / len(arr)
    buckets = [[] for _ in range(len(arr) + 1)]
    for num in arr:
        buckets[int((num - min_val) / bucket_range)].append(num)
    sorted_arr = []
    for bucket in buckets:
        insertion_sort(bucket)
        sorted_arr.extend(bucket)
    return sorted_arr