1. 排序的基本概念与应用

1.1 排序的定义

排序：指将一组记录按照某个或多个关键字的大小关系，进行递增或递减排列的操作过程。

稳定性：若在排序前后，相同关键字元素的相对位置保持不变，则称该排序算法具备稳定性。

内部排序：所有数据元素均存储于内存中完成的排序操作。

外部排序：当数据量过大无法全部载入内存时，需在排序过程中频繁进行内外存之间的数据交换，这类排序称为外部排序。

1.2 排序的实际应用场景

1.3 常见排序算法概览

以下为各排序算法的动态演示效果所对应的接口实现：

// 向下调整堆结构
void AdjustDown(int *a, int n, int parent);

// 堆排序
void HPSort(int *a, int n);

// 直接插入排序
void InsertSort(int *a, int n);

// 希尔排序
void ShellSort(int *a, int n);

// 选择排序
void SelectSort(int *a, int n);

// 快速排序——霍尔分区法
int QSPart1(int *a, int left, int right);

// 快速排序——前后指针法（效率略低于霍尔法）
int QSPart2(int *a, int left, int right);

// 标准快速排序
void QuickSort(int *a, int left, int right);

// 非递归形式的快速排序
void QuickSortNonr(int *a, int left, int right);

// 冒泡排序
void BubbleSort(int *a, int n);

// 归并排序辅助函数
void _MergeSort(int *a, int *tmp, int left, int right);

// 归并排序主函数
void MergeSort(int *a, int n);

// 非递归版本归并排序
void MergeSortNonr(int *a, int n);

// 计数排序
void CountSort(int *a, int n);

2. 主要排序算法的实现原理

2.1 插入类排序方法

2.1.1 算法思想解析

直接插入排序是一种直观且基础的排序方式。其核心思想是：

将待排序的数据逐个插入到一个已经有序的序列中，每插入一个元素都维持新序列的有序性，直至所有元素处理完毕，最终形成完整的有序序列。

这一过程类似于日常打扑克牌时理牌的方式，玩家每次拿到一张新牌后会将其插入到手中已排好序的牌中的合适位置。

2.1.2 直接插入排序的具体实现

当处理第 i 个元素（i ≥ 0）时，前 i 个元素 array[0] 到 array[i-1] 已经有序。此时取出 array[i+1] 的值，从后往前依次比较，并将大于该值的元素向后移动，直到找到合适的插入位置。

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

直接插入排序特性总结：

1. 初始序列越接近有序，算法执行效率越高；
2. 时间复杂度为 O(N)；
3. 空间复杂度为 O(1)，属于原地排序；
4. 是一种稳定的排序算法。

2.1.3 希尔排序（增量递减排序）

希尔排序又称为“缩小增量排序”，是对直接插入排序的优化改进。

基本思路如下：

首先设定一个初始增量 gap，将整个序列划分为若干子序列，每个子序列由相距为 gap 的元素组成。对每个子序列分别进行直接插入排序。随后逐步缩小 gap 值，重复上述分组和排序过程。当 gap 减小至 1 时，整个序列再次进行一次直接插入排序，此时由于前期预排序的作用，整体数据已较为有序，因此效率较高。

// 希尔排序实现（包含预排序和最终插入排序）
// 时间复杂度约为 O(N^1.3)
void ShellSort(int *a, int n) {
    // 方法一：按组分别排序
    /*
    int gap = 3;
    for (int j = 0; j < gap; j++) {
        for (int i = j; i < n - gap; i += gap) {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0) {
                if (tmp < a[end]) {
                    a[end + gap] = a[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
    */
    // 方法二：多组同时进行预排序，互不影响
}

3. 排序算法的时间复杂度与稳定性分析

本节主要讨论不同排序算法在运行效率和稳定性方面的表现差异，帮助根据实际场景选择合适的排序策略。常见指标包括：

• 时间复杂度：反映算法执行时间随输入规模增长的趋势；
• 空间复杂度：衡量额外内存使用情况；
• 稳定性：判断相同元素是否能保持原有顺序。

这些因素共同决定了某一算法在特定环境下的适用性。

// 最终版本的希尔排序实现，通过动态控制 gap 实现预排序与直接插入排序的结合
int gap = n;
while (gap > 1) {
    gap = gap / 3 + 1;  // 当 gap > 1 时进行预排序，当 gap == 1 时执行最后一次直接插入排序
    for (int i = 0; i < n - gap; i++) {  // 每次处理 gap 组数据，实现并行排序逻辑
        int end = i;
        int tmp = a[end + gap];
        while (end >= 0) {
            if (tmp < a[end]) {
                a[end + gap] = a[end];
                end -= gap;
            } else {
                break;
            }
        }
        a[end + gap] = tmp;
    }
}


