一个个熟悉的排序

pre span > 排序，多么熟悉的词。在没有真正接触到它时，已经听闻了它的强大和重要性。如今，那一个个耳熟能详的排序算法，也渐渐的在自己面前揭开了它们的神秘面纱。 那么多的排序算法，想一一总结一番。可是，在每个总结之前，有个宏观整体上的认识，感觉效果会更好些。所以，我们先从排序讲起。 排序（Sorting）是数据处理中一种重要而且常用的运算。它就是将一组对象按照规定的次序重新排列的过程，往往是为检索服务的。 下面我将从以上四个方面，宏观认识一下排序算法。 首先，排序可分为两大类： （1）内部排序（Internal Sorting）：待排序的记录全部存放在计算机内存中进行的排序过程。 （2）外部排序（External Sorting）：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。 后面讨论的算法都是指的内部排序。 对于内部排序的方法，有很多种，主要总结的为排序、交换排序、选择排序和归并排序四类。 相同键值的两个记录在排序前后相对位置的变化情况是排序算法研究中经常关注的一个问题，这个问题称为排序算法的稳定性。 判断一种排序算法是否稳定，只需要看经过排序后，序列内相同键值的位置是否发生变化，如果没有变化，则是稳定的；如果位置发生了变化，则是不稳定的。 值得注意的是，稳定性是排序方法本身的特定，与数据无关，换句话说，一种排序方法如果是稳定的，则对所有的数据序列都是稳定的，反过来，如果一组数据上出现不稳定的现象，则该方法是不稳定的。

 下面是各种排序方法的稳定性比较：

 

 评价一个排序算法的优劣，通常可用时间复杂度和空间复杂度两个指标。我们主要讨论时间复杂度。

 在排序过程中主要有比较两个键值大小和将记录从一个位置移动到另一个位置这两种基本操作。因此，从键值的比较次数和记录的移动次数两个方面来分析时间复杂度。

 下面是各种排序算法的时间复杂度：

 到此为止，对排序算法的宏观认识也就结束了。主要是从排序的分类、方法、稳定性和时间复杂度四个方面剖析，并没有涉及到某一种排序方法的具体算法，这将是后面需要一个一个总结的工作。

 不管是软考还是自考，都需要学习和掌握排序算法。而此篇宏观性的博客，也主要是从自考的学习中着手，感觉思路更清楚，理解更容易。

我明白了，排序算法基础 `O(n^2)`的排序算法并不是最优的，最优的排序算法是 `O(nlogn)` 。 `O(n^2)`的排序算法相对是比较基础的，因为它是最简单的求解思路，在面临一个问题的时候，都会先尝试用最简单的方法去解决它，这个过程能够加深对问题本身的理解，从而提出更加复杂的解法，或者来优化最开始简单的解法。 对于一些问题，如果你没有思路的话，先拿出最简单的解法，虽然这个解法可能在效率上有一些问题，先将你这个解法摆出来，在这个过程中你可能会想到一些优化的地方，同时面试官也会看到你解题的路径，这也是一种非常好的解题思路。 并非是在所有的场合都去使用 `O(nlogn)`级别的排序算法的。编码简单，易于
我明白了，浅聊数据结构(和算法) 数据结构是计算机领域专业必学的知识点，因为数据结构研究的就是数据如何在计算机中进行组织和存储，从而高效的获取数据或者修改数据。 有时可以让我们根据不同的应用，灵活选择最合适的数据结构继而解决相应的问题。