今天学长为大家讲解数据结构中两朵奇葩之一
算法-排序
排序在我们的生活中可以说是处处可见，在各种地方和场合都需要进行排序，比如对于成绩的高低，各种的评分等等，也是数据结构中一大重要的算法。排序主要分为五大类分别是插入排序，选择排序，交换排序，归并排序以及基数排序，今天我们就其中一些主要的排序算法为大家讲解，共同揭开他们神秘的面纱！
排序和诸如线性表、图、树等章节的知识点不同，他的组织比较松散，知识点之间不存在层级关系。也就是说，在排序这个章节中，知识和知识之间的关系是平等的。不存在非要学懂冒泡排序才能理解选择排序。因此，对于本章的学习，要以分散的、独立的记忆为主，理解清楚各个算法的流程、特点、优点缺点即可。
在讲解各种排序之前，我们先看看各种排序的稳定性，时间复杂度、空间复杂度、稳定性，总结如下图：
冒泡顺序
冒泡排序顾名思义就是从最后往前两个元素开始进行两两比较，如果a小于a[i-1]，那么让他们互换位置，每比较一轮必有一个最小的元素冒泡到这些所比较元素的前面。
算法步骤：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
核心代码
希尔顺序
希尔排序是对插入排序的优化，基于以下两个认识：1.数据量较小时插入排序速度较快，因为n和n2差距很小；2.数据基本有序时插入排序效率很高，因为比较和移动的数据量少。
因此，希尔排序的基本思想是将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。
希尔排序的划分子序列不是像归并排序那种的二分，而是采用的叫做增量的技术，例如有十个元素的数组进行希尔排序，首先选择增量为10/2=5，此时第1个元素和第（1+5）个元素配对成子序列使用插入排序进行排序，第2和（2+5）个元素组成子序列，完成后增量继续减半为2，此时第1个元素、第（1+2）、第（1+4）、第（1+6）、第（1+8）个元素组成子序列进行插入排序。这种增量选择方法的好处是可以使数组整体均匀有序，尽可能的减少比较和移动的次数，二分法中即使前一半数据有序，后一半中如果有比较小的数据，还是会造成大量的比较和移动，因此这种增量的方法和插入排序的配合更佳。
希尔排序的时间复杂度和增量的选择策略有关，上述增量方法造成希尔排序的不稳定性。
核心代码
堆顺序
堆排序是一种基于二叉堆（BinaryHeap）结构的排序算法，所谓二叉堆，我们通过完全二叉树来对比，只不过相比较完全二叉树而言，二叉堆的所有父节点的值都大于（或者小于）它的孩子节点。
堆排序是把数组看作堆，第i个结点的孩子结点为第2*i+1和2*i+2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。
下述代码使用的大顶堆，建立好堆后堆顶元素为最大值，此时取堆顶元素即使堆顶元素和最后一个元素交换，最大的元素处于数组最后，此时调整小了一个长度的堆，然后再取堆顶和倒数第二个元素交换，依次类推，完成数据的非递减排序。
堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的文件
归并顺序
归并排序是采用分治法（DivideandConquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行.logn.次，因此，总的时间复杂度为O(nlogn)。
归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。
归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
选择顺序
选择排序的过程较为简单，通过遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。
核心代码
插入顺序
遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较是，原来靠后的还是拍在后边，所以插入排序是稳定的。
当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。
核心代码
bye~
今天是年9月10日
距离考研还有天
走好选择的路，别选择好走的路。
大牛学长一直在~
预览时标签不可点收录于话题#个上一篇下一篇