## 1 对比总览

| 排序算法   | 核心思想                       |   最好时间复杂度  |   最坏时间复杂度  |    平均时间复杂度   |      空间复杂度     |  稳定性  |
| :----- | :------------------------- | :--------: | :--------: | :----------: | :------------: | :---: |
| 插入排序   | 将待排序元素插入到已有序序列的合适位置        |    O(n)    |    O(n²)   |     O(n²)    |      O(1)      |  ✅ 稳定 |
| 折半插入排序 | 用折半查找优化插入位置的查找过程           | O(n log n) |    O(n²)   |     O(n²)    |      O(1)      |  ✅ 稳定 |
| 希尔排序   | 分组插入排序，逐步缩小增量              |    O(n)    |    O(n²)   | O(n^1.3\~n²) |      O(1)      | ❌ 不稳定 |
| 冒泡排序   | 相邻元素两两比较，将较大元素逐步"冒泡"到末尾    |    O(n)    |    O(n²)   |     O(n²)    |      O(1)      |  ✅ 稳定 |
| 快速排序   | 选取基准，分治递归地将序列分为小于和大于基准的两部分 | O(n log n) |    O(n²)   |  O(n log n)  | O(log n)\~O(n) | ❌ 不稳定 |
| 简单选择排序 | 每趟选择未排序部分的最小元素放到已排序末尾      |    O(n²)   |    O(n²)   |     O(n²)    |      O(1)      | ❌ 不稳定 |
| 堆排序    | 利用堆这种数据结构，不断取出堆顶元素重建堆      | O(n log n) | O(n log n) |  O(n log n)  |      O(1)      | ❌ 不稳定 |
| 归并排序   | 将序列不断二分，对子序列排序后合并          | O(n log n) | O(n log n) |  O(n log n)  |      O(n)      |  ✅ 稳定 |
| 基数排序   | 按位（个/十/百位）依次进行分配和收集        | O(d·(n+k)) | O(d·(n+k)) |  O(d·(n+k))  |     O(n+k)     |  ✅ 稳定 |

> 注：基数排序中，d 为最大位数，k 为基数（如十进制 k=10）。

***

## 2 详细说明

### 2.1 插入排序

* **核心思想**：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分从后往前依次比较，找到合适位置插入。

* **适用场景**：数据量小（n < 50）或数据基本有序时效率很高。

* **特点**：实现简单，稳定，在接近有序时性能接近 O(n)。

### 2.2 折半插入排序

* **核心思想**：在插入排序的基础上，利用折半查找（二分查找）在已排序序列中快速定位插入位置，减少比较次数。

* **特点**：相比直接插入排序减少了比较次数，但移动次数不变，整体时间复杂度仍为 O(n²)。

### 2.3 希尔排序

* **核心思想**：将序列按一定增量分组，对每组进行插入排序；逐步减小增量，当增量为 1 时整个序列基本有序，最后做一次完整插入排序。

* **增量序列**：常见的有 Hibbard 增量（2^k-1）、Sedgewick 增量等，不同增量序列影响时间复杂度。

* **特点**：第一个突破 O(n²) 的排序算法，是插入排序的改进版。

### 2.4 冒泡排序

* **核心思想**：从前往后依次比较相邻元素，若逆序则交换，每趟将当前未排序部分的最大元素"冒泡"到末尾。

* **优化方案**：设置标志位，若一趟遍历没有发生交换说明已有序，可提前结束。

* **特点**：简单直观，速度较慢，适合教学场景。

### 2.5 快速排序

* **核心思想**：选择一个基准元素（pivot），将序列分成两部分——小于等于基准的在左边，大于基准的在右边，然后递归地对左右两部分排序。

* **最坏情况**：每次选择的基准恰好是最大或最小元素，退化为 O(n²)；可通过随机选取基准或三数取中法优化。

* **特点**：实际应用中最快的排序算法之一，C 标准库的 `qsort` 即采用此算法。

### 2.6 简单选择排序

* **核心思想**：每趟在未排序部分中找到最小（或最大）元素，将其与未排序部分的第一个元素交换。

* **特点**：比较次数始终为 O(n²)，与初始序列无关；但移动次数较少。

### 2.7 堆排序

* **核心思想**：将序列构建成一个大顶堆（或小顶堆），每次取出堆顶元素（最大值或最小值），将堆尾元素移到堆顶后调整堆，重复 n-1 次。

* **特点**：始终保持在 O(n log n) 的时间复杂度，不受初始序列影响；但不稳定。

### 2.8 归并排序

* **核心思想**：采用分治策略，将序列递归地二分至单个元素，然后逐层合并两个有序子序列。

* **实现方式**：分为自上而下的递归实现和自下而上的迭代实现。

* **特点**：稳定排序，效率稳定在 O(n log n)，但需要 O(n) 的额外空间。

### 2.9 基数排序

* **核心思想**：不直接比较元素大小，而是按位数（个位、十位、百位…）依次进行分配（入桶）和收集（出桶）。

* **实现方式**：

  * **LSD（Least Significant Digit）**：从最低位开始排序

  * **MSD（Most Significant Digit）**：从最高位开始排序

* **特点**：非比较排序，适用于整数或固定长度字符串，时间复杂度为线性。



核心思想：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分从后往前依次比较，找到合适位置插入。

排序算法对比

本文对比九种常见排序算法。O(n²)级中插入排序适合小规模或基本有序数据；O(n log n)级中快排实际最快但不稳定，归并稳定但需额外空间，堆排空间最优且性能稳定；基数排序线性时间处理整数。选型需根据数据规模、稳定性和内存限制综合考量。

算法

编程语言

"详解9大经典排序算法：插入排序、希尔排序、冒泡排序、快速排序、堆排序等核心原理与性能对比。包含时间复杂度、空间复杂度及稳定性分析，帮助开发者根据数据特点选择最优排序策略，提升算法效率。特别适合面试准备和算法优化参考。"

数据结构

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

排序算法对比-腾讯云开发者社区-腾讯云

排序算法对比

排序算法对比

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