用大白话和面试官扯“八大常用排序算法的基本思想”

目录

一、直接插入排序

二、希尔排序

三、直接选择排序

四、堆排序

五、冒泡排序

六、快速排序

七、归并排序

八、基数排序

Hello，你好呀，我是灰小猿，一个超会写bug的程序猿。

最近在进行学习的时候发现总能用到数据结构中的各种排序算法，有的记忆不到位的还需要重新去了解学习。同时在很多的面试中面试官都喜欢提问常见排序的基本思想和步骤，所以今天就抽空在这里和大家用大白话总结一下常见的内部排序算法设计的基本思想，可能比较言简意赅，所以欢迎有其他见解的小伙伴在评论区提出分享。

一、直接插入排序

直接插入排序的基本思想：每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。

二、希尔排序

希尔排序的基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为dI的倍数的记录放在同一个组中。先在各组内进行直接插入排序；

然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dr=1(dr<dr-1<0<d2<dl)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

三、直接选择排序

直接选择排序的基本思想：选择法排序也是常用的排序方法之一，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换...依此类推，直到所有记录排完为止。

四、堆排序

堆排序的基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。它通过建立初始堆和不断地重建堆，逐个地将排序关键字按顺序输出，从而达到排序的目的。

五、冒泡排序

冒泡排序的基本思想：将被排序的记录数组R[1...n]垂直排列，每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

六、快速排序

快速排序的基本思想：采用了一种分治的策略，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

七、归并排序

归并排序的基本思想：将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并，直到得到长度为n的有序表为止，排序结束。

八、基数排序

基数排序的基本思想：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。

关于常见排序算法的基本思想浅谈就先和大家聊到这里，

之后还将具体针对每一个算法进行深入的剖析讲解。

感兴趣的小伙伴可以持续关注哟！

文章来源: blog.csdn.net，作者：灰小猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_44985880/article/details/115443961