老狗啃骨头之算法-八大排序算法
source link: http://www.veiking.cn/blog/1020-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
老狗啃骨头之算法-八大排序算法_老狗啃骨头_Veiking百草园-知识点滴,日常分享
排序，就是将一组无序的数据，按照一定规则，使其有序化排列。排序时是否根据比较来决定元素间的相对次序，还可以分为比较类排序、非比较类排序。无论什么分类，都是尝试将其算法特征进行归纳，是为了方便我们学习的，融会贯通，这些名称分类即使以后都忘了，在设计程序算法的时候，也会潜移默化的影响着我们，这才是最后真正的目的
传达摩祖师修于少林，功法大成，出『易筋经』。在金庸老先生的武侠江湖中，『易筋经』取古拙朴实之招式，聚根沉基稳之内力，属至高无上的武学精髓。其流传于民间的『易筋经十二式』，亦是一套不错的健身操，早晚操练，应能强身健体益气凝神，这些方法理论甚至已成为坊间各家拳法中习武的根基要术，演化出五花八门的操演招式。
（注：许多古籍，并无具考，神神叨叨很多也是胡诌八扯，尊重文化渊源，亦须晓格物致知；如手中菩提，可把玩修性，切勿执住成迷。）
咱们讹引一下：易筋经所说的这个清虚，犹如我们讲数据结构的学习和认识；这个脱换，就像我们说这个算法的设计与思考。我们接下来要说的八大排序算法，就像这个『易筋经十二式』一样，算是研究学习算法基础的基础。通过对这几种排序的了解和学习，真正理解算法学习的本质，以至于衍生到栈或队列或树还是图、任何复杂的结构，会发现他们差不多都是一样的原理。
我辈皆是程序员，自然还是说程序。接下来，咱们就捋捋这些个排序。
有序是快速精准定位数据的前提条件，所以排序是许多数据操作的前提。排序排序，就是将一组无序的数据，按照一定规则，使其有序化排列。
在大分类上，说有两种：内部排序和外部排序，内外之分，其实说的差不多就是内存外存。如数据能全部加载完，在内存中就可以完成的，我们说这是内部排序；如果数据量大，内存一下子搞不定，还得在外存，像硬盘之类的也要参与进来，我们说这就是外部排序。外部排序是一种工程算法的范畴，算是排序算法的具体应用，涉及方面较多，更复杂，我们这里暂且不管，我们要说的排序，都是内部排序，我们这里仅从数据结构这个层面，探讨算法。
这个内部排序，按照策略来说，又可以分成以下小类：交换排序、插入排序、选择排序、归并排序和基数排序，其中有些小类，还衍生出一些比较有个性的排序算法，如下图所示：
除了这些分类，排序时是否根据比较来决定元素间的相对次序，还可以分为比较类排序、非比较类排序。
无论什么分类，都是尝试将其算法特征进行归纳，是为了方便我们学习的，融会贯通，这些名称分类即使以后都忘了，在设计程序算法的时候，也会潜移默化的影响着我们，这才是最后真正的目的。
场景和性能
举例一组数字，在排序的时候，我们有时候会遇到两个数字是一样的，参考下图：
在计算机里，每个元素都被看成独立的对象，即使是同样的数字，此⑥非彼⑥，是两个不同的对象；在计算机里，相等不等于相同，相等、相同，注意这两个概念之间的不同。这种情况在排序的时候，就会出现这两个⑥，谁先谁后的问题，我们说：不影响相同元素最最初相对次序的排序，是稳定的排序；可能导致相同元素相对次序最后不确定的，是不稳定的排序。
说到研究算法，我们还要考虑时间复杂度和空间复杂度，带上这个稳定性，我们给常用的这八种排序算法，做了一个统计表，可以直观的参看对比：
我们可以看到，根据待排数据样本的大小，和数据样本的特点，不同的排序算法表现出来的性能优劣是有区别的。当n较大时，时间复杂度为O(nlog2n)的排序算法：快速排序、堆排序或归并排序，优势是很明显的。
按照分类，和复杂度等，我们粗略的看了看下这八种排序算法：冒泡排序、快速排序、直接插入排序、希尔排序、简单选择排序、堆排序、归并排序、基数排序，习惯上我们说插入排序，就是说直接插入排序；选择排序，就是指简单选择排序，所以，之后我们将通过图文代码一并来过一过这八大排序算法：
冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序、基数排序。Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK