关于*常见的四种排序算法的相关面试题

程序员面试干货来啦，今天小编就先为大家整理4道大厂面试时常见关于 *常见的四种排序算法 的面试题。看看你能答对几道题呢！多多掌握此类面试题，就会增加面试通过的机率哦，后续还有其他类的面试题，请持续关注哟！

19.1. 冒泡排序 1. 说明 冒泡排序是⼀种简单的排序算法。它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也 就是说该数列已经排序完成。 这个算法的名字由来是因为越 ⼩的元素会经由交换慢慢“浮”到数列的顶端。 2. 算法描述 (1)⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换它们两个； (2)对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对，这样在最后的元素应该会是最⼤的数； (3)针对所有的元素重复以上的步骤，除了最后⼀个； (4)重复步骤1~3，直到排序完成 3. 编码实现 function bubbleSort ( arr ) for ( let -1 ; i > 0 for ( let 0 //依次拿出相邻的2个进⾏⽐较 if 1 // 需要交换位置 1 1 ]] return arr 19.2. 选择排序 1. 说明 选择排序(Selection-sort)是⼀种简单直观的排序算法。它的⼯作原理：⾸先在未排序序列中找到最⼩（⼤）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最 ⼩（⼤）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。 2. 算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： ● 初始状态：⽆序区为R[1..n]，有序区为空； ● n-1趟结束，数组有序化了。 3. 编码实现 function selectSort ( arr ) const for ( let 0 ; i < len - 1 // 遍历未排序的区域 // 将最⼩值的下标暂定为i let // 依次与它右侧元素⽐较 for ( let 1 if // ⼀旦minIndex有变化(发现最⼩值的下标不是i) if return arr 19.3.插入排序 1. 说明 插⼊排序（Insertion-Sort）的算法描述是⼀种简单直观的排序算法。它的⼯作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插⼊。 2. 算法描述 ⼀般来说，插⼊排序都采⽤in-place在数组上实现。具体算法描述如下： ● 从第⼀个元素开始，该元素可以认为已经被排序； ● 取出下⼀个元素，在已经排序的元素序列中从后向前扫描； ● 如果该元素（已排序）⼤于新元素，将该元素移到下⼀位置； ● 重复步骤3，直到找到已排序的元素⼩于或者等于新元素的位置； ● 将新元素插⼊到该位置后； ● 重复步骤2~5。 3. 编码实现 function insertSort ( arr ) const // 假设第⼀个元素已排序了 for ( let 1 // 遍历未排序的区域 const // 将start与左边的⽐较(从右向⽐) let 1 while 0 1 // 向右移位 j-- 1 return arr 19.4. 希尔排序 1. 说明 1959年Shell发明，第⼀个突破O(n2)的排序算法，是简单插⼊排序的改进版。它与插⼊排序的不同之处在于，它会优先⽐较距离较远的元素。希尔排序又叫缩⼩增量排序。 2. 算法描述 先将整个待排序的记录序列分割成为若⼲⼦序列分别进⾏直接插⼊排序，具体算法描述： ● 按增量序列个数k，对序列进⾏k 趟排序； ● 每趟排序，根据对应的增量ti，将待排序列分割成若⼲长度为m 的⼦序列，分别对各⼦表进⾏直接插⼊排序。仅增量因⼦为1 时，整个序列作为⼀个表来处理，表长度即为整个序列的 长度。 3. 编码实现 希尔排序 1. 计算出⼀系列增量值(折半法): 对每个⼩数组进⾏插⼊排序 每个⼩数组排序是交替进⾏ let distance while ( distance > 1 distance Math .floor( distance / 2 ) // console.log(distance) for ( let distance // 遍历未排序的区域 // 将start与左边的⽐较(从右向⽐) let distance while 0 distance // 向右移位 distance distance return arr 希望这些面试题对你有所帮助！ 下一期我们会有关于其他大厂面试题。 别忘了关注我们的公众号哦，预防走丢！ 愿你眼眸有星辰，心中有山海，从此以梦为马，不负韶华！ 码上未来，成就你更好的未来！

END