数据结构中七大排序算法原理解析（快速/冒泡/插入/折半插入/选择/堆/归并）

目录

一、冒泡排序原理

二、快速排序原理

三、直接插入排序原理

四、折半插入排序原理

五、直接选择排序原理

六、堆排序原理（以小根堆为例）

七、归并排序原理

总结对比表

       排序是计算机科学中最基础、最经典的问题之一。无论你是准备期末考试的在校生，还是刷题备战面试的求职者，亦或是想要提升代码效率的开发者，掌握排序算法都是绕不开的必修课。

        为什么快速排序被称为“快速”？为什么插入排序要从后往前比较？堆排序是如何做到既高效又节省空间的？冒泡排序真的那么“慢”吗？

        本文将用最简洁的语言，为你拆解七大经典排序算法的核心原理。不需要复杂的数学推导，只需一张图、一段话，就能让你快速理解每种算法的精髓。无论你是初学者还是想温故知新的老手，相信都能从中获益。

        让我们从最熟悉的冒泡排序开始，逐步揭开排序算法的神秘面纱。

一、冒泡排序原理

基本思想：

• 从左到右，依次比较相邻两个元素

• 如果左边的元素大于右边的元素，就交换位置

• 一轮比较下来，最大的元素会被“冒泡”到最右边

• 重复上述过程，直到整个序列有序

优化：若某一趟没有发生交换，说明已有序，可提前结束

时间复杂度：最好 O(n)，最坏 O(n²)

视频演示：

用剪映专业版制作数据结构冒泡排序算法原理演示视频

二、快速排序原理

问题引入：一趟冒泡排序只能使一个元素排序到位。

快速排序特点：

• 一趟操作后使某个元素排序到位（该元素称为基准）

• 该元素把序列划分为两个子序列：

  • 左边所有元素 ≤ 基准

  • 右边所有元素 ≥ 基准

• 递归对左右子序列重复上述过程

时间复杂度：平均 O(n log n)，最坏 O(n²)

视频演示：

用剪映专业版制作快速排序算法原理(数据结构)演示视频

三、直接插入排序原理

基本思想：

• 将待排序元素与已排序部分的最后一个元素开始比较

• 若当前元素大于待插入元素，则将其后移一位

• 继续与前一个元素比较，重复上述过程

• 直到找到小于等于待插入元素的位置，即插入点

为什么不从前往后比较？

• 从后向前可以一边比较一边移动元素，查找与移动合并为一次循环，效率更高

• 从前往后比较需要先找到位置，再单独移动元素，多一次遍历，效率更低

时间复杂度：最好 O(n)，最坏 O(n²)

视频演示：

用剪映专业版制作直接插入排序算法原理演示视频

四、折半插入排序原理

基本思想：

特点：减少了比较次数，但移动次数不变

时间复杂度：O(n²)

视频演示：

用剪映专业版制作折半插入排序算法原理(数据结构)演示视频

五、直接选择排序原理

基本思想：

• 在同一个数组中进行直接选择排序

• 选挑一个最小的，跟第一位交换

• 待排序下标往后移到第二位，从这里开始往后找一个最小的，跟第二位交换

• 待排序下标往后移到第三位，以此类推

特点：

• 每趟最多交换一次

• 比较次数固定为 n(n-1)/2

时间复杂度：O(n²)

视频演示：

用剪映专业版制作直接选择排序算法原理(数据结构)演示视频

六、堆排序原理（以小根堆为例）

基本思想：

1. 建堆

将一个无序序列构建成一个小根堆。小根堆的特性是：堆顶元素是整个堆中最小的

2. 反复取出堆顶

• 取出堆顶元素（当前最小值），将其放到有序序列的末尾

• 将剩余元素重新调整成小根堆

• 重复此过程，直到所有元素都被取出

• 最终得到一个从小到大排列的有序序列

时间复杂度：O(n log n)

视频演示：

制作堆排序算法原理(数据结构)演示视频

七、归并排序原理

基本思想：采用分治法

步骤：

初始状态：46  33  66  38  92  30

（1,1）归并后：[33 46]   [38 66]   [30 92]

（2,2）归并后：[33 38 46 66]   [30 92]

（4,4）归并后：[30 33 38 46 66 92]

时间复杂度：O(n log n)

总结对比表