常见排序算法及其实现

# 1. I. 导论

A. 算法的重要性

B. 排序算法的定义

C. 排序算法的分类

# 2. 冒泡排序（Bubble Sort）

冒泡排序是一种简单直观的排序算法。它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复地进行直到没有再需要交换，也就是说该列表已经排序完成。以下是关于冒泡排序的详细内容：

A. **算法原理**
冒泡排序算法原理是通过每次比较相邻的两个元素，如果它们的顺序错误则交换它们，这样一轮过后，最大（或最小）的元素就会沉到底部。重复进行这个过程，直到整个序列排列好。

B. **时间复杂度分析**
在最坏的情况下，冒泡排序的时间复杂度是O(n^2)，最好的情况下是O(n)。

C. **实现代码示例**

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

# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("排序后的数组：", sorted_arr)

**代码总结：** 冒泡排序比较简单，但由于其时间复杂度较高，不适合处理大量数据的排序。

D. **算法优化**
冒泡排序可以通过增加标记位来进行优化，如果一轮循环中没有发生元素交换，说明数组已经有序，可以提前结束排序。

# 3. III. 插入排序（Insertion Sort）

#### A. 算法原理
插入排序是一种简单直观的排序算法。它的原理是将待排序的数组分成已排序和未排序两部分，然后依次将未排序部分的元素插入到已排序部分的合适位置，直到整个数组有序。

#### B. 时间复杂度分析
最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^2)，最好时间复杂度为O(n)。空间复杂度为O(1)。

#### C. 实现代码示例（Python）

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