【读书笔记】算法漫步 第6章

问题7 排序

 很多时候，如果集合中的数据是有序的，处理效率会比无序时高得多，所以排序（就是让数据集有序排列的过程）的重要性不容置疑，因为排序使用颇为频繁，同事数据集的规模越来越大，因此排序过程的效率尤为重要。

对排序的研究，在计算机出现以前就颇有研究。随着计算机应用领域的广泛，排序算法在计算机实现也是最早被研究和实现的一类算法。

排序问题是一个非数值问题（查找也是一个非数值问题），排序的逻辑（排序的实现方法）不是一个数值过程，或者说不是一个数学方法，无需什么数学基础或数学思维。

排序算法和程序，更多的是涉及算法逻辑、程序和数据结构的知识。当然，一个正常的人类，只有有一定的经验和能力，在日常的生活中都会排序，不过要能够理解和掌握高效的排序算法，实现高效的排序程序还是需要专门的学习和实践的。实话实说，很多先进的排序算法不是一般人能够想出来的。当然，学习先进的排序算法，一般人都可以。

本章首先介绍了一个来源于生活的冒泡排序算法，这个算法的逻辑其实不用学，很多人都会。如果真的学习排序，就会知道这个算法本身是没有什么实用价值的，因为它是一种最没有效率的方法。书中给了一个简要的说明，如果在特定计算环境下对100万个数据排序，某个先进的算法（比如书中介绍的另一个算法）需要1S，那冒泡排序算法可能需要10h以上，我以前上课时，讲排序，就是一开始运行两个程序（一个是冒泡，一个是快排），然后到了下课，快排程序早结束了，而冒泡排序程序还在执行中。

本章还介绍了经典的先进排序—快速排序和合并排序（也叫归并排序）。

以及简要介绍了排序问题的下界（或者称为下限，这是一个计算机领域的专有名词）

【作者感受】

排序问题和排序算法研究和使用的历史悠久，现在还有人再研究和设计新的排序算法，但是对一般人来说，更多的使用排序。因为历史上，已经有很多先进高效的排序算法被发明和设计出来了。

现在，学习排序算法，我个人觉得更多的是训练计算思维。通过学习各种排序算法，设计的逻辑，在程序和数据结构方面设计的技巧，分析排序方法的性能，都是很好的训练计算思维的教学素材。