经典排序算法全攻略
php中文网2019-04-20 15:21
金三银四的求职旺季眼看就要结束了，各位童鞋拿到心仪的Offer了吗？
这次跳槽季的面试中有没有被算法难倒呢？不久前，一位程序员就因为算法问题被面试官吐槽了：清华就这水平？
咳，清华的水平小编不敢妄作评论，不过算法是真心重要！就连李开复老师都曾经说过：“算法远远比日新月异语言重要得多。算法是本质，是‘万变不离其宗’的东西”。
算法不仅作为理论基础，微软造作系统的研发更新、谷歌搜索、百度地图引导等都需要强大的算法在背后支撑。今天小编就来和大家聊聊排序算法。
在开始今天的话题前，我们先来get一下，到底什么是排序呢？
排序是指将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。
作为计算机内经常进行的一种操作，简而言之，排序就是帮助它们回归自己的正确位置。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
按稳定性也可以分为稳定排序和不稳定排序：
稳定性：当序列中存在两个或两个以上的关键字相等的时候，如果排序前序列中1领先于2,那么排序后1如果仍旧领先2的话，则是稳定的。（相等的元素排序后相对位置不变）
不稳定性：当序列中存在两个或两个以上的关键字相等的时候，如果排序前序列中1领先于2,那么排序后1如果落后2的话，则是不稳定的。（相等的元素排序后相对位置发生改变）
下面咱们就一一来了解一下各大排序算法：
插入排序
插入排序的原理应该是算法中最容易理解的了。这是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这就好比打扑克牌，插入排序便是一套按照牌型大小对扑克牌进行整理的模式。插入排序分为直接插入排序与二分插入排序。
直接插入：将待排序的关键字依次与其前一个关键字起逐个向前扫描比较，若是待排关键字小于扫描到的关键字，则将扫描到的关键字的向后移动一个位置，直到找到没有比待排关键字大的地方插入。
二分插入：以待排关键字所在位置将序列分为有序数列和无序数列两部分，然后对有序数列进行折半查找，找出一个点，左边的序列都是小于待排序关键字，该点与其右边至待排关键字的序列都是大于待排关键字的，将右边序列右移然后插入空处
处。
冒泡排序
冒泡排序作为最简单的算法之一，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作就是重复地比较元素，直到元素们都落座了正确的位置，序列排序就算完成。
简而言之，将每次相邻两个关键字进行比较（0与1,1与2依次比较大小），小数上浮，大数下沉，每趟排序找出最大的数换到最右边。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，“blue、blue~”
选择排序
选择排序是一种简单直观的排序算法,它的标签就是“稳定”。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
首先，从n 个记录中找出关键码最小的记录与第一个记录交换；
接下来，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
最后，从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码起始有序就完成啦。
希尔排序
希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先对较远的元素“下手”。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。(鉴定完毕，是算法里的一枝独秀没错了...）
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
自上而下的递归：
所有递归的方法都可以用迭代重写，所以就有了第2种方法；
自下而上的迭代
归并排序有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。当n较大，内存空间允许，且要求稳定性 =》归并排序当n较小，可采用直接插入或直接选择排序。
快速排序
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。此时基准元素在其排好序后的正确位置然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
计数排序
计数排序是一种稳定的排序算法。它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。但是，计数排序也是很高冷哒！作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
同时有一定的局限性：
关键字可分解。 记录的关键字位数较少，如果密集更好 如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质。那二叉树结构是什么呢？它是一种特殊的树形结构，只是在每个节点之后又多出两个分支。但又同时满足堆积的性质，分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
桶排序
桶排序是计数排序的升级版。首先将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。它利用了我们高中所学函数的映射关系，高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的N个数据均匀的分配到K个桶中。总结
今天的排序算法就聊到这里了，随着人工智能的发展，互联网的人才要求越来越高，而只有你具备扎实的理论功底，才能力排万难，在茫茫面试者中脱颖而出，让我们一起加油吧
举报/反馈
0
0
收藏
分享
