电脑网站打不开怎么解决网站网页设计

408答疑

---

---

一、排序的基本概念

• 文章链接: 点击跳转

二、插入排序

• 文章链接: 点击跳转

三、交换排序

• 文章链接: 点击跳转

四、选择排序

• 文章链接: 点击跳转

五、归并排序、基数排序和计数排序

• 文章链接: 点击跳转

六、排序的代码实操

• 文章链接: 点击跳转

七、各种内部排序算法的比较及应用

• 文章链接: 点击跳转

八、外部排序

• 暂略

九、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书

---

十、总结

• ​数据结构框架和逻辑结构
  需明确数据结构的基本框架与逻辑结构关系，为算法实现奠定基础
• ​学习方法
  • 先通过画图理清排序流程，再研究代码实现
  • 复杂代码由小模块组成，需先理解整体流程再分解学习
  • 避免死记硬背代码细节（如 mid+1、right-1），应在实践中理解其作用
• ​稳定性前提
  仅当存在重复数据时，排序算法的稳定性才有意义
• ​学习建议
  • 多画图辅助理解排序过程，尤其是边界条件与数据交换逻辑

基本排序算法

• 直接插入排序、冒泡排序和简单选择排序是基本的排序算法，它们主要用于元素个数 $n$ 不是很大的（$n<10000$）的情形。

• 它们的平均时间复杂度均为 $O(n^2)$，实现也非常简单。直接插入排序对于规模很小的元素序列（$n\le 25$）非常有效。它的时间复杂度与待排序元素序列的初始排列有关。在最好情况下，直接插入排序只需要 $n-1$ 次比较操作就可以完成，且不需要交换操作。在平均情况下和最差情况下，直接插入排序的比较和交换操作都是 $O(n^2)$。冒泡排序在最好情况下只需要一趟排序过程就可以完成，此时也只需要 $n-1$ 次比较操作，不需要交换操作。简单选择排序的关键字比较次数与待排序元素序列的初始排列无关，其比较次数总是 $O(n^2)$，但元素移动次数则与待排序元素序列的初始排列有关，最好情况下数据不需要移动，最坏情况下元素移动次数不超过 $3(n-1)$。

• 从空间复杂度来看，这三种基本的排序算法除一个辅助元素外，都不需要其他额外空间。从稳定性来看，直接插入排序和冒泡排序都是稳定的，但简单选择排序不是。

希尔排序

• 对于中等规模的元素序列（$n\le 10000$），希尔排序是一种很好的选择。在希尔排序中，开始时增量较大，分量较多，每个组内的记录数较少，因而记录的比较和移动次数较少，且移动距离较远；到后来步长越来越小（最后一步为 1），分组越少，每个组内的记录数越多，但同时记录次序也越来越接近有序，因而记录的比较和移动次数也都比较少。从理论上和实验上都已证明，在希尔排序中，记录的总比较次数和总移动次数比直接插入排序时少得多，特别是当 $n$ 越大时效果越明显。而且，希尔排序代码简单，基本上不需要什么额外内存，但希尔排序是一种不稳定的排序算法。

快速排序、堆排序和归并排序

• 对于元素个数 $n$ 很大的情况，可以采用快速排序、堆排序、归并排序或基数排序，其中快速排序和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法。

• 快速排序是最通用的高效内部排序算法，特别是它的划分思想经常在很多算法设计题中出现。平均情况下它的时间复杂度为 $O(n{\log }_{2}n)$，一般情况下所需要的额外空间也是 $O({\log }_{2}n)$。但是快速排序在有些情况下也可能会退化（如元素序列已经有序时），时间复杂度会增加到 $O(n^2)$，空间复杂度也会增加到 $O(n)$。但我们可以通过“三者取中”法来避免最坏情况的发生。

• 堆排序也是一种高效的内部排序算法，它的时间复杂度是 $O(n{\log }_{2}n)$，而且没有什么最坏情况会导致堆排序的运行明显变慢，并且堆排序基本上不需要额外的空间。但堆排序不大可能提供比快速排序更好的平均性能。

  • 同一数据集通过不同建堆方式（整体建堆 vs 边插入边调整）可能得到不同堆结构
  • 节点删除依据优先级（类似优先级队列），而非插入顺序
  • 底层实现为数组，逻辑结构视为完全二叉树
  • 应用需理解原理（如 Top-K 问题），非单纯背诵

• 归并排序也是一个重要的高效排序算法，它的一个重要特性是性能与输入元素序列无关，时间复杂度总是 $O(n{\log }_{2}n)$。归并排序的主要缺点是需要 $O(n)$ 的额外存储空间。

• 基数排序是一种相对特殊的排序算法，这类算法不仅是对元素序列的关键字进行比较，更重要的是它们对关键字的不同位部分进行处理和比较。虽然基数排序具有线性增长的时间复杂度，但由于在常规编程环境中，基数排序的线性时间开销实际上并不比快速排序的时间开销小很多，并且由于基数排序基于的关键字抽取算法受到操作系统和排序元素的影响，其适应性远不如普通的进行比较和交换操作的排序算法。因此，在实际工作中，常规的高效排序算法如快速排序的应用要比基数排序广泛得多。基数排序需要的额外存储空间包括和待排序元素序列规模相同的存储空间及与基数数目相等的一系列桶（一般用队列实现）。

混合使用

• 我们可以混合使用不同的排序算法，这也是得到普遍应用的一种算法改进方法，例如，可以将直接插入排序集成到归并排序的算法中。这种混合算法能够充分发挥不同算法各自的优势，从而在整体上得到更好的性能。