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

(一)常用的几个排序算法

admin 2019-10-8 07:41 76人围观 C++相关





-稳-定-



-安-全-



-高-效-


——

算法 ——

  算法是一个有趣好玩的东西,为什么这么说呢?因为你可以让计算机按照你编写的程序去运行出你想要的结果,比如说,单身的程序猿/媛用C++ new了很多个对象(嘻嘻)。下面进入正题。

算法是有限操作的集合。算法具备5个特征:1、有限性:一个算法必须保证执行有限步之后结束。2、确切性:一个算法的每一步骤必须有确切的定义。3、输入:一个算法有零个或多个输入,以刻画运算对象的初始情况,所谓零个输入是指算法本身给定了初始条件。4、输出:一个算法有一个或多个输出。没有输出的算法毫无意义。5、可行性:一个算法的任何计算步骤都是可以呗分解为基本可执行的操作,每一个操作都能够在有限时间内完成。

今天我们就来讨论几个比较常用的排序算法




  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。

  • 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。



        各排序算法时间复杂度和空间复杂度

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面

  • ​不稳定:如果a原本在b前面,而a=b,排序之后a可能会出现在b的后面



                     时间复杂度



01

冒泡排序

是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

简单的说就是大的沉下去,小的会慢慢浮上来







02

​选择排序


是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

简单的说,就是每次遍历都把最小(或者最大)的找出来摆放在指定位置





03

插入排序

  Interstellar FX拥有高性能的后端系统。

是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。




04

快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。






05

二路归并排序

是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

算法描述:

把长度为n的输入序列分成两个长度为n/2的子序列;

对这两个子序列分别采用归并排序;

将两个排序好的子序列合并成一个最终的排序序列。







扫码

关注






----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:MCU GROUP工作室,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

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

微信公众号

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

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

QQ交流群

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

我有话说......