基本排序算法

一、冒泡排序

1. 什么是冒泡排序？

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它得名于其工作方式，即较小（或较大）的元素会像水中的气泡一样，通过不断交换，慢慢“浮”到数列的顶端。

a. 核心思想

它重复地遍历待排序的数列，一次比较两个相邻的元素，如果它们的顺序（如从大到小或从小到大）错误就把它们交换过来。遍历数列的工作会重复地进行，直到没有再需要交换的元素为止，这意味着整个数列已经排序完成。

b. 工作原理

比较相邻元素：从列表的第一个元素开始，比较它和下一个元素。
交换：如果第一个元素比第二个元素大（以升序为例），就交换它们的位置。
向后移动：继续比较下一对相邻的元素（即新的第二个和第三个元素），重复步骤2。
完成一轮：持续这个过程，直到列表的末尾。经过第一轮遍历后，最大的元素会被放置在列表的最后一个位置。
重复：对除了最后一个元素之外的所有元素，重复以上步骤。每一轮遍历都会将当前未排序部分的最大元素放到其最终位置。
终止：当某一轮遍历中没有发生任何交换时，说明列表已经完全排序，可以提前终止算法。

2. 图解示例

让我们用一个简单的例子 [5, 1, 4, 2, 8] 来演示冒泡排序的过程（升序排列）。

第一轮 (Pass 1):

(5, 1): 5 > 1，交换 -> [1, 5, 4, 2, 8]
(5, 4): 5 > 4，交换 -> [1, 4, 5, 2, 8]
(5, 2): 5 > 2，交换 -> [1, 4, 2, 5, 8]
(5, 8): 5 < 8，不交换 -> [1, 4, 2, 5, 8]
结果: 经过第一轮，最大的元素 8 已经“冒泡”到了正确的位置。

第二轮 (Pass 2): (现在只需要处理前4个元素)

(1, 4): 1 < 4，不交换 -> [1, 4, 2, 5, 8]
(4, 2): 4 > 2，交换 -> [1, 2, 4, 5, 8]
(4, 5): 4 < 5，不交换 -> [1, 2, 4, 5, 8]
结果: 第二大的元素 5 已经就位。

第三轮 (Pass 3): (现在只需要处理前3个元素)

(1, 2): 1 < 2，不交换 -> [1, 2, 4, 5, 8]
(2, 4): 2 < 4，不交换 -> [1, 2, 4, 5, 8]
结果: 此时，我们发现这一轮没有发生任何交换。这意味着列表已经排好序了，可以提前结束。

最终排序结果: [1, 2, 4, 5, 8]

3. Python 代码实现

下面提供了两种 Python 实现：一个基础版本和一个优化版本。

a. 基础版冒泡排序

这个版本直接翻译了冒泡排序的基本思想，即使列表已经排好序，它也会完成所有的循环。

def bubble_sort_basic(arr):
    """
    基础版冒泡排序
    """
    n = len(arr)
    
    # 外层循环决定了需要进行多少轮“冒泡”
    for i in range(n):
        # 内层循环负责每一轮的比较和交换
        # -i 是因为每轮过后，末尾的 i 个元素已经是有序的了，无需再比较
        # -1 是因为我们要比较 arr[j] 和 arr[j+1]，防止索引越界
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素（升序排列），则交换
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j] # Pythonic 的交换方式

# --- 示例 ---
my_list = [5, 1, 4, 2, 8]
bubble_sort_basic(my_list)
print("基础版排序后的列表:", my_list)  # 输出: [1, 2, 4, 5, 8]

