排序算法精讲：基础实现与性能分析

排序算法精讲：从理论到实践

一、排序概念及应用

1.1 基本概念

排序：将一组记录按照特定关键字（如数值大小）进行递增或递减排列的操作。

1.2 常见排序算法分类

• 简单低效型：直接插入排序、冒泡排序、选择排序
• 高效优化型：希尔排序、快速排序、归并排序、堆排序

---

二、基础排序算法实现

2.1 插入排序家族

2.1.1 直接插入排序

核心思想：将待排元素逐个插入已有序序列中。

void InsertSort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0) {
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                end--;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

我的理解（如图所示）：

特性分析：

• 接近有序时效率高
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)

2.1.2 希尔排序（优化版插入排序）

优化策略：通过分组增量（gap）预排序逐步逼近全局有序。