希尔排序的特点归纳如下：
1. 希尔排序是基于直接插入排序的一种改进算法，利用分组插入的思想提升效率。
2. 在 gap 大于 1 的阶段，主要作用是预排序，使整个数组逐渐趋于有序；当 gap 减小至 1 时，数组已接近有序状态，此时再进行一次插入排序，效率显著提高。
3. 时间复杂度约为 O(N^1.3)，优于普通插入排序的 O(N)。
4. 排序过程不稳定，属于不稳定的排序算法。

2.2 选择排序

2.2.1 基本原理
在未排序的数据序列中，反复查找最小（或最大）的关键元素，并将其放置到当前待排序区间的起始位置。重复此过程，直到所有元素都被安排到位。

2.2.2 直接选择排序
- 在区间 array[i] 到 array[n-1] 中找出关键码最小（或最大）的元素。
- 若该元素不在当前区间的首位（或末位），则将其与首元素（或尾元素）交换。
- 对剩余子区间 array[i+1] 到 array[n-2] 重复上述操作，直至区间仅剩一个元素。

// 优化版选择排序：每轮同时选出最大值和最小值
void SelectSort(int *a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int maxi = begin, mini = begin;
        // 遍历当前区间，定位最大值和最小值的索引
        for (int i = begin + 1; i <= end; i++) {
            if (a[i] > a[maxi]) maxi = i;
            if (a[i] < a[mini]) mini = i;
        }

        // 将最小值交换至区间开头
        swap(a[begin], a[mini]);

        // 如果最大值原本位于 begin 位置，由于上一步交换已被影响，需更新其索引
        if (maxi == begin)
            maxi = mini;

        // 将最大值交换至区间末尾
        swap(a[end], a[maxi]);

        // 缩小排序范围
        begin++;
        end--;
    }
}

直接选择排序特性总结：
1. 算法逻辑清晰、易于理解，但运行效率较低，在实际工程中极少使用。
2. 时间复杂度恒为 O(N)，无论数据初始状态如何。
3. 空间复杂度为 O(1)，属于原地排序算法。
4. 不具备稳定性，例如在序列 6 6 1 6 中，相同元素的相对顺序可能被改变。

2.2.3 堆排序
堆排序是一种基于堆结构的选择排序变体。它利用堆的性质（父节点大于等于或小于等于子节点）来高效选出极值元素，从而完成排序任务。  
注意：若要升序排列，则构建大根堆；若要降序排列，则构建小根堆。

