八大排序/八大排序口述版/八大排序面试版/八大排序思路(冒泡排序/选择排序/插入排序/希尔排序/归并排序/快速排序/堆排序/基数排序)-Toy模板网

这篇具有很好参考价值的文章主要介绍了八大排序/八大排序口述版/八大排序面试版/八大排序思路(冒泡排序/选择排序/插入排序/希尔排序/归并排序/快速排序/堆排序/基数排序)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在算法和开发的面试中，经常会让你口述一下排序的某个算法的原理和思路，我整理了一下这八大排序的口述思路。

如果需要详细版本，包含思路、解析、代码、时间复杂度、空间复杂度、稳定性分析以及排序之间的详细比较的内容，请看这篇文章：

Python实现八大排序：排序特点/原理解析/思路解析/代码解析/考点解析/面试考试点睛(冒泡排序/选择排序/插入排序/希尔排序/归并排序/快速排序/堆排序/基数排序)_python排序从大到小_会害羞的杨卓越的博客-CSDN博客

1、冒泡排序

第一个数和第二个数比较，第一个数大则交换
第二个数和第三个数交换，第三个数大则交换
一直到最后一个数，则此时最后一个数为最大，最后一个数进入了已排序序列
重复1-3步骤，继续对前面n-1个数进行排序，完成排序

2、选择排序

第一步：选择第一个数的索引为最小数的索引
第二步：对剩下n-1个数进行遍历比较，遇到比当前最小索引数小的数，则更新最小索引
第三步：将新的最小索引数与第一个数进行交换，第一个数进入已排序序列（如果最小索引没有发生过变化，则不需要交换）
第四步：重复1-3步骤，继续对后面n-1个数进行排序，完成排序

3、插入排序

将第一个数与第二个数比较，第一个数大则交换，前面两个数进入已排序序列，第三个数为未排序序列的第一个数
未排序序列的数与已排序序列的所有数进行比较，将当前未排序序列的数插入到已排序序列的数
重复这个过程，完成排序

4、希尔排序

希尔排序也是插入排序的一种，对直接插入排序进行了改进，它采用了一种分组的策略使用直接插入排序，让排序的效率变得更高。分组数（也就是常说的gap，增量）

设为gap = n/2，向下取整，对gap个分组的每个小组的数进行直接插入排序
将gap更新为gap = gap /2，向下取整，对gap个分组的每个小组的数进行直接插入排序
重复这个过程直到gap为1，就是一个分组，即对整个数组进行一次直接插入排序

比如有10个数，第一次分组数就是10/2=5，这个5个分组对应的数的序号为：
（1，6）（2，7）（3，8）（4，9）（5，10）
对5个小组的所有数都进行一次直接插入排序
第二次分组数为5/2 = 2，这2个分组对应的数的序号为：
（1，3，5，7，9）（2，4，6，8，10）
对2个小组的所有数都进行一次直接插入排序

5、归并排序

主要采用分割和合并的思路进行排序

将数组按照最中间索引，分割为左右两个数组（奇数个数的数组左右两个数组的元素个数相差为1）
将左右两个数组继续分割为左右两个数组，直到分割到数组只有一个元素
创建一个空的数组，依次遍历左右数组，比较左右数组的第一个元素的大小，较小的那个元素从对应数组中弹出
重复3的过程，直到两个数组的元素都弹出，即都合并到了新数组中
按照1、2分割的方式，重复3、4的过程，继续合并左右数组，直到合并至最后一个数组完成排序

因此可以看出归并排序需要的内存资源明显比较大（空间复杂度较高）

6、快速排序

第一个数为记作temp，最左边索引记为left，最右边为right，mid=（left+right）/2

从nums[right]开始找比nums[left]小的数，找不到right一直左移，找到将nums[right]赋给nums[left]
从nums[left]开始找比nums[right]大的数，找不到left一直左移，找到将nums[left]赋给nums[right]
重复1-2的过程，使得left=right=mid，将temp赋给nums[left]
将原来的数组按照mid分割为两个部分，将剩下的两个部分重复1-3的过程
将剩下的数组继续按照mid分割为两个部分，重复1-4的过程

7、堆排序

大顶堆是一个每一个结点的值都大于左右子树的结点的值的完全二叉树，小顶堆是一个每一个结点的值都小于左右子树的结点的值的完全二叉树。在实际编程中，不需要构造完全二叉树这个数据结构，一个结点的索引为i时，它的左右子树的索引分别为（2i+1）、（2i+2），它的父节点的索引为ceil(i/2)-1。ceil是一个向下取整的python函数