总览

第 2 章排序

排序就是一组对象按照某种逻辑顺序重新排列的过程。计算机早期的时候，人们认为 30%的时间都花在了排序上。今天这个比例降低了的原因是现在的排序算法更加高效，而不是重要性降低了。

2.1 初级排序算法

学习的目的是熟悉术语以及简单的技巧，而且这些算法某些情况下会比讨论的复杂算法更加高效，他们有助于我们改进复杂算法。

2.1.2 选择排序

最简单的排序算法：找到最小的一个，放到第一位，然后找剩余的最小的，放到第二个，

内循环：就是 N 次的交换，以及 n-1 一直到 1 的和。为~N2/2 次的比较。

2.1.3 插入排序

原理：从最左侧开始一个个比较，然后插入到左侧中合适的位置去。一个个的比较插入。

最好情况，N-1 次比较，0 次交换，最坏情况 N2/2 比较和 N2/2 次交换。平均是 N2/4 次比较和 N2/4 次交换

结论是部分有序的情况下适合插入排序

2.1.4 排序算法的可视化

其实就是可视化轨迹图

2.1.5 比较两种算法

就是很简单的运行时间进行比较

2.3 快速排序

适用于各种不同的输入数据，在一般情况下比其他排序算法都要快一些。还有个小的点是他是原地排序，只需要很小的辅助栈。

2.3.1 基本算法

是分治的排序算法，切分的位置取决于数组的内容、

原理：就是随意取一个值，然后 i 从前面开始找，j 从后面开始找，找到第一个比这个值大的就与 j 的值换位置。j 取为新值。从左侧开始找第一个比这个值小的值，与这个值换位置。i 取为新的值。然后继续遍历。直到 i 与 j 相遇，这个时候左右两边就被分为了两块。然后重复上面的内容就可以了。

平均需要 2NlnN 次比较以及 1/6 的交换。

证明略费事

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 981909093@qq.com