another_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort_basic(another_list)
print("基础版排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

b. 优化版冒泡排序

如果在某一轮遍历中，一次交换都没有发生，这说明整个列表已经是有序的了。我们可以利用这一点来提前结束排序，从而提高效率。

def bubble_sort_optimized(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]
                # 只要发生了一次交换，就将标志位设为 True
                swapped = True
        
        # 如果在一整轮的比较中都没有发生交换，说明列表已经有序
        # 此时可以提前退出循环
        if not swapped:
            break

# --- 示例 ---
my_list_opt = [5, 1, 4, 2, 8]
bubble_sort_optimized(my_list_opt)
print("优化版排序后的列表:", my_list_opt)  # 输出: [1, 2, 4, 5, 8]

# 对于一个几乎有序的列表，优化效果会很明显
nearly_sorted_list = [1, 2, 4, 3, 5, 6]
bubble_sort_optimized(nearly_sorted_list)
print("优化版排序后的列表:", nearly_sorted_list) # 输出: [1, 2, 3, 4, 5, 6]

4. 算法分析

时间复杂度:
- 最坏情况: O(n²)。当待排序列表是完全逆序时，需要进行 n*(n-1)/2 次比较和交换。
- 平均情况: O(n²)。
- 最好情况: O(n)。当列表已经是有序的时，对于优化版的冒泡排序，只需要进行一轮遍历（n-1次比较）而没有任何交换，即可确定列表已有序并终止。
空间复杂度: O(1)。冒泡排序是原地排序算法，因为它只需要一个额外的临时变量来进行元素交换，所需空间是常数级别的。
稳定性: 冒泡排序是稳定的。因为只有当 arr[j] > arr[j+1] 时才会交换，相等的值不会改变它们的相对顺序。

5. 小结

优点:

实现简单：代码逻辑非常清晰，容易理解和实现。
稳定性：是一种稳定的排序算法。
空间效率高：是原地排序，不需要额外的存储空间。

缺点:

时间效率低：O(n²) 的时间复杂度使其在处理大规模数据时非常慢。

因此，冒泡排序在实际应用中很少被使用，它更多地是作为一种教学工具，帮助初学者理解排序算法的基本思想。

二、选择排序

1. 什么是选择排序？

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

a. 核心思想

算法将列表分为两个部分：

已排序部分：位于列表的前端。
未排序部分：位于列表的后端。

在每一轮迭代中，算法会从“未排序部分”中挑选出最小的元素，并将其与“未排序部分”的第一个元素交换位置。这样，已排序部分的长度就增加了一，而未排序部分的长度减少了一。

b. 工作原理

找到最小值：从列表的第一个元素开始，遍历整个列表，找到最小元素的索引。
交换：将找到的最小元素与列表的第一个元素进行交换。此时，第一个元素就是整个列表最小的，它现在属于“已排序部分”。
缩小范围：从列表的第二个元素开始，重复以上过程（在剩余的“未排序部分”中找到最小值，并与该部分的第一个元素交换）。
重复：持续这个过程，每次都将未排序部分的查找范围缩小一个元素。
终止：当“未排序部分”只剩下一个元素时，整个列表就已经排序完成了。

2. 图解示例

我们还是用 [5, 1, 4, 2, 8] 这个例子来演示选择排序的过程（升序排列）。

初始状态: [5, 1, 4, 2, 8] (整个列表都是未排序部分)

第一轮 (Pass 1):

查找范围: [5, 1, 4, 2, 8]
在范围中找到的最小元素是 1。
将 1 与范围的第一个元素 5 交换。
结果: [1, 5, 4, 2, 8]
已排序部分: [1]

第二轮 (Pass 2):

查找范围: [5, 4, 2, 8] (从第二个元素开始)
在范围中找到的最小元素是 2。
将 2 与范围的第一个元素 5 交换。
结果: [1, 2, 4, 5, 8]
已排序部分: [1, 2]

第三轮 (Pass 3):

查找范围: [4, 5, 8] (从第三个元素开始)
在范围中找到的最小元素是 4。
它本身就是范围的第一个元素，所以和自己交换（无变化）。
结果: [1, 2, 4, 5, 8]
已排序部分: [1, 2, 4]

第四轮 (Pass 4):

查找范围: [5, 8] (从第四个元素开始)
在范围中找到的最小元素是 5。
它本身就是范围的第一个元素，和自己交换（无变化）。
结果: [1, 2, 4, 5, 8]
已排序部分: [1, 2, 4, 5]

此时，未排序部分只剩下 [8]，算法结束。

最终排序结果: [1, 2, 4, 5, 8]

3. Python 代码实现

下面是选择排序的 Python 代码实现。

def selection_sort(arr):
    """
    选择排序函数
    """
    n = len(arr)
    
    # 遍历整个列表，i 是已排序部分的边界
    for i in range(n):
        # 假设当前位置的元素是未排序部分中的最小元素
        min_index = i
        
        # 遍历 i 之后的所有元素，以找到真正的最小元素
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # 更新最小元素的索引
                
        # 将找到的最小元素与当前位置 i 的元素进行交换
        # 如果 min_index 没有改变，就意味着当前元素已经是最小的，无需交换
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

# --- 示例 ---
my_list = [5, 1, 4, 2, 8]
selection_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [1, 2, 4, 5, 8]

another_list = [64, 34, 25, 12, 22, 11, 90]
selection_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度:
- 最坏情况: O(n²)。
- 平均情况: O(n²)。
- 最好情况: O(n²)。
- 解释：无论输入数据是什么样的（即使是已经排好序的），选择排序的比较次数都是固定的。它有两层嵌套循环，外层循环 n-1 次，内层循环的比较次数是一个等差数列 (n-1) + (n-2) + ... + 1，总比较次数为 n*(n-1)/2。因此，其时间复杂度总是 O(n²)。
空间复杂度: O(1)。选择排序也是原地排序算法，只需要一个额外的变量 min_index 来存储索引，空间是常数级别的。
稳定性: 选择排序是不稳定的。
- 解释：稳定性指相等的元素在排序后其相对位置保持不变。在选择排序中，交换操作可能会打乱相等元素的原始顺序。
- 例如，对于列表 [5a, 8, 5b, 2]（5a 和 5b 值相等，但我们用 a 和 b 区分它们），第一轮会找到 2，然后将 5a 和 2 交换，列表变为 [2, 8, 5b, 5a]。此时，5b 跑到了 5a 的前面，它们的相对顺序改变了。

5. 小结

优点:

实现简单：和冒泡排序一样，逻辑简单，易于理解。
移动次数少：对于每个元素，最多只会进行一次交换。如果数据的交换成本（移动成本）远高于比较成本，选择排序会比冒泡排序更有优势。

缺点:

时间效率低：O(n²) 的时间复杂度使其不适合处理大规模数据。
性能固定：无法像优化后的冒泡排序那样，在数据基本有序时提前结束，它总是会执行完所有的比较。

总的来说，选择排序也是一种主要用于教学目的的算法，在实际工程中很少使用。

三、插入排序

1. 什么是插入排序？

插入排序（Insertion Sort）是一种简单直观的排序算法，其工作方式非常像我们平时整理扑克牌。我们每次从牌堆里抽一张牌，然后将它插入到手中已有牌的正确位置，以保证手中的牌一直是有序的。

a. 核心思想

算法将列表分成“已排序”和“未排序”两个部分。初始时，已排序部分只包含第一个元素。然后，算法每次从未排序部分取出一个元素，在已排序部分中从后向前扫描，找到相应的位置并插入。

b. 工作原理

从第二个元素开始：将列表的第一个元素视为一个已排序的子序列。
选择并比较：取出未排序部分的第一个元素（我们称之为“待插入元素”或 key）。
向后移动：将这个 key 与已排序子序列中的元素从后向前逐一比较。如果已排序的元素大于 key，则将该元素向右移动一个位置。
插入：重复步骤3，直到找到一个小于或等于 key 的元素，或者已到达子序列的开头。然后将 key 插入到这个位置。
重复：对未排序部分的所有元素重复步骤2-4，直到整个列表都变为已排序状态。

2. 图解示例

我们用 [5, 2, 4, 6, 1, 3] 这个例子来演示插入排序的过程（升序排列）。我们将用 | 符号来分隔已排序和未排序部分。

初始状态: [5 | 2, 4, 6, 1, 3] (已排序部分是 [5])

第一轮 (处理 2):

key = 2。
比较 2 和 5。5 > 2，所以将 5 向右移动 -> [ _, 5, 4, 6, 1, 3]
已到达列表开头，将 2 插入空位。
结果: [2, 5 | 4, 6, 1, 3]

第二轮 (处理 4):

key = 4。
比较 4 和 5。5 > 4，将 5 向右移动 -> [2, _, 5, 6, 1, 3]
比较 4 和 2。2 < 4，停止移动。将 4 插入空位。
结果: [2, 4, 5 | 6, 1, 3]

第三轮 (处理 6):

key = 6。
比较 6 和 5。5 < 6，停止移动。6 保持原位。
结果: [2, 4, 5, 6 | 1, 3]

第四轮 (处理 1):

key = 1。
比较 1 和 6 (6 > 1) -> 右移 6
比较 1 和 5 (5 > 1) -> 右移 5
比较 1 和 4 (4 > 1) -> 右移 4
比较 1 和 2 (2 > 1) -> 右移 2
已到达列表开头，将 1 插入。
结果: [1, 2, 4, 5, 6 | 3]

第五轮 (处理 3):

key = 3。
比较 3 和 6 (6 > 3) -> 右移 6
比较 3 和 5 (5 > 3) -> 右移 5
比较 3 和 4 (4 > 3) -> 右移 4
比较 3 和 2 (2 < 3)，停止移动。将 3 插入。
结果: [1, 2, 3, 4, 5, 6]

算法结束，列表已完全排序。

3. Python 代码实现

下面是插入排序的 Python 代码实现。

def insertion_sort(arr):
    """
    插入排序函数
    """
    # 从第二个元素开始遍历 (索引为 1)
    # 因为第一个元素自己就是一个已排序的子序列
    for i in range(1, len(arr)):
        # key 是当前需要被插入的元素
        key = arr[i]
        
        # j 是已排序部分的最后一个元素的索引
        j = i - 1
        
        # 将 key 与已排序部分的元素从后向前比较
        # 如果已排序的元素大于 key，则将其向后移动
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 元素后移
            j -= 1
            
        # 当循环结束时，j+1 就是 key 应该插入的位置
        arr[j + 1] = key

# --- 示例 ---
my_list = [5, 2, 4, 6, 1, 3]
insertion_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [1, 2, 3, 4, 5, 6]

another_list = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度:
- 最坏情况: O(n²)。当待排序列表是完全逆序时，每个元素都需要与前面所有已排序的元素进行比较和移动。
- 平均情况: O(n²)。
- 最好情况: O(n)。当列表已经是有序的时，每次插入操作只需要进行一次比较，内层循环不会执行。这使得插入排序在处理“几乎有序”的数据时非常高效。
空间复杂度: O(1)。插入排序是原地排序算法，只需要一个额外的变量 key 来存储待插入元素，空间是常数级别的。
稳定性: 插入排序是稳定的。
- 解释：当待插入元素 key 遇到与它相等的元素时，循环条件 key < arr[j] 为假，循环会停止，key 会被插入到这个相等元素的后面。因此，相等元素的原始相对顺序得以保留。

5. 小结

优点:

实现简单：代码简洁，易于理解。
高效处理小规模或基本有序的数据：对于小列表，它的性能很好。对于几乎排好序的列表，它的时间复杂度接近线性 O(n)，这是它优于冒泡排序和选择排序的一个重要特点。
稳定性：是一种稳定的排序算法。
空间效率高：是原地排序，占用极少的额外空间。
在线算法 (Online Algorithm)：可以边接收数据边排序，因为它在决定一个元素的位置时，不需要知道后面元素的信息。

缺点:

时间效率低：对于大规模且无序的数据，O(n²) 的时间复杂度使其效率低下，不如快速排序、归并排序等 O(n log n) 算法。

总的来说，插入排序是小型数据集和几乎有序数据集的绝佳选择。在一些复杂排序算法中（如 Timsort，Python 的 list.sort() 和 sorted() 使用的算法），当数据块小到一定程度时，也会切换到插入排序来进行处理。

四、快速排序

快速排序（Quicksort）是计算机科学中最著名和使用最广泛的排序算法之一。它由托尼·霍尔在1959年发明。

1. 什么是快速排序？

快速排序是一种高效的、基于分治法（Divide and Conquer） 的排序算法。与归并排序类似，它也将问题分解为更小的子问题来解决，但其分治的方式非常独特。

a. 核心思想 (分治法)

快速排序将一个大数组的排序问题分解为对两个小数组的排序问题。其步骤如下：

分解 (Divide)：
- 从数组中选择一个元素，我们称之为 “基准”（Pivot）。
- 重新排列数组，将所有小于基准的元素移动到基准的左边，所有大于基准的元素移动到基准的右边。相等的元素可以放在任何一边。
- 完成这个过程后，基准元素就处于其最终的排序位置。这个过程被称为 “分区”（Partitioning）。
征服 (Conquer)：
- 递归地对基准左边的子数组和右边的子数组进行快速排序。
合并 (Combine)：
- 因为子数组是原地排序的，所以当递归结束时，整个数组就已经排好序了。这个步骤是隐式的，不需要任何操作。

b. 分区（Partition）操作是关键

分区的实现方式有很多种，最著名的是 Lomuto 分区方案。其工作原理如下：

通常选择数组的最后一个元素作为基准。
维护一个指针 i，它指向“小于基准”区域的最后一个元素的下一个位置（可以看作是这个区域的右边界）。初始时，i 在数组的起始位置之前。
用另一个指针 j 遍历数组（从头到倒数第二个元素）。
如果 arr[j] 小于或等于基准，就将 i 向右移动一位，然后交换 arr[i] 和 arr[j]。这相当于将小于基准的元素 arr[j] 放入“小于基准”的区域。
遍历结束后，将基准元素（原本在数组末尾）与 arr[i+1] 交换。这样，基准就恰好位于所有比它小的元素和所有比它大的元素之间。
返回基准的新索引。

2. 图解示例

我们用 [7, 2, 1, 6, 8, 5, 3, 4] 这个例子来演示快速排序的过程。

初始调用: quick_sort([7, 2, 1, 6, 8, 5, 3, 4])

第一轮 (Partition):

选择基准（Pivot），我们选最后一个元素 4。
分区过程会将 <4 的元素放到左边，>4 的元素放到右边。
分区后的数组可能样子是：[3, 2, 1, 4, 8, 5, 7, 6] (注意：分区结果不唯一，取决于具体实现)
现在 4 已经找到了它的最终位置（索引3）。

第二轮 (递归调用):

现在问题变成了两个独立的子问题：
1. 对 4 左边的子数组 [3, 2, 1] 进行快速排序。
2. 对 4 右边的子数组 [8, 5, 7, 6] 进行快速排序。
处理左子数组 [3, 2, 1]:
- 选择基准 1。
- 分区后：[1, 2, 3] (1 位于正确位置)。
- 递归处理 1 左边（空）和右边 [2, 3] 的子数组。
- 处理 [2, 3]，基准为 3，分区后不变，2 在左，排序完成。
处理右子数组 [8, 5, 7, 6]:
- 选择基准 6。
- 分区后：[5, 6, 7, 8] (6 位于正确位置)。
- 递归处理 6 左边 [5] 和右边 [7, 8] 的子数组。
- [5] 已排序。处理 [7, 8]，基准为 8，分区后不变，7 在左，排序完成。

最终结果:
当所有递归调用都返回后，原始数组就变成了 [1, 2, 3, 4, 5, 6, 7, 8]。

3. Python 代码实现

下面是使用 Lomuto 分区方案的快速排序 Python 实现。

def partition(arr, low, high):
    """
    分区函数 (Lomuto partition scheme)
    
    Args:
        arr: 待分区的列表
        low: 起始索引
        high: 结束索引 (也是基准元素的索引)
        
    Returns:
        基准元素分区后的最终索引
    """
    # 选择最后一个元素作为基准
    pivot = arr[high]
    
    # i 是指向小于基准的区域的最后一个元素的下一个位置
    i = low - 1
    
    # 遍历从 low 到 high-1 的元素
    for j in range(low, high):
        # 如果当前元素小于或等于基准
        if arr[j] <= pivot:
            # 将 i 向右移动
            i += 1
            # 将小于基准的元素 arr[j] 交换到 i 指向的位置
            arr[i], arr[j] = arr[j], arr[i]
            
    # 将基准元素放到正确的位置 (i+1)
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    
    # 返回基准的索引
    return i + 1

def _quick_sort_recursive(arr, low, high):
    """
    快速排序的递归辅助函数
    """
    if low < high:
        # pi 是分区后基准的索引
        pi = partition(arr, low, high)
        
        # 递归地对基准左边的子数组进行排序
        _quick_sort_recursive(arr, low, pi - 1)
        
        # 递归地对基准右边的子数组进行排序
        _quick_sort_recursive(arr, pi + 1, high)

def quick_sort(arr):
    """
    快速排序主函数
    """
    _quick_sort_recursive(arr, 0, len(arr) - 1)


# --- 示例 ---
my_list = [7, 2, 1, 6, 8, 5, 3, 4]
quick_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [1, 2, 3, 4, 5, 6, 7, 8]

another_list = [64, 34, 25, 12, 22, 11, 90]
quick_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度:
- 最坏情况: O(n²)。当每次选择的基准都是当前数组中的最小或最大元素时发生（例如，对一个已经排好序的数组进行排序）。这会导致分区极不平衡，递归树退化成一个线性链表。
- 平均情况: O(n log n)。这是快速排序最常见的情况。每次分区都将数组分成大致相等的两部分，递归树的深度为 log n，每层分区操作的总时间是 O(n)。
- 最好情况: O(n log n)。每次分区都恰好将数组分成两半。
空间复杂度: O(log n) (平均情况) 到 O(n) (最坏情况)。这个空间是递归调用栈所占用的。平均情况下递归深度为 log n，最坏情况下为 n。
稳定性: 快速排序是不稳定的。在分区过程中，元素交换可能会改变相等元素的原始相对顺序。

5. 优化

为了避免最坏情况的发生，可以优化基准的选择：

随机基准：随机选择一个元素作为基准。这使得最坏情况在实践中几乎不可能发生。
三数取中 (Median-of-Three)：取数组的第一个、中间一个和最后一个元素的中位数作为基准。这能有效避免在有序或逆序数组上性能下降的问题。

6. 小结

优点:

极高的平均效率：O(n log n) 的平均时间复杂度，并且其常数因子很小，使其在实践中通常比其他 O(n log n) 算法（如归并排序、堆排序）更快。
原地排序：通常是原地排序，只需要 O(log n) 的栈空间。

缺点:

最坏情况性能差：O(n²) 的时间复杂度在某些情况下可能发生。
不稳定：不保证相等元素的相对顺序。
对小数据量效率不高：对于非常小的数组，其递归开销可能比插入排序等简单算法更大。因此，一些优化的快速排序实现会在子数组小到一定程度时，切换到插入排序。

五、归并排序

1. 什么是归并排序？

归并排序（Merge Sort）是另一种基于分治法（Divide and Conquer）思想的高效排序算法。它的名字来源于其核心操作——“归并”（Merge），即将两个已经排好序的序列合并成一个有序序列。

a. 核心思想 (分治法)

归并排序将排序问题分解为三个步骤：

分解 (Divide)：将待排序的列表不断地对半分割，直到每个子列表只包含一个元素。一个只包含一个元素的列表自然就是有序的。
征服 (Conquer)：这一步是隐式的。因为分解到最后，每个子列表都只有一个元素，所以它们已经是“已排序”的状态。
合并 (Combine)：从最小的子列表开始，将相邻的两个已排序的子列表归并成一个更大的、有序的列表。这个过程不断重复，直到所有子列表被合并成一个完整的、有序的列表。

b. 工作原理

归并排序的关键在于**“合并”**这一步。假设我们有两个已经排好序的列表 A 和 B，如何将它们合并成一个有序的大列表 C 呢？

创建两个指针，分别指向 A 和 B 的起始位置。
比较两个指针指向的元素。
将较小的那个元素复制到 C 中，并将该指针向后移动一位。
重复步骤2和3，直到其中一个列表的所有元素都被复制完毕。
将另一个列表中剩余的所有元素直接复制到 C 的末尾。

2. 图解示例

我们用 [8, 3, 1, 7, 0, 10, 2] 这个例子来演示归并排序的过程。

1. 分解 (Splitting Phase):

                [8, 3, 1, 7, 0, 10, 2]
               /                       \
        [8, 3, 1, 7]                  [0, 10, 2]
       /           \                 /          \
   [8, 3]        [1, 7]            [0, 10]      [2]
  /      \      /      \          /       \
[8]      [3]  [1]      [7]      [0]       [10]

分解过程一直持续到每个子列表只有一个元素。

2. 合并 (Merging Phase):

现在，我们从底层开始，将这些单元素的列表两两合并。

[8] 和 [3] 合并成 [3, 8]
[1] 和 [7] 合并成 [1, 7]
[0] 和 [10] 合并成 [0, 10]
[2] 保持不变（因为它没有相邻的伙伴）

此时，列表结构变为：

1	[3, 8] [1, 7] [0, 10] [2]

[3, 8] 和 [1, 7] 合并成 [1, 3, 7, 8]
[0, 10] 和 [2] 合并成 [0, 2, 10]

此时，列表结构变为：

1	[1, 3, 7, 8] [0, 2, 10]

最后，[1, 3, 7, 8] 和 [0, 2, 10] 合并成最终结果 [0, 1, 2, 3, 7, 8, 10]

最终排序结果: [0, 1, 2, 3, 7, 8, 10]

3. Python 代码实现

下面是归并排序的典型 Python 递归实现。

def merge_sort(arr):
    """
    归并排序函数
    """
    # 递归的终止条件：如果列表只有一个元素或为空，则它已经是有序的
    if len(arr) > 1:
        # 1. 分解 (Divide)
        mid = len(arr) // 2  # 找到列表的中间位置
        left_half = arr[:mid]  # 分割成左半部分
        right_half = arr[mid:] # 分割成右半部分

        # 递归地对左右两半进行排序
        merge_sort(left_half)
        merge_sort(right_half)

        # 2. 合并 (Combine/Merge)
        i = 0  # 左半部分的索引
        j = 0  # 右半部分的索引
        k = 0  # 合并后主列表的索引

        # 当左右两半都还有元素时，进行比较
        while i < len(left_half) and j < len(right_half):
            if left_half[i] <= right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 检查是否有剩余的元素
        # 如果左半部分还有剩余，直接复制过来
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        # 如果右半部分还有剩余，直接复制过来
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# --- 示例 ---
my_list = [8, 3, 1, 7, 0, 10, 2]
merge_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [0, 1, 2, 3, 7, 8, 10]

another_list = [64, 34, 25, 12, 22, 11, 90]
merge_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度: O(n log n)。
- 解释：分解过程将列表分成两半，这个过程的递归树深度是 log n。在每一层递归中，合并操作都需要遍历该层的所有元素，总共是 n 个元素。因此，总的时间复杂度是 n * log n。
- 这个时间复杂度非常稳定，无论是最好、最坏还是平均情况，都是 O(n log n)。这是归并排序的一个巨大优势。
空间复杂度: O(n)。
- 解释：归并排序不是原地排序。在合并阶段，需要创建临时的 left_half 和 right_half 列表来存储数据。在递归的每一层，这些临时列表加起来的总空间是 O(n)。
稳定性: 归并排序是稳定的。
- 解释：在合并操作中，当遇到相等的元素时（left_half[i] <= right_half[j]），我们总是先取左半部分的元素。这保证了相等元素的原始相对顺序不会改变。

5. 小结

优点:

性能稳定可靠：时间复杂度始终是 O(n log n)，不受输入数据的影响。
稳定性：是一种稳定的排序算法，适用于需要保持相等元素相对顺序的场景。
适用性广：特别适合对链表进行排序，因为链表插入操作 O(1)，可以避免数组复制带来的开销。也适用于外部排序（数据量大到无法一次性载入内存）。

缺点:

空间复杂度较高：需要 O(n) 的额外空间，这在内存受限的情况下可能是一个问题。相比之下，快速排序的平均空间复杂度是 O(log n)。

总的来说，归并排序是一种非常强大和可靠的排序算法，当需要一个性能稳定或排序结果稳定的算法时，它是一个绝佳的选择。

六、堆排序

1. 什么是堆排序？

堆排序是一种基于比较的排序算法，它利用了一种叫做 “堆”（Heap） 的数据结构。你可以把它看作是选择排序的一种改进版本。在选择排序中，我们每次都需要线性扫描 O(n) 来找到未排序部分的最大（或最小）元素。而堆排序通过将数据组织成一个堆，可以在 O(log n) 的时间内找到最大（或最小）元素，从而提高了效率。

a. 核心前提：什么是堆（Heap）？

在介绍堆排序之前，必须先理解“堆”。堆是一个近似完全二叉树的结构，并同时满足堆的性质：

结构性：它是一棵完全二叉树。这意味着树的每一层都是完全填满的，除了最后一层，最后一层的节点都尽量靠左排列。这使得我们可以用一个 数组（列表） 来高效地表示它，而无需使用指针。
- 对于数组中索引为 i 的节点：
  - 其父节点索引：(i - 1) // 2
  - 其左子节点索引：2 * i + 1
  - 其右子节点索引：2 * i + 2
堆序性 (Heap Property)：
- 最大堆 (Max-Heap)：父节点的值总是大于或等于其任何一个子节点的值。因此，堆的根节点（数组的第一个元素）是整个堆中的最大值。
- 最小堆 (Min-Heap)：父节点的值总是小于或等于其任何一个子节点的值。因此，堆的根节点是整个堆中的最小值。

为了实现升序排序，我们通常使用最大堆。

b. 堆排序的工作原理

堆排序可以分为两个主要阶段：

阶段一：建堆 (Build Heap)

将待排序的无序列表看作一个完全二叉树。
从最后一个非叶子节点开始，向前逐个处理到根节点。
对每个节点执行一个叫做 “堆化”（Heapify） 或“下沉”（Sift-down）的操作，确保以该节点为根的子树满足最大堆的性质。
当处理完所有非叶子节点后，整个列表就变成了一个最大堆。

阶段二：排序 (Sorting)

此时，列表的第一个元素（根节点）是当前所有元素中的最大值。
将这个最大值与列表的最后一个元素交换。这样，最大的元素就被放到了它最终应该在的正确位置。
将列表的已排序部分（即最后一个元素）从堆中移除（逻辑上通过缩小堆的大小来实现）。
此时，新的根节点可能违反了最大堆的性质。对新的根节点执行一次“堆化”操作，使其恢复最大堆的性质。
重复步骤2-4，每次都将堆顶的最大元素交换到末尾，然后缩小堆的范围并调整堆，直到堆的大小为1。

2. 图解示例

我们用 [4, 10, 3, 5, 1, 2] 来演示堆排序的过程。

阶段一：构建最大堆

初始数组（看作树）：

从最后一个非叶子节点 3 (索引2) 开始堆化，无变化。
处理下一个非叶子节点 10 (索引1)。它的子节点是 5 和 1。10 是最大的，无变化。
处理根节点 4 (索引0)。它的子节点是 10 和 3。10 > 4，交换 4 和 10。
1
2
3
4
5
10
/ \
4 3
/ \ /
5 1 2
交换后，4 到了新位置（原 10 的位置），它的子节点是 5 和 1。5 > 4，再次交换。
1
2
3
4
5
10
/ \
5 3
/ \ /
4 1 2
建堆完成，数组变为 [10, 5, 3, 4, 1, 2]。

阶段二：排序

第一次：堆是 [10, 5, 3, 4, 1, 2]。
- 交换 10 和 2 -> [2, 5, 3, 4, 1, 10]。
- 堆范围缩小为前5个元素 [2, 5, 3, 4, 1]，对根节点 2 进行堆化 -> [5, 4, 3, 2, 1]。
- 此时数组为 [5, 4, 3, 2, 1, 10]。
第二次：堆是 [5, 4, 3, 2, 1]。
- 交换 5 和 1 -> [1, 4, 3, 2, 5]。
- 堆范围缩小为前4个元素 [1, 4, 3, 2]，对根节点 1 进行堆化 -> [4, 2, 3, 1]。
- 此时数组为 [4, 2, 3, 1, 5, 10]。
……以此类推，直到堆中只剩一个元素。

最终排序结果: [1, 2, 3, 4, 5, 10]

3. Python 代码实现

def heapify(arr, n, i):
    """
    将以 i 为根的子树调整为最大堆
    
    Args:
        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)

    # 1. 构建最大堆
    # 从最后一个非叶子节点开始，向前遍历
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. 一个个从堆顶取出元素，进行排序
    # 将当前最大元素（根）与末尾元素交换，然后重新调整堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0) # 对缩小后的堆进行堆化

# --- 示例 ---
my_list = [4, 10, 3, 5, 1, 2]
heap_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [1, 2, 3, 4, 5, 10]

another_list = [64, 34, 25, 12, 22, 11, 90]
heap_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度: O(n log n)。
- 建堆阶段: 虽然看起来是 n/2 次调用 heapify (复杂度 log n)，但精确分析表明建堆的时间复杂度是线性的 O(n)。
- 排序阶段: 进行了 n-1 次交换和 heapify 操作。每次 heapify 的时间复杂度是 O(log n)。所以这部分是 O(n log n)。
- 总计: O(n) + O(n log n) = O(n log n)。这个时间复杂度在最好、最坏和平均情况下都是一样的。
空间复杂度: O(1)。
- 堆排序是原地排序算法，因为它是在原始数组上直接进行操作的，只需要常数级别的额外空间（用于递归调用栈，但可以被迭代写法替代）。
稳定性: 堆排序是不稳定的。
- 解释：在将堆顶元素与堆尾元素交换时，可能会打乱相等元素的原始相对顺序。例如 [3a, 2, 3b]，建堆后可能是 [3b, 2, 3a]，第一次交换会将 3b 与 3a 交换，3a 就跑到了 3b 的后面。

5. 小结

优点:

性能优秀且稳定：O(n log n) 的时间复杂度在各种情况下都得到保证，没有像快速排序那样的 O(n²) 最坏情况。
空间效率高：O(1) 的空间复杂度，是原地排序算法。

缺点:

不稳定：不适用于需要保持相等元素相对顺序的场景。
常数因子较大：在实践中，对于同样的数据，平均性能通常不如经过优化的快速排序，因为其数据访问模式对 CPU 缓存不友好。

堆排序在需要 O(n log n) 最坏情况时间保证和 O(1) 空间复杂度的场景下非常有用，例如在一些嵌入式系统或对内存要求严格的环境中。它也是实现**优先队列（Priority Queue）**的常用数据结构。

七、希尔排序

1. 什么是希尔排序？

希尔排序，也称递减增量排序算法（Diminishing Increment Sort），是插入排序的一种更高效的改进版本。它由 Donald Shell 于1959年提出。

插入排序在处理“几乎有序”的数组时效率非常高，但当数组元素需要移动很长的距离时（例如，最小的元素在数组末尾），它的效率就很低，因为每个元素只能向前移动一个位置。

希尔排序的核心思想就是克服了插入排序的这个缺点。它通过允许交换相隔一定距离的元素，来快速地将元素移动到更接近其最终位置的地方，从而使得整个数组变得“部分有序”。然后，它逐步缩减这个距离，最后进行一次标准的插入排序，此时由于数组已经基本有序，排序速度会非常快。

a. 核心思想

选择一个增量序列（Gap Sequence）：选择一个整数序列 t1, t2, ..., tk，其中 t1 > t2 > ... > tk = 1。这个序列被称为增量或间隙（Gap）。
分组排序：对于每一个增量 t_i，将整个数组分为 t_i 个子数组。每个子数组由所有相隔 t_i 的元素组成。
对子数组进行插入排序：对这 t_i 个子数组分别进行插入排序。由于是同时对多个交错的子数组进行排序，这个过程实际上是在整个数组上进行一次“宏观”的插入排序。
递减增量：重复步骤2和3，使用下一个更小的增量 t_{i+1}。
最终排序：当增量 t_k = 1 时，整个数组被看作一个子数组，执行一次标准的插入排序。但此时，数组已经基本有序，所以这次插入排序的效率非常高。

b. 增量序列的选择

增量序列的选择对希尔排序的性能至关重要。

Shell 原始序列: N/2, N/4, ..., 1 (其中 N 是数组大小)。简单但不是最优。
Knuth 序列: 1, 4, 13, 40, ... (通过 h = 3*h + 1 生成)。性能更好，被广泛使用。
Sedgewick 序列: 1, 5, 19, 41, ... (更复杂的公式)。在实践中表现更好。

对于教学和基础实现，我们通常使用最简单的 Shell 原始序列。

2. 图解示例

我们用 [8, 3, 1, 7, 0, 10, 2] 这个例子来演示希尔排序的过程。数组长度 n = 7。
我们将使用 Shell 原始增量序列。

第一轮：Gap = 7 // 2 = 3

我们将数组分为3个子数组：
- 子数组1: arr[0], arr[3], arr[6] -> [8, 7, 2]
- 子数组2: arr[1], arr[4] -> [3, 0]
- 子数组3: arr[2], arr[5] -> [1, 10]
对每个子数组进行插入排序：
- [8, 7, 2] -> [2, 7, 8]
- [3, 0] -> [0, 3]
- [1, 10] -> [1, 10]
将排序后的元素放回原数组的交错位置。
- 结果数组: [2, 0, 1, 7, 3, 10, 8]
- 注意：数组现在比原来更有序了。像 0, 1, 2 这样的小元素被快速移动到了数组的前端。

第二轮：Gap = 3 // 2 = 1

现在增量为1，这相当于对整个数组进行一次标准的插入排序。
待排序数组是 [2, 0, 1, 7, 3, 10, 8]。
因为这个数组已经“几乎有序”，插入排序会非常快。
- 0 会向前移动两位。
- 1 会向前移动一位。
- 3 会向前移动一位。
- 8 会向前移动一位。
最终排序结果: [0, 1, 2, 3, 7, 8, 10]

3. Python 代码实现

下面是使用 Shell 原始增量序列的 Python 代码实现。

def shell_sort(arr):
    """
    希尔排序函数
    """
    n = len(arr)
    # 初始增量 gap，并不断缩小
    gap = n // 2

    while gap > 0:
        # 下面的循环是分组后的插入排序
        # i 从 gap 开始，确保每个元素都能作为待插入元素
        for i in range(gap, n):
            # temp 是当前待插入的元素
            temp = arr[i]
            # j 是当前元素所在分组的前一个元素的索引
            j = i
            
            # 在当前分组内进行插入排序的比较和移动
            # j >= gap 保证了 j-gap 不会越界
            # arr[j - gap] > temp 是插入排序的核心比较
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            
            # 将待插入元素放入正确的位置
            arr[j] = temp
        
        # 缩小增量
        gap //= 2

# --- 示例 ---
my_list = [8, 3, 1, 7, 0, 10, 2]
shell_sort(my_list)
print("排序后的列表:", my_list)  # 输出: [0, 1, 2, 3, 7, 8, 10]

another_list = [64, 34, 25, 12, 22, 11, 90]
shell_sort(another_list)
print("排序后的列表:", another_list) # 输出: [11, 12, 22, 25, 34, 64, 90]

4. 算法分析

时间复杂度:
- 希尔排序的时间复杂度分析非常复杂，它完全取决于所选的增量序列。
- 最坏情况: 使用 Shell 原始序列 N/2, N/4, ... 时，最坏时间复杂度为 O(n²)。
- 平均/最好情况: 使用更优的增量序列（如 Knuth 序列），其时间复杂度可以达到 O(n^(3/2)) 甚至 O(n log² n)。它优于简单的 O(n²) 排序算法，但劣于 O(n log n) 的高级排序算法。
空间复杂度: O(1)。
- 希尔排序是原地排序算法，只需要一个额外的变量 temp 来存储元素，空间是常数级别的。
稳定性: 希尔排序是不稳定的。
- 解释：在分组排序中，相隔较远的两个相等元素可能会在它们各自的子数组中被交换，从而导致它们的相对顺序发生改变。例如，在 [5a, 1, 5b] 中，如果 gap=2，5a 和 5b 在同一个子数组，它们的顺序可能不会变。但如果 gap=1 之前有其他 gap 使得 5b 被交换到了 5a 前面，稳定性就被破坏了。

5. 小结

优点:

性能优于简单排序：比冒泡排序、选择排序和插入排序等 O(n²) 算法要快得多。
实现相对简单：相比快速排序、归并排序等，代码实现逻辑更简单一些。
空间效率高：是原地排序，只需要 O(1) 的额外空间。

缺点:

性能不稳定：时间复杂度依赖于增量序列，难以精确分析。
算法不稳定：不保证相等元素的相对顺序。
性能瓶颈：对于大规模数据，其性能不如快速排序、归并排序和堆排序等 O(n log n) 算法。

总的来说，希尔排序是一种在简单排序和高级排序之间的“中间地带”算法，适用于中等规模的数据集，并且在对内存要求严格的场景下有一定优势。

八、计数排序

1. 什么是计数排序？

计数排序是一种非比较型的整数排序算法，它的核心思想与我们之前讨论的比较排序算法（如快速排序、归并排序）完全不同。它不是通过比较元素大小来排序，而是通过统计每个整数出现的次数来确定元素的位置。

这个算法的效率非常高，可以达到线性时间复杂度 O(n)，但它有一个重要的限制：它只适用于整数，并且这些整数需要在一个相对较小的范围内。

a. 核心思想

计数 (Counting)：找出待排序数组中最大和最小的元素，然后创建一个“计数数组”（或称为“桶”），其大小足以覆盖从最小到最大的整个整数范围。遍历待排序数组，将每个元素出现的次数记录在计数数组的相应位置上。
累加 (Cumulative Sum)：修改计数数组，使其每个位置上的值是“小于或等于”该索引的元素总数。这样，计数数组就存储了每个元素在排序后应该出现的最终位置信息。
排序 (Placing)：创建一个新的输出数组。反向遍历原始的待排序数组，根据计数数组中的位置信息，将每个元素直接放入输出数组的正确位置，同时更新计数数组中的计数值。

2. 图解示例

我们用一个简单的例子 [4, 2, 2, 8, 3, 3, 1] 来演示计数排序的过程。

1. 找出范围并创建计数数组

数组中的最大值是 8。
创建一个大小为 8 + 1 = 9 的计数数组 count_arr，索引从 0 到 8，初始值全为 0。
count_arr = [0, 0, 0, 0, 0, 0, 0, 0, 0]

2. 统计元素出现次数

遍历原始数组 [4, 2, 2, 8, 3, 3, 1]：
- 遇到 4，count_arr[4] 加 1。
- 遇到 2，count_arr[2] 加 1。
- …
最终得到的计数数组为：
count_arr = [0, 1, 2, 2, 1, 0, 0, 0, 1]
(含义：数字1出现1次，2出现2次，3出现2次，4出现1次，8出现1次)

3. 计算累加和

修改 count_arr，让每个位置存储小于等于当前索引的元素总数。
- count_arr[1] += count_arr[0] -> 1 + 0 = 1
- count_arr[2] += count_arr[1] -> 2 + 1 = 3
- count_arr[3] += count_arr[2] -> 2 + 3 = 5
- count_arr[4] += count_arr[3] -> 1 + 5 = 6
- …
最终得到的累加数组为：
count_arr = [0, 1, 3, 5, 6, 6, 6, 6, 7]
(含义：小于等于1的数有1个，小于等于2的数有3个，小于等于3的数有5个… 这个值减1就是该数字在排序后数组中的最后一次出现的位置索引)

4. 放置到输出数组 (反向遍历)

创建一个与原始数组等长的输出数组 output_arr。
从后向前遍历原始数组 [4, 2, 2, 8, 3, 3, 1]：
- 元素 1: count_arr[1] 是 1。将 1 放到 output_arr 的 1-1=0 索引处。然后 count_arr[1] 减 1。
  output = [1, _, _, _, _, _, _], count_arr[1]=0
- 元素 3 (第二个): count_arr[3] 是 5。将 3 放到 output_arr 的 5-1=4 索引处。count_arr[3] 减 1。
  output = [1, _, _, _, 3, _, _], count_arr[3]=4
- 元素 3 (第一个): count_arr[3] 是 4。将 3 放到 output_arr 的 4-1=3 索引处。count_arr[3] 减 1。
  output = [1, _, _, 3, 3, _, _], count_arr[3]=3
- 元素 8: count_arr[8] 是 7。将 8 放到 output_arr 的 7-1=6 索引处。count_arr[8] 减 1。
  output = [1, _, _, 3, 3, _, 8], count_arr[8]=6
- … 以此类推 …
最终排序结果: [1, 2, 2, 3, 3, 4, 8]

为什么要反向遍历？
反向遍历是为了保证排序的稳定性。当遇到重复元素时（如两个3），原始数组中排在后面的3会先被放入输出数组的靠后位置，这样它们的相对顺序就保持不变了。

3. Python 代码实现

下面提供了两个版本的实现：一个基础版（只处理非负整数）和一个更通用的优化版（处理任意整数范围）。

a. 基础版 (处理非负整数)

def counting_sort_basic(arr):
    """
    计数排序基础版（只适用于非负整数）
    """
    # 1. 处理边界情况
    if len(arr) <= 1:
        return arr

    # 2. 找到最大值以确定计数数组的大小
    max_val = max(arr)
    
    # 3. 创建并填充计数数组
    count_arr = [0] * (max_val + 1)
    for num in arr:
        count_arr[num] += 1
        
    # 4. 计算累加和
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i-1]
        
    # 5. 创建输出数组并从后向前遍历原数组以放置元素
    output_arr = [0] * len(arr)
    for num in reversed(arr):
        # 找到 num 在排序后应该在的位置
        position = count_arr[num] - 1
        output_arr[position] = num
        # 处理重复数字，将下一个同样值的数字放在前一个位置
        count_arr[num] -= 1
        
    return output_arr

# --- 示例 ---
my_list = [4, 2, 2, 8, 3, 3, 1]
sorted_list = counting_sort_basic(my_list)
print("基础版排序后的列表:", sorted_list) # 输出: [1, 2, 2, 3, 3, 4, 8]

b. 优化版 (处理任意整数范围，包括负数)

这个版本通过引入偏移量（offset）来处理负数或不从0开始的整数范围，从而节省空间。

def counting_sort_optimized(arr):
    """
    计数排序优化版（适用于任意整数范围）
    """
    if len(arr) <= 1:
        return arr

    # 1. 找到最大值和最小值以确定范围
    max_val = max(arr)
    min_val = min(arr)
    
    # 2. 创建计数数组，大小为 (max - min + 1)
    #    offset 用于将原始数值映射到计数数组的索引 (0, 1, 2...)
    offset = min_val
    count_arr_size = max_val - min_val + 1
    count_arr = [0] * count_arr_size
    
    # 3. 填充计数数组
    for num in arr:
        count_arr[num - offset] += 1
        
    # 4. 计算累加和
    for i in range(1, count_arr_size):
        count_arr[i] += count_arr[i-1]
        
    # 5. 创建输出数组并放置元素
    output_arr = [0] * len(arr)
    for num in reversed(arr):
        position = count_arr[num - offset] - 1
        output_arr[position] = num
        count_arr[num - offset] -= 1
        
    return output_arr

# --- 示例 ---
my_list_neg = [-5, 5, -9, 1, 10, 0, 1]
sorted_list_neg = counting_sort_optimized(my_list_neg)
print("优化版排序后的列表:", sorted_list_neg) # 输出: [-9, -5, 0, 1, 1, 5, 10]

4. 算法分析

时间复杂度: O(n + k)
- n 是待排序数组的元素个数。
- k 是整数的范围（即 max_val - min_val + 1）。
- 整个过程包括几次对大小为 n 或 k 的数组的线性扫描，所以是 O(n + k)。
- 当 k 的大小与 n 相当或更小时（k = O(n)），时间复杂度可以看作是线性时间 O(n)，这比任何基于比较的排序算法 O(n log n) 都要快。
空间复杂度: O(n + k)
- 需要一个大小为 k 的 count_arr 和一个大小为 n 的 output_arr。
稳定性: 计数排序是稳定的，前提是正确实现（即在构建输出数组时反向遍历原始数组）。

5. 小结

优点:

速度极快：在特定条件下，它是最快的排序算法之一。
稳定性：是一种稳定的排序算法。

缺点:

适用范围窄：只能用于整数排序。
空间浪费：当整数范围 k 远大于元素数量 n 时（例如，排序 [1, 10, 1000000]），会造成巨大的空间浪费，此时性能会急剧下降。

因此，计数排序是一种非常特殊的、在特定场景下极为高效的算法，常被用作更复杂算法（如基数排序）的子过程。

九、总结

1. 主流排序算法综合对比表

特性 / 算法	冒泡排序 (Bubble)	选择排序 (Selection)	插入排序 (Insertion)	希尔排序 (Shell)	归并排序 (Merge)	快速排序 (Quick)	堆排序 (Heap)	计数排序 (Counting)
时间复杂度 (平均)	O(n²)	O(n²)	O(n²)	O(n log n) ~ O(n²) ¹	O(n log n)	O(n log n)	O(n log n)	O(n + k) ²
时间复杂度 (最坏)	O(n²)	O(n²)	O(n²)	O(n²) (取决于增量)	O(n log n)	O(n²) (需优化避免)	O(n log n)	O(n + k)
时间复杂度 (最好)	O(n) (优化后)	O(n²)	O(n)	O(n log n)	O(n log n)	O(n log n)	O(n log n)	O(n + k)
空间复杂度	O(1)	O(1)	O(1)	O(1)	O(n)	O(log n) (平均)	O(1)	O(n + k)
稳定性	稳定	不稳定	稳定	不稳定	稳定	不稳定	不稳定	稳定
排序方式	In-place (原地)	In-place (原地)	In-place (原地)	In-place (原地)	Out-of-place (非原地)	In-place (原地)	In-place (原地)	Out-of-place (非原地)
算法类型	比较排序	比较排序	比较排序	比较排序	比较排序 (分治)	比较排序 (分治)	比较排序 (选择)	非比较排序
核心思想	相邻元素比较交换，最大值“冒泡”到末尾	每次从未排序部分找最小元素放到已排序末尾	将元素插入到已排序序列的正确位置	分组的插入排序，逐步缩小增量	分解成小数组，排序后合并	选定基准，分区后递归排序	构建最大堆，将堆顶与末尾交换并调整	统计每个元素出现的次数来确定位置
主要优点	实现简单，易于理解	实现简单，交换次数少	对小规模或几乎有序的数据效率高	比 O(n²) 算法快，且为原地排序	性能极为稳定，适用于链表和外部排序	平均速度最快，常数因子小，原地排序	保证 O(n log n) 最坏性能且为原地排序	速度极快，可达线性时间
主要缺点	效率极低，实际中不使用	效率极低，无法利用数据初始顺序	对大规模乱序数据效率低	性能依赖增量序列，不稳定	需要 O(n) 额外空间	最坏情况性能差 (O(n²))，不稳定	实际平均性能常数因子大于快速排序，不稳定	适用范围窄 (整数且范围k不能太大)，空间开销大
适用场景	教学演示	教学演示，或当数据交换成本极高时	数据量小，或数据基本有序	中等规模数据集，对内存要求严格	内存充裕，需要稳定排序或处理外部数据	通用场景，大多数情况下的首选	需要可靠性能保证和低空间占用的场景	整数排序，且数据范围 k 不比 n 大很多

2. 表格注解与总结

¹ 希尔排序的复杂度: 它的时间复杂度与所选的“增量序列”密切相关，分析非常复杂。虽然其最坏情况是 O(n²)，但在良好增量序列下，其性能远超一般 O(n²) 算法，接近 O(n log n)。

² k 的含义: 在计数排序中，k 代表待排序数据中最大值与最小值之差，即 max(arr) - min(arr)。

3. 如何选择排序算法？

追求极致性能，且不要求稳定性：快速排序通常是首选。现代编程语言的内置排序函数（如 Python 的 sort()）通常是基于快速排序的变体（如 IntroSort）或结合了多种排序思想的混合算法（如 Timsort）。
需要稳定的排序结果：归并排序是最佳选择。例如，当你需要按多个字段排序时（先按年龄排，年龄相同时保持原始顺序），稳定性至关重要。
关心最坏情况的性能和内存占用：堆排序能提供 O(n log n) 的最坏情况时间保证和 O(1) 的空间复杂度，非常可靠。
数据规模非常小，或基本有序：插入排序的简单性和高效性使其成为理想选择。这也是 Timsort 等高级算法在处理小数据块时会切换到插入排序的原因。
排序的是整数且范围不大：计数排序可以提供无与伦比的线性时间性能。它是基数排序等更复杂算法的基础。
教学或理解算法思想：冒泡排序和选择排序虽然效率低下，但它们的逻辑简单直观，是学习排序算法的绝佳起点。