前言

本文将对几种常见的排序算法进行总结和回顾，包括快速排序、归并排序、基数排序和堆排序。为了熟练掌握这些排序算法，我们需要从三个方面深入理解：算法类型、时间复杂度和空间复杂度，以及算法的稳定性。

算法类型

排序算法大致可以分为两大类：

• 比较类：这类算法通过比较元素来确定它们之间的相对顺序，但时间复杂度无法低于 O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类：这类算法不通过比较来决定元素间的相对顺序，可以实现线性时间复杂度，因此也称为线性时间非比较类排序。

具体排序算法分类如下：

冒泡排序

冒泡排序是一种简单的排序算法，通过多次遍历待排序数组，每次比较相邻的两个元素，较大的元素逐渐“浮”到数组的一端。

快速排序

快速排序通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的小，这样可以分别对这两部分继续排序，从而实现整个序列的有序化。

选择排序

选择排序每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到所有元素有序。

堆排序

堆排序利用堆这种数据结构进行排序，堆是一种特殊的树形数据结构，具有“堆性质”，即每个节点的值都大于或等于其子节点的值。

归并排序

归并排序采用分治法，将已有序的子序列合并，得到完全有序的序列。

直接插入排序

直接插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

希尔排序

希尔排序是对插入排序的一种改进，它首先将待排序文件分割成多个子序列，分别对各子序列进行插入排序，然后缩小增量，重复上述过程，直至增量为 1。

基数排序

基数排序按照低位先排序，然后收集；再按照高位排序，然后再收集，依次类推，直到完成最终排序。

时间复杂度和稳定性

以下是各种排序算法的时间复杂度和稳定性总结：

面试常考知识点

• 快速排序、基数排序和堆排序 是面试中最常考的三种排序算法。
• 归并排序 是比较类排序算法中占用内存最多的。
• 快速排序 是时间复杂度最低的算法之一。
• 快速排序、希尔排序、选择排序和堆排序 是不稳定的排序算法。

总结

本文总结了各种排序算法的核心内容，希望读者能够更好地理解和掌握这些算法。接下来的章节将介绍查找相关的内容及其重要考点。