Python-排序算法

[Panda-Z-Coding]

四种常见的排序算法的详细解释及其对应的Python代码实现：

1. 冒泡排序（Bubble Sort）
2. 堆排序（Heap Sort）
3. 插入排序（Insertion Sort）
4. 选择排序（Selection Sort）

---

1. 冒泡排序（Bubble Sort）

算法简介

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

Python代码实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 提前退出标志位
        swapped = False
        # 每次遍历后，最大的元素会“冒泡”到末尾
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # 交换
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 如果没有发生交换，说明数组已经有序
        if not swapped:
            break
    return arr

# 示例使用
if __name__ == "__main__":
    sample_list = [64, 34, 25, 12, 22, 11, 90]
    print("原始列表:", sample_list)
    sorted_list = bubble_sort(sample_list)
    print("排序后列表:", sorted_list)

运行结果

原始列表: [64, 34, 25, 12, 22, 11, 90]
排序后列表: [11, 12, 22, 25, 34, 64, 90]

算法分析

• 时间复杂度：
  • 最佳情况：O(n)（当数组已经有序时）
  • 平均和最坏情况：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：稳定

---

2. 堆排序（Heap Sort）

算法简介

堆排序是一种基于比较的排序算法，利用堆这种数据结构来排序。堆是一种完全二叉树，分为最大堆和最小堆。堆排序通常使用最大堆，先构建一个最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，之后对剩下的元素重新调整为最大堆，如此反复，直到整个数组有序。

Python代码实现

def heapify(arr, n, i):
    largest = i  # 初始化最大值为根节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点比根节点大
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点比当前最大的还大
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是根节点
    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

# 示例使用
if __name__ == "__main__":
    sample_list = [12, 11, 13, 5, 6, 7]
    print("原始列表:", sample_list)
    sorted_list = heap_sort(sample_list)
    print("排序后列表:", sorted_list)

运行结果

原始列表: [12, 11, 13, 5, 6, 7]
排序后列表: [5, 6, 7, 11, 12, 13]

算法分析

• 时间复杂度：
  • 所有情况：O(n log n)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定

---

3. 插入排序（Insertion Sort）

算法简介

插入排序是一种简单直观的排序算法，类似于整理扑克牌的方式。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

Python代码实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入的元素
        j = i -1
        # 将arr[i]插入到已排序部分的正确位置
        while j >=0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 移动元素
            j -=1
        arr[j + 1] = key  # 插入

    return arr

# 示例使用
if __name__ == "__main__":
    sample_list = [31, 41, 59, 26, 41, 58]
    print("原始列表:", sample_list)
    sorted_list = insertion_sort(sample_list)
    print("排序后列表:", sorted_list)

运行结果

原始列表: [31, 41, 59, 26, 41, 58]
排序后列表: [26, 31, 41, 41, 58, 59]

算法分析

• 时间复杂度：
  • 最佳情况：O(n)（当数组已经有序时）
  • 平均和最坏情况：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：稳定

---

4. 选择排序（Selection Sort）

算法简介

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

Python代码实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前索引为最小值
        min_idx = i
        # 在剩下的元素中寻找最小值
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 交换找到的最小值与当前位置的值
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例使用
if __name__ == "__main__":
    sample_list = [64, 25, 12, 22, 11]
    print("原始列表:", sample_list)
    sorted_list = selection_sort(sample_list)
    print("排序后列表:", sorted_list)

运行结果

原始列表: [64, 25, 12, 22, 11]
排序后列表: [11, 12, 22, 25, 64]

算法分析

• 时间复杂度：
  • 所有情况：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定

---

总结

以上四种排序算法各有优缺点：

1. 冒泡排序：实现简单，但效率较低，适用于小规模数据。
2. 堆排序：时间复杂度稳定为O(n log n)，适用于大规模数据，但不稳定。
3. 插入排序：在数据基本有序的情况下效率较高，适用于小规模数据，且稳定。
4. 选择排序：实现简单，但效率不高，不适合大规模数据，不稳定。

根据具体的应用场景和数据特点选择合适的排序算法，可以在保证效率的同时满足稳定性等需求。

如果你对某个排序算法有更多的问题或需要更详细的解释，欢迎继续提问！

PythonForAlgorithm