找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

史上最全排序算法总结 | 原力计划

admin 2020-1-15 16:40 86人围观 C++相关





作者 | 铁猴
责编 | 屠敏
出品 | CSDN 博客

 简介
本文对常见排序算法进行总结。


排序算法
冒泡排序该算法比较简单,几乎所有语言涉及到算法时,都会涉及到冒泡算法。算法思路:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

    持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
选择排序每次选择一个最大(小)的,直到所有元素都被输出。可参考:https://blog.csdn.net/sun7545526/article/details/85165618直接插入排序插入排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止算法思路:当插入第i(i >= 1)时,前面的V[0],V[1],……,V[i-1]已经排好序。这时,用V[I]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的元素向后顺移。以[21,25,49,25,16,08]为例,排序过程如下所示:

在小规模数据集或是基本有序时,该算法效率较高。希尔排序先对数据进行预处理,使其基本有序,然后再用直接插入排序算法排序。详细过程可参考:https://blog.csdn.net/eric_sunah/article/details/103080731快速排序利用“分而治之”的思想对集合进行排序可参考:https://blog.csdn.net/sun7545526/article/details/85165742堆排序说堆排序前,先说下啥是堆。堆:堆是满足下列性质的完全二叉树:

  • 每个节点都大于或是等于其左右孩子节点的值,称为大顶堆

  • 每个节点都小于或是等于其左右孩子节点的值,称为小顶堆
接下来说下堆是如何做排序的,思路如下(以大顶堆为例):

  1. 根节点是整个堆的最大值,将它移走。

  2. 将剩余n-1个节点重新构造成一个堆,再将根节点移走

  3. 重复执行1,2。直到没有节点可移动,就生成了有序序列。
该算法有两个需要解决问题:

  1. 如何将一个无序序列构建一个堆。

  2. 移除根节点后,如何用剩余的节点重建堆。
详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103081878归并排序归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103082607


总结
分类总结:

时间复杂度总结:

版权声明:本文为CSDN博主「铁猴」加入原力计划的原创文章。【成就一亿技术人】即日起至12.24日,CSDN协调更多流量给优秀原创作者!详情请戳下方二维码~~年底了,给用心写技术文章的同学意思意思


热 文 推 荐
小米卢伟冰回应“低价误国”;国产统一操作系统 UOS 正全面适配;Vue 2.6.11 发布 | 极客头条☞Nginx 之父被捕,程序员如何避免面向起诉编程?| CSDN 博文精选
☞让 API 端点的响应速度提高 50 倍!
☞微信地位,牢不可破?
HTML + CSS 为何得不到编程界的认可?
讯飞轮值总裁胡郁:大数据是人工智能产业落地的必要保障| BDTC 2019
公司倒闭,39 岁重新找工作,薪资不到 8000,太残酷!
阿里云上万个 Kubernetes 集群大规模管理实践


点击阅读原文,与作者面对面交流!


你点的每个“在看”,我都认真当成了喜欢
----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:CSDN,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......