1. 排序算法总结

一、排序算法概述

排序算法是将一组数据按照特定的顺序进行排列的方法。在计算机科学中，排序算法有着广泛的应用，如数据库查询、数据处理、图形学等领域。不同的排序算法具有不同的时间复杂度、空间复杂度和稳定性等特点。

常见的排序算法可以分为以下几类：

1. 简单排序算法：包括冒泡排序、插入排序和选择排序。这些算法的实现相对简单，但效率较低，时间复杂度通常为 O(n²)。
2. 高效排序算法：如快速排序、归并排序和堆排序。这些算法的时间复杂度为 O(n log n)，在处理大规模数据时效率较高。
3. 其他排序算法：还有一些特殊的排序算法，如计数排序、桶排序和基数排序等，它们适用于特定的数据类型和场景。

二、排序算法的重要概念

1. 稳定性：如果在排序过程中，相等元素的相对顺序保持不变，则称该排序算法是稳定的；否则，是不稳定的。
2. 时间复杂度：衡量排序算法执行时间的指标，通常用大 O 符号表示。时间复杂度越低，算法执行速度越快。
3. 空间复杂度：衡量排序算法所需额外空间的指标。空间复杂度越低，算法所需的内存空间越少。

三、常见排序算法的特点比较

排序算法	时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(1)	稳定
插入排序	O(n²)	O(1)	稳定
选择排序	O(n²)	O(1)	不稳定
快速排序	O(n log n)（平均情况），O(n²)（最坏情况）	O(log n)（递归调用栈空间）	不稳定
归并排序	O(n log n)	O(n)（辅助数组空间）	稳定
堆排序	O(n log n)	O(1)（如果不考虑堆数据结构占用的空间）	不稳定

在实际应用中，应根据数据规模、数据特点和性能要求等因素选择合适的排序算法。对于小规模数据，简单排序算法可能足够高效；对于大规模数据，高效排序算法通常更适合。

2. 简单排序算法

一、冒泡排序

1. 通俗介绍：

   • 想象有一排高矮不齐的小朋友，我们要让他们从矮到高排队。从第一个小朋友开始，依次比较相邻的两个小朋友，如果前面的比后面的高，就交换他们的位置。这样一遍一遍地比较和交换，就像水里的泡泡一样，小的泡泡往上冒，大的泡泡往下沉，最后所有的小朋友就按身高排好队了。

2. 术语介绍：

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

3. Python 代码实现及注释：