// 向上调整函数 —— 用于建堆过程中将新元素插入堆底后恢复堆结构
void AdjustUp(int *a, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {  // 调整至根节点或满足堆序性为止
        if (a[parent] < a[child]) {  // 大根堆条件
            swap(a[parent], a[child]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

// 向下调整函数 —— 常用于堆顶元素移除后恢复堆结构
void AdjustDown(int *a, int n, int parent) {
    int child = parent * 2 + 1;  // 默认左孩子为较大者
    while (child < n) {
        // 存在右孩子且右孩子更大时，选择右孩子
        if (child + 1 < n && a[child + 1] > a[child])
            child++;

        if (a[child] > a[parent]) {  // 大根堆调整
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 堆排序主函数
void HPSort(int *a, int n) {
    // 使用向下调整方式建堆，时间复杂度为 O(N logN)
}

// 向下调整，时间复杂度为 O(N)，从最后一个非叶子节点开始处理
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    AdjustDown(a, n, i);

// 整体时间复杂度：O(N*logN)
int end = n - 1;
while (end) {
    swap(a[0], a[end]);
    AdjustDown(a, end, 0); // 在向下调整过程中，child 不会等于 end
    --end;
}

// 堆排序的特点归纳如下：
// 1. 利用堆结构进行元素选择，排序效率较高  
// 2. 时间复杂度稳定在 O(N log N)
// 3. 空间复杂度为 O(1)，属于原地排序算法
// 4. 排序过程不具备稳定性

2.3 交换排序
核心思想：通过比较序列中两个记录的键值大小，根据结果交换其位置。此类排序方式的典型特征是：较大的键值逐步向序列尾部移动，较小的则向前部移动。

2.3.1 冒泡排序
实现代码如下：
void Bubble(int *a, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j + 1 < n; j++) {
            if (a[j] > a[j+1]) {
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
}

冒泡排序特性总结：

    
逻辑清晰，易于理解和实现
    
时间复杂度为 O(N)
    
空间复杂度为 O(1)
    
具备排序稳定性


2.3.2 快速排序
快速排序由 Hoare 于 1962 年提出，是一种基于二叉树思想的交换类排序方法。基本思路为：从待排序列中选取一个基准元素（pivot），将剩余元素划分为两个子序列——左侧所有元素均小于该基准，右侧均大于它。随后对这两个子序列递归执行相同操作，直至整个序列有序。

void QuickSort(int *a, int left, int right) {
    if (left >= right) return;
    int keyi = QSPart1(a, left, right);
    QuickSort(a, left, keyi - 1);  // 处理左半部分
    QuickSort(a, keyi + 1, right); // 处理右半部分
}

1. Hoare 法（霍尔法）


实现细节如下：
int QSPart1(int *a, int left, int right) {
    // 使用三数取中策略选择基准点
    int keyi = GetMidl(a, left, right);
    swap(a[left], a[keyi]); // 将选中的基准放到最左边
    int begin = left, end = right;

    while (begin < end) {
        // 右侧先出发，寻找比基准小的元素
        while (begin < end && a[end] >= a[keyi])
            --end;
        // 左侧再出发，寻找比基准大的元素
        while (begin < end && a[begin] <= a[keyi])
            ++begin;
        // 找到后交换
        swap(a[begin], a[end]);
    }
    // 最终将基准元素归位
    swap(a[keyi], a[begin]);
    return begin; // 返回分割点，此时左小右大
}

2. 挖坑法


3. 前后指针法


前后指针法实现如下（相比霍尔法效率略低）：
int QSPart2(int *a, int left, int right) {
    int prev = left, cur = prev + 1;
    int keyi = GetMidl(a, left, right);
    swap(a[left], a[keyi]); // 将中间值作为基准并置于首位

    while (cur < right) {
        if (a[cur] < a[keyi] && ++prev != cur)
            swap(a[cur], a[prev]);
        cur++;
    }
    swap(a[prev], a[keyi]);
    return prev; // 返回基准最终所在位置
}

2.3.3 快速排序优化策略（面试时可只讲思路）

    
三数取中法选取基准：避免极端情况下（如已排序序列）导致性能退化为 O(N)，从首、尾、中三个位置取中间值作为 pivot。
    
小区间优化：当递归进入较小的子区间时，继续使用递归开销较大，可改用插入排序提升效率。


// 三数取中函数实现
int GetMidl(int *a, int left, int right) {
    int mid = (left + right) / 2;
    if (a[left] < a[mid]) {
        if (a[mid] < a[right]) {
            return mid;
        }
    }

// 快速排序的优化与实现

// 三数取中法选择基准值
int MidNumIndex(int *a, int left, int right) {
    int mid = (left + right) / 2;
    if (a[left] > a[mid]) {
        if (a[mid] > a[right])
            return mid;
        else if (a[left] < a[right])
            return left;
        else
            return right;
    } else {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] < a[right])
            return right;
        else
            return left;
    }
}

// 第一种分区方式（以最右元素为基准）
int QSPart1(int *a, int left, int right) {
    int midi = MidNumIndex(a, left, right);
    Swap(&a[midi], &a[right]);  // 将中间值放到末尾作为基准

    int key = a[right];
    int begin = left, end = right;

    while (begin < end) {
        while (begin < end && a[begin] <= key)
            begin++;
        while (begin < end && a[end] >= key)
            end--;

        if (begin < end)
            Swap(&a[begin], &a[end]);
    }
    Swap(&a[begin], &a[right]);
    return begin;
}

// 递归版快速排序
// 当区间较小时采用插入排序进行优化，提升效率
void QuickSort(int *a, int left, int right) {
    if (left >= right) return;

    // 小数据量时使用插入排序减少递归开销
    if (right - left < 10) {
        InsertSort(a + left, right - left + 1);
    } else {
        int keyi = QSPart1(a, left, right);

        // 分别对左右子区间递归排序
        QuickSort(a, left, keyi - 1);
        QuickSort(a, keyi + 1, right);
    }
}



// 非递归版本的快速排序
// 利用栈模拟递归过程，避免深度递归带来的栈溢出问题
void QuickSortNonr(int *a, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);

    while (!STEmpty(&st)) {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);

        int keyi = QSPart1(a, begin, end);

        // 先压入右半部分，再压入左半部分（后进先出）
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (keyi - 1 > begin) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }

    STDestory(&st);
}

// 快速排序特性总结
1. 综合性能优秀，实际应用广泛  
2. 时间复杂度：O(N log N)，最坏情况下为 O(N)，但通过随机化或三数取中可有效避免  
3. 空间复杂度：O(log N)，主要来自递归调用栈或显式栈  
4. 排序稳定性：不稳定  

2.4 归并排序

2.4.1 基本思想
归并排序是一种基于“分治法”的高效排序算法，其核心操作是“归并”，即将两个已有序的序列合并成一个有序序列。该算法首先将原始序列不断分割为更小的子序列，直到每个子序列只有一个元素；然后逐层向上合并，最终形成完全有序的整体序列。若每次合并两个子序列，则称为二路归并。



// 递归实现归并排序的辅助函数
// 使用临时数组 tmp 存储合并结果，并复制回原数组
void _MergeSort(int *a, int *tmp, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;

    // 分别对左右两部分进行归并排序
    _MergeSort(a, tmp, left, mid);
    _MergeSort(a, tmp, mid + 1, right);

    // 设置双指针遍历两个有序段
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;

    // 合并两个有序段到临时数组
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] <= a[begin2])
            tmp[index++] = a[begin1++];
        else
            tmp[index++] = a[begin2++];
    }

    // 处理剩余未合并的元素
    while (begin1 <= end1)
        tmp[index++] = a[begin1++];

    while (begin2 <= end2)
        tmp[index++] = a[begin2++];

    // 将合并结果从临时数组拷贝回原数组
    memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

// 主函数：归并排序入口
// 时间复杂度稳定为 O(N log N)
void MergeSort(int *a, int n) {
    int *tmp = (int *)malloc(sizeof(int) * n);
    if (!tmp) {
        perror("malloc fail");
        return;
    }

    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
    tmp = NULL;
}

2.4.2 非递归版归并排序
// 使用迭代方式实现归并排序，避免递归带来的函数调用开销
void MergeSortNonr(int *a, int n) {
    int *tmp = (int *)malloc(sizeof(int) * n);
    if (!tmp) {

// 动态内存分配失败处理
if (tmp == NULL) {
    perror("malloc fail");
    return;
}

// 初始化每组归并元素的间隔
int gap = 1;
while (gap < n) {
    // 对每一对相邻子序列进行归并操作
    for (int i = 0; i < n; i += 2 * gap) {
        int begin1 = i, end1 = i + gap - 1;
        int begin2 = i + gap, end2 = i + 2 * gap - 1;

        // 定义两个区间：[begin1, end1] 和 [begin2, end2]
        // 处理三种越界情况：
        // 1. 仅 end2 越界
        // 2. begin2 和 end2 均越界
        // 3. end1、begin2、end2 都越界

        // 若第二组起始位置已越界，无需继续
        if (begin2 >= n) break;

        // 若第二组结束位置越界，修正为数组末尾
        if (end2 >= n) end2 = n - 1;

        int j = i;
        // 将两组数据按序合并至临时数组 tmp
        while (begin1 <= end1 && begin2 <= end2) {
            if (a[begin1] < a[begin2]) 
                tmp[j++] = a[begin1++];
            else 
                tmp[j++] = a[begin2++];
        }

        // 将剩余未处理的数据依次复制到 tmp
        while (begin1 <= end1) 
            tmp[j++] = a[begin1++];

        while (begin2 <= end2) 
            tmp[j++] = a[begin2++];
        
        // 将本次归并结果拷贝回原数组对应位置
        memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    // 每轮后归并间隔翻倍
    gap *= 2;
}

// 释放临时空间
free(tmp);
tmp = NULL;

归并排序特性归纳：

1. 主要不足在于需额外开辟 O(N) 的存储空间；其设计思想常被应用于磁盘外排序场景中。
2. 时间复杂度为：O(N log N)，在各类情况下表现稳定。
3. 空间复杂度为：O(N)，受限于辅助数组的使用。
4. 具备稳定性，相同值的相对顺序不会改变。

2.5 非比较类排序方法

计数排序基于“鸽巢原理”，可视为哈希直接定址法的一种变体应用，体现桶排序的基本思想。其核心步骤包括：

• 统计待排序列中各元素出现的频次。
• 依据统计信息，将元素重新放回原数组完成排序。

// 计数排序实现函数
void CountSort(int* a, int n) {
    // 确定数据极值以缩小空间开销
    int max = a[0], min = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }

    // 计算所需辅助空间大小
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (count == NULL) {
        perror("calloc fail");
        return;
    }

    // 利用偏移量实现相对映射，减少内存浪费
    for (int i = 0; i < n; ++i) {
        count[a[i] - min]++;
    }

    // 回收排序结果至原数组
    int j = 0;
    for (int i = 0; i < range; ++i) {
        while (count[i]--) {
            a[j++] = i + min;
        }
    }

    // 释放动态分配内存
    free(count);
}

计数排序特点总结：

1. 当输入数据分布集中、范围较小时，效率极高；但适用条件较为严格，通用性较差。
2. 时间复杂度为：O(N + range)，其中 range 表示数值跨度。
3. 空间复杂度为：O(range)，取决于最大与最小值之差。
4. 排序过程保持元素间的相对顺序，具有良好的稳定性。

常见排序算法的时间复杂度与稳定性对比