Python 数据结构之十大经典排序算法一文通关

一、前置知识

在学习本文之前，需要具备以下基础知识：

• Python 基础语法
• 算法与数据结构基础

二、十大经典排序算法

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 归并排序
6. 快速排序
7. 堆排序
8. 计数排序
9. 桶排序
10. 基数排序

本文将一一讲解这十种排序算法。

三、冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历过要排序的数列，一次比较两个元素，如果顺序有误就交换位置。它的实现过程如下：

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

例如，对于输入列表 [3, 1, 2, 5, 4]，冒泡排序算法的输出结果为 [1, 2, 3, 4, 5]。

四、 选择排序

选择排序是一种简单直观的排序算法。它的实现过程如下：

def selection_sort(data):
    for i in range(len(data)):
        min_index = i
        for j in range(i+1, len(data)):
            if data[j] < data[min_index]:
                min_index = j
        data[i], data[min_index] = data[min_index], data[i]
    return data

例如，对于输入列表 [3, 1, 2, 5, 4]，选择排序算法的输出结果为 [1, 2, 3, 4, 5]。

五、插入排序

插入排序是一种简单直观的排序算法，它的实现过程如下：

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j+1] = data[j]
            j -= 1
        data[j+1] = key
    return data

例如，对于输入列表 [3, 1, 2, 5, 4]，插入排序算法的输出结果为 [1, 2, 3, 4, 5]。

六、希尔排序

希尔排序是一种改进的插入排序算法，它的实现过程如下：

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

例如，对于输入列表 [3, 1, 2, 5, 4]，希尔排序算法的输出结果为 [1, 2, 3, 4, 5]。

七、归并排序

归并排序是一种分治思想的算法，它的实现过程如下：

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

例如，对于输入列表 [3, 1, 2, 5, 4]，归并排序算法的输出结果为 [1, 2, 3, 4, 5]。

八、快速排序

快速排序是一种分治思想的算法，它的实现过程如下：

def quick_sort(data):
    if len(data) <= 1:
        return data
    pivot = data[0]
    left = [x for x in data[1:] if x <= pivot]
    right = [x for x in data[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

例如，对于输入列表 [3, 1, 2, 5, 4]，快速排序算法的输出结果为 [1, 2, 3, 4, 5]。

九、堆排序

堆排序是一种树形选择排序。它的实现过程如下：

def heap_sort(data):
    def sift_down(start, end):
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and data[child] < data[child+1]:
                child += 1
            if data[root] < data[child]:
                data[root], data[child] = data[child], data[root]
                root = child
            else:
                break

    for start in range((len(data)-2)//2, -1, -1):
        sift_down(start, len(data)-1)

    for end in range(len(data)-1, 0, -1):
        data[0], data[end] = data[end], data[0]
        sift_down(0, end-1)
    return data

例如，对于输入列表 [3, 1, 2, 5, 4]，堆排序算法的输出结果为 [1, 2, 3, 4, 5]。

十、计数排序

计数排序是一种线性时间复杂度的排序算法，它的实现过程如下：

def counting_sort(data):
    bucket = [0] * (max(data)+1)
    for i in data:
        bucket[i] += 1
    index = 0
    for i in range(len(bucket)):
        while bucket[i] > 0:
            data[index] = i
            index += 1
            bucket[i] -= 1
    return data

例如，对于输入列表 [3, 1, 2, 5, 4]，计数排序算法的输出结果为 [1, 2, 3, 4, 5]。

十一、桶排序

桶排序是一种线性时间复杂度的排序算法，它的实现过程如下：

def bucket_sort(data):
    max_num = max(data)
    min_num = min(data)
    bucket_size = 5
    bucket_count = (max_num - min_num) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]
    for i in data:
        buckets[(i-min_num)//bucket_size].append(i)
    result = []
    for b in buckets:
        if b:
            result.extend(sorted(b))
    return result

例如，对于输入列表 [3, 1, 2, 5, 4]，桶排序算法的输出结果为 [1, 2, 3, 4, 5]。

十二、基数排序

基数排序是一种多关键字排序算法，它的实现过程如下：

def radix_sort(data):
    max_num = max(data)
    max_digits = len(str(max_num))
    mod = 10
    dev = 1
    for i in range(max_digits):
        buckets = [[] for _ in range(mod*2)]
        for j in data:
            bucket_index = j // dev % mod + mod
            buckets[bucket_index].append(j)
        dev *= 10
        data = [x for b in buckets for x in b]
    return data

例如，对于输入列表 [3, 1, 2, 5, 4]，基数排序算法的输出结果为 [1, 2, 3, 4, 5]。

结语

以上就是十大经典排序算法的实现过程。需要注意的是，不同的排序算法在不同场景下可能会有不同的表现。掌握不同的排序算法，能够帮助我们更好地解决实际问题。