排序算法快速记忆

embedded/2024/9/24 1:25:03/

基础概念

1,插入排序(以第一个元素先入序列,然后逐个入序列)

从第一个元素开始,该元素可以认为已经被排序,然后取出下一个元素,从已排序的元素序列从后往前扫描,如果大于就在后面,如果小于就放前面

2,希尔排序(index增量对比,增量递减至1)

1,先选定一个增量(第一次是个数除以二),然后将所有距离为gap的元素分在同一组,进行对比,比如10个数,增量是10/2=5,所以第一个数和第六个数对比,如果第六个比较大,就互换位置,直到第五个被执行完,然后增量=5/2=2,重复该步骤
2,当增量的大小减到1时的排序,等于排序完成

3,选择排序(从候选中挑选入序列)

最简单的做法就是每次从候选中挑选一个最小值放入序列,优化做法是每次从候选中挑选最大和最小值,分别放序列的两头

4,冒泡排序(对比右移动)

从第一数开始,逐个对比,如果比较大,就向右移动一位

5,堆排序(完全二叉树)

堆排序是一种不稳定的算法>排序算法,它利用堆这种数据结构进行排序。堆排序的时间复杂度为O(nlogn),在原数据上进行排序,空间复杂度为 O(1)。但是,由于堆排序过程中必须先构建一个堆,因此需要占用额外的空间来存储堆。

6,快速排序(左右两边指针移动对比,停止指针位互换)

左右端最后一个分别是LR向中间走,但是位置并未变动,当左边走到比自己大的就停止,当右边遇到比自己小的也停止,然后指针的两个下标数据互换,互换结束后继续往前走,当两个指针碰一起,也就是index相同的时候,对比index的数据与两个端的大小,然后进行互换操作。这种算法快,复杂度是n*log2^n
简而言之,就是确定一个数作为基准,然后对比另一边,假设另一半大,就互换,然后基位到了另一边,反过来继续对比。

  • 假如数组是{2,8,7,1,3,5,6,4},以最后一个元素为基准元素,排序后结果是:{2,3,1,4,7,5,6,8}

1.起始指针位在index7,数字是4,对比左边指针位index0,数字是2,2比4小,对比下一位8 =》{2,8,7,1,3,5,6,4}
2.左指针位值 8 比右指针位值 4 大,位置互换,基准跳到左指针index1 =》{2,4,7,1,3,5,6,8}
3.重复一二步骤,左(1,4)比右(6,6)(5,5)都小,比(4,3)大,所以进行一次互换,基准位跳到4 =》{2,3,7,1,4,5,6,8}
4.基准位右指针位值 4)比左指针位值 7)小,互换,基准位跳到2 =》{2,3,4,1,7,5,6,8}
5.基准位左指针位值 4)比右指针位值 1)大,互换,基准位跳到3 =》{2,3,1,4,7,5,6,8}

7,归并排序

归并排序是一种稳定的、基于比较的算法>排序算法,采用分治思想,将待排序列分成若干个子序列,对每个子序列进行内部排序,最后合并各个有序子序列,得到完整的有序序列。归并排序的时间复杂度为 O(nlogn),可以保证排序的稳定性。

总结

  • 插入排序:先从候选中选择一个,然后逐个拿来对比,与新的序列进行对比,然后插入新序列。(需要新增数组)
    选择排序:每次从候选中选择一个最小或者最大值,插入新的序列(需要新增数组)
  • 希尔排序:折中取对比偏移量,逐个根据偏移量进行数据对比和互换,结束后继续折中偏移量(无需新增数组)
  • 冒泡算法:下标位进行遍历对比,直接在原来的列表上进行换位置,注意这里并非固定某一个候选值与其他进行对比。(无需新增数组)
  • 堆排序:不稳定排序,(时间复杂度O(nlogn),空间复杂度为O(1),需新增一个堆)
  • 归并排序:稳定排序,分治思想。(时间复杂度O(nlogn))
  • 快速排序:挑选最后一个作为候选值,先左边逐个对比,遇到比自己大则互换,然后与右边互换位置向左逐个对比,遇到比自己小则互换。相当于拿一个值作为标准,通过左右不断互换的方式让这个标准值的左边比自己小,右边比自己大。所以快速排序得到的结果并非一定是顺序的。

归纳

  • 1,插入排序和选择排序,都是针对数值,讲究的是从原来数组中挑选出来得到一个新数组,一个是拿出来后对比插入,另一个是先对比后直接拿出来放入,都需要创建一个新数组。

  • 2,希尔排序、冒泡排序和快速排序,都是针对下标,一个是偏移对比,一个是逐个对比,最后一个是左右下标偏互换,都是在自身数组上操作。


http://www.ppmy.cn/embedded/110258.html

相关文章

c++ run error: _M_construct null not valid

字符串拼接后运行报错。 #include <iostream> #include <string> using namespace std; int main() { int saveImageCount 123; int rtkEventCount 123; string strSend "{\n\t" "\"imageCount\"" : std::to_string(…

联邦迁移学习

Finetune&#xff08;微调&#xff09; 和 Fixed Feature Extractor&#xff08;固定特征提取器&#xff09; 确实有相似之处&#xff0c;但它们的关键区别在于模型参数的调整范围和任务的相似性。 区别&#xff1a; Finetune&#xff08;微调&#xff09;&#xff1a; 所有层…

七、装饰器模式

装饰器模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;允许在不改变对象自身的情况下&#xff0c;动态地向对象添加新功能。它通过将功能附加到对象的方式来增强其行为&#xff0c;提供了一种灵活的替代方案来使用子类扩展功能。 主要组成部分…

TikTok海外直播专线:顺畅的TikTok全球直播体验

TikTok直播功能的爆发式增长&#xff0c;迅速引领了社交媒体的新潮流。为了满足用户对海外直播的高质量需求&#xff0c;出现了专为TikTok直播打造的海外直播专线&#xff0c;帮助用户在全球范围内实现稳定、流畅的直播体验。 TikTok海外直播专线的核心技术与设计 TikTok海外直…

5个免费版文章生成器,自动写作文章没困扰

随着AI技术的发展&#xff0c;许多人工做的事情都变得简单化了&#xff0c;如&#xff1a;写作文章&#xff0c;以往都是人工写作&#xff0c;而现在可以由文章生成器进行自动写作了。用过文章生成器的人都知道它的强大之处&#xff0c;那么在市面上一些文章生成器中有免费可用…

为什么eBay的防IP关联很重要?

对于电商卖家来说&#xff0c;eBay是一个非常重要的平台。作为拥有庞大用户群和​​丰富商品种类的国际电商平台&#xff0c;eBay为卖家提供了广泛的市场覆盖和无限的商会。 然而&#xff0c;eBay严格的IP关联政策可能是一个巨大的障碍。如果多个账户使用同一个IP地址&#xff…

SpringBoot集成MyBatis-Plus

MyBatis-Plus简介 MyBatis-Plus&#xff08;简称 MP&#xff09;是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。 1.愿景 我们的愿景是成为 MyBatis 最好的搭档&#xff0c;就像 魂斗罗 中的 1P、2P&#…

开源 AI 智能名片小程序在内容营销中的应用与价值

摘要&#xff1a;本文深入探讨在消费升级的时代背景下&#xff0c;开源 AI 智能名片小程序如何在内容营销中发挥重要作用。阐述了内容营销通过图片、文字、视频等媒介传播相关内容信息给目标用户以促进销售及实现营销目的的过程。分析了开源 AI 智能名片小程序作为一种新型营销…