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

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

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

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

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

1、冒泡排序

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

2、选择排序

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

3、插入排序

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

4、希尔排序


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

  1. 设为gap = n/2,向下取整,对gap个分组的每个小组的数进行直接插入排序
  2. 将gap更新为gap = gap /2,向下取整,对gap个分组的每个小组的数进行直接插入排序
  3. 重复这个过程直到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. 将数组按照最中间索引,分割为左右两个数组(奇数个数的数组左右两个数组的元素个数相差为1)
  2. 将左右两个数组继续分割为左右两个数组,直到分割到数组只有一个元素
  3. 创建一个空的数组,依次遍历左右数组,比较左右数组的第一个元素的大小,较小的那个元素从对应数组中弹出
  4. 重复3的过程,直到两个数组的元素都弹出,即都合并到了新数组中
  5. 按照1、2分割的方式,重复3、4的过程,继续合并左右数组,直到合并至最后一个数组完成排序

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

6、快速排序

第一个数为记作temp,最左边索引记为left,最右边为right,mid=(left+right)/2

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

7、堆排序

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

  1. 构造一个完全二叉树,将数组的数依次放入完全二叉树中
  2. 调整这个完全二叉树为一个大顶堆
  3. 交换根节点和最后一个结点的值,取出最后一个结点的值到已排序序列中
  4. 删除最后一个结点
  5. 重复2-4的过程,直到删除整个完全二叉树,完成排序

8、基数排序

  1. 首先找出最大的数,将它的位数记为k
  2. 构造一个桶结构,包含10个组,编号记为0-9
  3. 将原数组按进行遍历取出,将当前遍历的数按照个位上0-9数放入对应0-9编号桶中
  4. 将桶中的数按照顺序放回数组中
  5. 将个位换成10位,重复2-4的过程,直到达到k位

因此可以知道,基数排序对于浮点数、位数大的数有更好的效率。

这就是8大排序的口述版的全部内容了,有点的话拜托点赞、收藏、关注哦。

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

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

我的主页还有许多其他非常有价值的NLP内容

Transformer提出文章论文精读:

Transformer:《Attention is all you need》(论文精读/原理解析/模型架构解读/源码解析/相关知识点解析/相关资源提供)_会害羞的杨卓越的博客-CSDN博客

Transformer解读:

Transformer算法解读(self-Attention/位置编码/多头注意力/掩码机制/QKV/Transformer堆叠/encoder/decoder)_会害羞的杨卓越的博客-CSDN博客

Hugging Face实战:

Hugging Face实战(NLP实战/Transformer实战/预训练模型/分词器/模型微调/模型自动选择/PyTorch版本/代码逐行解析)上篇之模型调用_会害羞的杨卓越的博客-CSDN博客

bert系列算法

BERT系列算法解读:(RoBERTa/ALBERT/DistilBERT/Transformer/Hugging Face/NLP/预训练模型/模型蒸馏)_会害羞的杨卓越的博客-CSDN博客

包括一些大方向的内容:

深度学习五大基本网络_常用深度学习网络_会害羞的杨卓越的博客-CSDN博客

机器学习算法(全教程/全解析/源码全解/实战教程)_会害羞的杨卓越的博客-CSDN博客

人工智能的分类:机器学习/专家系统/推荐系统/知识图谱/强化学习/迁移学习/特征工程/模式识别_会害羞的杨卓越的博客-CSDN博客

计算机视觉:

openCV基础教程_会害羞的杨卓越的博客-CSDN博客

陆续更新中,有用的话拜托点赞收藏哦。文章来源地址https://www.toymoban.com/news/detail-641724.html

到了这里,关于八大排序/八大排序口述版/八大排序面试版/八大排序思路(冒泡排序/选择排序/插入排序/希尔排序/归并排序/快速排序/堆排序/基数排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包