def bubble_sort(arr):
    n = len(arr)
    # 外层循环控制排序的轮数，一共进行 n-1 轮
    for i in range(n - 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]
    return arr

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> bubbleSort(std::vector<int> arr) {
    int n = arr.size();
    // 外层循环控制排序的轮数，一共进行 n-1 轮
    for (int i = 0; i < n - 1; i++) {
        // 内层循环控制每一轮的比较和交换，每一轮都会把当前最大的元素移到最后
        for (int j = 0; j < n - i - 1; j++) {
            // 如果当前元素比下一个元素大，就交换它们的位置
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

5. 总结：
   • 优点：
     • 实现简单，容易理解。
     • 对于小规模数据的排序比较直观。
   • 缺点：
     • 时间复杂度较高，为 O(n²)，当数据规模较大时，排序速度非常慢。
   • 应用场景前提：
     • 适用于数据规模较小的情况。
     • 对算法效率要求不高，或者作为教学示例。

二、插入排序

1. 通俗介绍：

   • 就像我们玩扑克牌时整理手牌一样。从没有排序的牌中依次取出一张，插入到已经排好序的牌中的合适位置，使得插入后的牌依然是有序的。一开始只有一张牌是有序的，然后逐渐把其他牌插入到合适的位置，最后所有的牌就都排好序了。

2. 术语介绍：

   • 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3. Python 代码实现及注释：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        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

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> insertionSort(std::vector<int> arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 将 arr[i] 插入到前面已排序的序列中的合适位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

5. 总结：
   • 优点：
     • 对于接近有序的数组，插入排序非常高效，时间复杂度接近 O(n)。
     • 实现简单，代码量小。
   • 缺点：
     • 对于大规模乱序数据，时间复杂度为 O(n²)，效率较低。
   • 应用场景前提：
     • 数据量较小且部分有序的情况。
     • 对于频繁插入操作且希望保持整体有序的场景，如在线数据处理。

三、选择排序

1. 通俗介绍：

   • 想象有一群学生站成一排，我们要按照身高给他们排队。首先从这群学生中找到最矮的那个学生，把他放到第一位。然后在剩下的学生中继续找最矮的，放到第二位。这样依次进行，直到所有学生都排好序。

2. 术语介绍：

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

3. 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

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> selectionSort(std::vector<int> arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        int min_idx = i;
        // 找到未排序部分中的最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将最小元素与未排序部分的第一个元素交换位置
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
    return arr;
}

5. 总结：
   • 优点：
     • 实现简单，代码易于理解。
     • 交换次数相对较少，在某些情况下可能比冒泡排序更高效。
   • 缺点：
     • 时间复杂度为 O(n²)，效率较低。
     • 不稳定排序算法，在某些需要稳定性的场景不适用。
   • 应用场景前提：
     • 数据量较小且对算法效率要求不高的情况。
     • 当需要简单直观的排序算法且不关心稳定性时可以使用。

3. 高效排序算法

一、快速排序

1. 通俗介绍：

   • 快速排序就像整理书架。首先从书架中随便挑出一本书作为基准，把书架上其他的书分成两堆，一堆是比这本书矮的，放在基准书的左边；一堆是比这本书高的，放在基准书的右边。然后分别对这两堆书重复这个过程，直到所有的书都排好序。

2. 术语介绍：

   • 快速排序是一种分治算法。它通过选取一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的元素都小于基准元素，另一个子序列的元素都大于基准元素。然后对这两个子序列分别进行递归排序，最终得到有序序列。

3. Python 代码实现及注释：

def quick_sort(arr):
    # 如果数组长度小于等于 1，说明已经有序，直接返回
    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)

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> quickSort(std::vector<int> arr) {
    // 如果数组长度小于等于 1，说明已经有序，直接返回
    if (arr.size() <= 1) {
        return arr;
    }
    // 选取中间元素作为基准
    int pivot = arr[arr.size() / 2];
    // 创建三个向量分别用于存储小于、等于、大于基准的元素
    std::vector<int> left, middle, right;
    for (int x : arr) {
        // 如果元素小于基准，放入 left 向量
        if (x < pivot) {
            left.push_back(x);
        } else if (x == pivot) {
            // 如果元素等于基准，放入 middle 向量
            middle.push_back(x);
        } else {
            // 如果元素大于基准，放入 right 向量
            right.push_back(x);
        }
    }
    // 对小于基准的子向量递归调用快速排序
    left = quickSort(left);
    // 对大于基准的子向量递归调用快速排序
    right = quickSort(right);
    // 创建结果向量
    std::vector<int> result;
    // 预留足够的空间，避免频繁重新分配内存
    result.reserve(left.size() + middle.size() + right.size());
    // 将小于基准的子向量的元素插入结果向量
    result.insert(result.end(), left.begin(), left.end());
    // 将等于基准的子向量的元素插入结果向量
    result.insert(result.end(), middle.begin(), middle.end());
    // 将大于基准的子向量的元素插入结果向量
    result.insert(result.end(), right.begin(), right.end());
    // 返回排序后的结果向量
    return result;
}

5. 总结：
   • 优点：
     • 平均情况下时间复杂度为 O(n log n)，效率较高。
     • 原地排序算法，不需要额外的大量空间。
   • 缺点：
     • 最坏情况下时间复杂度为 O(n²)，当选取的基准元素不好时可能会导致性能下降。
     • 不稳定排序算法。
   • 应用场景前提：
     • 数据规模较大时表现良好。
     • 对稳定性要求不高的场景。

快速排序被认为是一种原地排序算法（在某些实现中），是因为它可以通过在原数组上进行交换操作来实现排序，而不需要创建与输入规模成比例的额外数组空间。例如，可以通过以下方式实现原地快速排序：

def partition(arr, low, high):
    # 选取最后一个元素作为基准
    pivot = arr[high]
    # i 初始化为 low - 1，用于标记小于基准的元素的边界
    i = low - 1
    for j in range(low, high):
        # 如果当前元素小于基准
        if arr[j] < pivot:
            # i 向后移动一位
            i += 1
            # 交换 arr[i] 和 arr[j]，将小于基准的元素移到前面
            arr[i], arr[j] = arr[j], arr[i]
    # 交换 arr[i + 1] 和 arr[high]，将基准放到正确的位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickSortInPlace(arr, low, high):
    if low < high:
        # 划分操作，得到基准的正确位置
        pivotIndex = partition(arr, low, high)
        # 对左半部分递归排序
        quickSortInPlace(arr, low, pivotIndex - 1)
        # 对右半部分递归排序
        quickSortInPlace(arr, pivotIndex + 1, high)

快速排序在原数组上进行划分和交换操作，实现了原地快速排序。它只需要少量的额外空间用于递归调用的栈空间，而不需要创建与输入规模成比例的额外数组空间。

二、归并排序

1. 通俗介绍：

   • 归并排序就像是玩拼图游戏。我们把一堆混乱的拼图碎片分成两堆，分别对这两堆进行整理，让它们各自变得有序。然后再把这两堆有序的碎片合并起来，就得到了一个完整有序的拼图。

2. 术语介绍：

   • 归并排序是一种分治算法。它将待排序序列分成若干个子序列，分别对每个子序列进行排序，然后将已排序的子序列合并成一个有序的序列。

3. Python 代码实现及注释：

def merge_sort(arr):
    # 如果数组长度小于等于 1，说明已经有序，直接返回
    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

算法思想：归并排序采用分治的思想。首先将数组不断地分成两半，直到每个子数组只有一个或零个元素，这时子数组必然是有序的。然后再将这些有序的子数组合并起来，在合并的过程中，比较两个子数组的当前元素，将较小的元素放入结果数组中，直到其中一个子数组的元素全部被处理完，再将另一个子数组的剩余元素添加到结果数组中。这样就得到了一个有序的数组。
4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> merge(std::vector<int> left, std::vector<int> right) {
    std::vector<int> result;
    int i = 0, j = 0;
    // 当左右两个子数组都还有元素时
    while (i < left.size() && j < right.size()) {
        // 如果左子数组的当前元素小于右子数组的当前元素
        if (left[i] < right[j]) {
            result.push_back(left[i]);
            i++;
        } else {
            result.push_back(right[j]);
            j++;
        }
    }
    // 如果左子数组还有剩余元素，将其添加到结果数组中
    while (i < left.size()) {
        result.push_back(left[i]);
        i++;
    }
    // 如果右子数组还有剩余元素，将其添加到结果数组中
    while (j < right.size()) {
        result.push_back(right[j]);
        j++;
    }
    return result;
}

std::vector<int> mergeSort(std::vector<int> arr) {
    // 如果数组长度小于等于 1，说明已经有序，直接返回
    if (arr.size() <= 1) {
        return arr;
    }
    int mid = arr.size() / 2;
    // 创建左子数组，包含从开始到中间的元素
    std::vector<int> left(arr.begin(), arr.begin() + mid);
    // 创建右子数组，包含从中间到结束的元素
    std::vector<int> right(arr.begin() + mid, arr.end());
    // 对左子数组进行归并排序
    left = mergeSort(left);
    // 对右子数组进行归并排序
    right = mergeSort(right);
    // 合并左右两个已排序的子数组
    return merge(left, right);
}

算法思想：与 Python 代码类似，C++ 版本的归并排序也采用分治思想。首先将输入的数组分成左右两个子数组，然后对这两个子数组分别进行归并排序，得到两个有序的子数组。接着，通过比较两个子数组的元素，将它们合并成一个有序的数组。这个过程不断递归进行，直到子数组的长度为 1 或 0，此时子数组已经有序。最后，将所有子数组合并起来，得到最终的有序数组。

5. 总结：
   • 优点：
     • 时间复杂度稳定为 O(n log n)，无论在最好、最坏还是平均情况下都是如此。
     • 稳定的排序算法，相等元素的相对顺序不会改变。
   • 缺点：
     • 需要额外的空间来存储合并过程中的临时数组，空间复杂度为 O(n)。
   • 应用场景前提：
     • 对稳定性有要求的场景。
     • 数据规模较大且对时间复杂度要求较高的情况。

三、堆排序

1. 通俗介绍：

   • 想象有一堆杂乱的苹果，我们要把它们按照大小排列好。首先把这堆苹果构建成一个特殊的“堆”结构，就像把苹果堆成一个有规则的形状。然后每次从堆中取出最大的苹果（根节点），放在一边，接着调整剩下的苹果，使其再次成为一个堆。这样重复操作，直到所有的苹果都被取出来，就得到了按大小排序的苹果。

2. 术语介绍：

   • 堆排序是利用堆这种数据结构而设计的一种排序算法。堆是一种完全二叉树，分为大顶堆和小顶堆。大顶堆的每个节点的值都大于或等于其子节点的值，小顶堆则相反。堆排序先将待排序序列构建成一个堆，然后不断地取出堆顶元素并调整堆，直到堆为空，从而实现排序。

3. Python 代码实现及注释：

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

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)

以下是对这段代码实现的heapify函数的详细解释和算法思路分析：

一、函数参数解释

• arr：待调整的数组，这个数组将被构建成一个堆。
• n：表示当前需要考虑的堆的大小，通常在堆排序的过程中会逐渐减小。
• i：表示当前需要进行调整的节点的索引。

二、算法思路

1. 确定初始最大元素：

   • 首先，将当前节点i标记为最大元素的索引largest。这是一个假设，后续会根据其左右子节点的值进行更新。

2. 比较左子节点：

   • 计算当前节点i的左子节点索引为2 * i + 1（这里假设数组索引从 0 开始）。
   • 然后检查左子节点是否存在（即左子节点索引小于n），并且左子节点的值是否大于当前假设的最大元素（即当前节点i的值）。
   • 如果满足条件，说明左子节点的值更大，将最大元素的索引更新为左子节点的索引left。

3. 比较右子节点：

   • 计算当前节点i的右子节点索引为2 * i + 2。
   • 同样检查右子节点是否存在（即右子节点索引小于n），并且右子节点的值是否大于当前的最大元素（此时可能是当前节点i或者更新后的左子节点）。
   • 如果满足条件，说明右子节点的值更大，将最大元素的索引更新为右子节点的索引right。

4. 调整堆结构：

   • 如果经过上述比较后，发现最大元素的索引不是当前节点i，说明需要调整堆结构以满足堆的性质。
   • 交换当前节点i和最大元素节点（索引为largest）的值，即arr[i], arr[largest] = arr[largest], arr[i]。
   • 由于交换后可能会破坏以最大元素节点为根的子树的堆性质，所以需要递归地对新的最大元素节点进行heapify操作，即heapify(arr, n, largest)。

三、整体作用

这个函数的主要作用是在构建堆和维护堆的性质过程中，确保以给定节点为根的子树满足堆的性质。通过不断地比较和交换节点，使得子树中的最大元素上升到根节点的位置，从而保证堆的有序性。在堆排序中，这个函数被反复调用，以逐步构建一个大顶堆或小顶堆，为后续的排序操作奠定基础。

4. C++代码实现及注释：

#include <iostream>
#include <vector>

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点存在且大于根节点
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大的不是根节点，则交换并继续调整
    if (largest!= i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 逐个取出堆顶元素并调整堆
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

5. 总结：
   • 优点：
     • 时间复杂度为 O(n log n)，在不同情况下都比较稳定。
     • 原地排序算法，不需要额外的大量空间（除了输入数组本身）。
   • 缺点：
     • 构建堆的过程相对复杂一些。
     • 不稳定排序算法。
   • 应用场景前提：
     • 对空间要求较高且数据规模较大的情况。
     • 不要求稳定性的场景。

堆排序的时间复杂度为$O(nlogn)$，原因如下：

一、构建堆的时间复杂度分析

1. 首先，构建堆的过程是从最后一个非叶子节点开始，逐步向上调整，直到根节点。
   • 对于一个包含$n$个元素的数组，最后一个非叶子节点的索引为$\lfloor n/2\rfloor -1$。
   • 从这个节点开始，对每个节点调用heapify函数进行调整，时间复杂度为$O(logn)$（因为每次调整都是从一个节点向下调整，最多需要$logn$次比较和交换操作）。
   • 一共有大约$\lfloor n/2\rfloor$个非叶子节点需要调整，所以构建堆的总时间复杂度为$O(nlogn)$（实际上更接近$O(n)$，因为每个节点调整的高度不是完全相同的$logn$，而是随着节点的位置逐渐减小）。

二、排序阶段时间复杂度分析

1. 在排序阶段，每次从堆中取出最大元素（即根节点），然后将最后一个元素移动到根节点位置，并对新的根节点调用heapify函数进行调整。
   • 每次取出最大元素并调整堆的操作时间复杂度为$O(logn)$。
   • 一共需要进行$n$次这样的操作，所以排序阶段的时间复杂度为$O(nlogn)$。

三、总体时间复杂度

1. 综合构建堆和排序阶段的时间复杂度，虽然构建堆的时间复杂度接近$O(n)$，但在大$O$表示法中，较小的项可以被忽略。
   • 所以堆排序的总体时间复杂度为$O(nlogn)$。

总之，堆排序通过巧妙地利用堆这种数据结构，在构建堆和排序过程中，虽然每个步骤的时间复杂度可能不是完全精确的$nlogn$，但在大$O$表示法的分析下，总体时间复杂度为$O(nlogn)$。

以下是一些其他常见的排序算法：

一、希尔排序

1. 通俗介绍：

   • 希尔排序就像是给一群学生分组排队。首先把学生分成几个小组，每个小组内的学生相隔一定的距离，在小组内进行简单的插入排序。然后逐渐缩小这个间隔，继续进行分组排序，直到间隔为 1，此时整个序列就基本有序了。

2. 术语介绍：

   • 希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。它通过将原始数据分成多个子序列，分别对这些子序列进行插入排序，逐步减少子序列的间隔，最终实现对整个序列的排序。

3. Python 代码实现及注释：

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

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> shellSort(std::vector<int> arr) {
    int n = arr.size();
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
    return arr;
}

5. 总结：
   • 优点：
     • 相比插入排序，希尔排序在大规模数据上效率更高。
     • 实现相对简单。
   • 缺点：
     • 不稳定排序算法。
     • 时间复杂度较难准确分析，取决于间隔序列的选择。
   • 应用场景前提：
     • 数据规模较大且对稳定性要求不高的情况。

二、计数排序

1. 通俗介绍：

   • 计数排序就像是给学生们按照身高分组计数。首先统计每个身高出现的次数，然后根据这个次数依次输出对应的身高，就得到了按身高排序的结果。

2. 术语介绍：

   • 计数排序是一种非比较型整数排序算法。它的核心思想是统计每个元素在序列中出现的次数，然后根据统计结果确定每个元素在排序后的序列中的位置。

3. Python 代码实现及注释：

def counting_sort(arr):
    if len(arr) == 0:
        return arr
    min_value = min(arr)
    max_value = max(arr)
    count_array = [0] * (max_value - min_value + 1)
    for num in arr:
        count_array[num - min_value] += 1
    sorted_arr = []
    for i, count in enumerate(count_array):
        sorted_arr.extend([i + min_value] * count)
    return sorted_arr

4. C++代码实现及注释：

#include <iostream>
#include <vector>

std::vector<int> countingSort(std::vector<int> arr) {
    if (arr.empty()) {
        return arr;
    }
    int min_value = *std::min_element(arr.begin(), arr.end());
    int max_value = *std::max_element(arr.begin(), arr.end());
    std::vector<int> count_array(max_value - min_value + 1, 0);
    for (int num : arr) {
        count_array[num - min_value]++;
    }
    std::vector<int> sorted_arr;
    for (int i = 0; i < count_array.size(); i++) {
        while (count_array[i] > 0) {
            sorted_arr.push_back(i + min_value);
            count_array[i]--;
        }
    }
    return sorted_arr;
}

5. 总结：
   • 优点：
     • 时间复杂度为$O(n+k)$，其中$n$是待排序数组的长度，$k$是数组中元素的取值范围。当$k$较小时，非常高效。
     • 稳定排序算法。
   • 缺点：
     • 只适用于整数排序，且当元素取值范围较大时，需要大量的额外空间。
   • 应用场景前提：
     • 数据范围较小的整数排序场景。