八种排序算法优缺点·

### 八大排序算法的优点与缺点

#### 1. 冒泡排序 Bubble Sort
冒泡排序通过重复遍历列表并逐次比较相邻元素来进行排序。每次遍历时，较大的元素会逐渐向序列末端移动。

- **优点**
- 实现简单直观。
- 对于几乎已排序的数据集表现较好，在这种情况下可以提前终止循环减少不必要的计算开销[^2]。

- **缺点**
- 平均时间复杂度较高 \(O(n^2)\)，对于大规模数据处理效率低下。
- 即使数组已经部分有序也需要完成所有轮次的扫描操作除非加入额外逻辑判断提前退出[^3]。

template <typename T>
void bubbleSort(T* arr, int size) {
    for (int i = 0; i < size; ++i) {
        bool swapped = false;
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果没有发生交换则说明已经是有序状态可以直接结束
        if (!swapped) break;
    }
}

#### 2. 插入排序 Insertion Sort
插入排序构建最终排序数组的工作原理是从第二个位置开始逐步向前查找合适的位置并将当前项插入其中。

- **优点**
- 当输入本身接近完全有序时性能极佳，能够在线性时间内完成\(O(n)\)。
- 不需要额外空间支持原地工作\[in-place\]。

- **缺点**
- 面对无序程度较高的大型数据集合其平均情况下的运行时间为平方级别\(O(n^2)\)。

#### 3. 选择排序 Selection Sort
选择排序每一轮从未排序区间选出最小值放置到已排序区间的最后面形成新的边界直至整个列表被整理完毕。

- **优点**
- 算法思路清晰易懂容易实现。
- 只需少量内存即可执行不需要辅助存储器就能完成任务[in-place sort]^[]。

- **缺点**
- 效率较低因为无论初始条件如何都需要做n*(n−1)/2次比较和最多n/2次交换动作所以整体复杂度固定为\(O(n^2)\)^[]。

#### 4. 归并排序 Merge Sort
归并排序采用分治策略将待排序表不断分割成更小子问题求解后再合并得到全局最优解的过程。

- **优点**
- 性能稳定不受原始数据影响始终维持着线性对数级的时间消耗\(O(nlogn)\)[^1]。
- 是一种稳定的排序方法意味着相同数值保持原有相对顺序不变[^4]。

- **缺点**
- 虽然理论上只需占用常量倍的空间但在实际应用中由于递归调用栈的存在使得所需临时缓冲区较大增加了额外成本。

#### 5. 快速排序 Quick Sort
快速排序同样是基于分治思想但采取了不同的划分方式即选取基准点pivot将其余元素分为小于等于大于三个子区域再分别递归处理各段落。

- **优点**
- 多数场景下速度非常快特别是当随机化版本遇到最坏情形概率很低的情况下可达到近似线性的期望时间\(O(nlogn)\)。
- 减少了不必要的元素搬移次数提高了缓存命中率从而加快访问速度。

- **缺点**
- 存在一个极端案例即逆序排列时退化至二次方级别的效能\(O(n^2)\);不过可以通过引入随机抽样机制缓解此现象的发生几率。

#### 6. 堆排序 Heap Sort
堆排序利用二叉树形结构维护最大(或最小)根节点特性以此为基础反复提取顶端元素重建剩余部分构成的新堆直到全部记录都被妥善安置为止。

- **优点**
- 同样具备较好的渐进时间界限\(O(nlogn)\),而且只需要很小一部分附加资源用于管理内部索引关系因此属于就地变换类型的操作。
- 构造过程中的下沉调整函数是该技术的核心所在它决定了后续一系列步骤能否高效运作的关键因素之一。

- **缺点**
- 数据分布不均匀可能导致频繁重构造成局部震荡进而降低总体吞吐量；另外稳定性方面存在缺陷无法保证相等键值之间的先后秩序。

#### 7. 计数排序 Counting Sort
计数排序适用于一定范围内整型数据统计频次之后按照频率重新组装输出结果的一种非比较类别的特殊手段。

- **优点**
- 执行速度快仅需一次遍历加若干次累加运算便可得出结论特别适合用来解决特定模式的问题比如字母表字符编码转换等场合。
- 安全可靠不会改变同名条目原有的前后关联属性故而是稳定可靠的解决方案。

- **缺点**
- 应用范围有限制只能作用于离散且有上下限约束的对象之上难以推广应用于浮点实数或其他连续域上的实例。

#### 8. 基数排序 Radix Sort
基数排序依据数字的不同位权由低位往高位依次分配给对应的容器内暂存起来等待收集汇总后继续向上一层推进直至最高有效位处理完结。

- **优点**
- 综合考虑到了各个维度的信息传递路径设计巧妙既保留了单趟流程耗时不随样本规模扩大而显著增长的优势又兼顾到了多阶段累积效应带来的好处总的时间代价大约相当于线性乘以位宽大小\(O(d*n)=O(k*n)\)(d代表关键字长度k表示基数数量)。
- 支持任意精度的大整数运算并且在整个过程中始终保持对象之间原本存在的相互依赖联系因而具有良好的兼容性和扩展能力。

- **缺点**
- 主要局限在于适用对象必须是可以分解为独立组成部分的整体例如正负整数字符串日期等等而对于其他形式的数据可能并不适用。