八大经典排序算法原理与代码实现

1. 排序

排序算法是计算机科学中最基础的技能之一，理解这些算法能显著提升代码效率。本文将带你快速掌握七大经典排序算法的核心原理与实现。

1.1 排序概念及其运用

排序是指将一组数据按照特定规则（如升序或降序）重新排列的过程。排序广泛用于优化数据检索、提高算法效率以及简化复杂问题的处理。

排序的主要应用场景

1. 数据库查询：加速数据检索（如索引排序）。
2. 搜索算法：二分查找要求数据有序。
3. 数据分析：统计、去重、Top-K 问题（如排行榜）。
4. 任务调度：按优先级处理任务。
5. 文件系统：按文件名、日期排序文件。

1.2 常见排序算法

本次将系统介绍多种经典排序算法，重点从时间复杂度、空间复杂度、稳定性三个维度展开分析。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。

2. 插入排序

插入排序的基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止。

2.1 直接插入排序

直接插入排序的思想是：当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置将 array[i] 插入，原来位置上的元素顺序后移。

动图：

实现代码：

// 直接插入排序算法实现
// 参数说明：
// arr - 待排序数组首地址
// n - 数组元素个数
// 特性：
// - 时间复杂度：O(n²)（最优 O(n)）
// - 空间复杂度：O(1)
// - 稳定排序
void InsertSort(int* arr, int n) {
    // 外层循环：遍历未排序元素（从第二个元素开始）
    for (int i = 0; i < n - ; i++) {
        
         end = i;
        
         temp = arr[end + ];
        
         (end >= ) {
             (arr[end] > temp) {
                arr[end + ] = arr[end];
                end--;
            }  {
                ;
            }
        }
        arr[end + ] = temp;
    }
}