您好、欢迎来到现金彩票网!
当前位置:秒速牛牛投注 > 桶链算法 >

数据结构与算法的重温之旅(九)——三个简单的排序算法

发布时间:2019-07-21 17:01 来源:未知 编辑:admin

  前面的几篇文章讲了一些基础的数据结构类型,这次我们就深入算法,先从简单的排序算法说起。在排序算法中,入门必学的三个算法分别是冒泡排序、插入排序和选择排序。下面就具体讲一下这三个算法的原理和代码实现

  冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

  在这里提一个知识点,如果涉及到两数交换的话除了用一个临时变量来暂存这种方法外,还有用异或运算来实现两数交换。上述的代码可以改写如下:

  异或运算是位运算,也就是将数字转换成二进制来运算。异或运算是两个数相同位上的数互相比较,只要是相同则返回0,不同则为1。拿个简单的例子:

  第一步异或运算里,a为1,对应的二进制是01,b为2对应的二进制是10,所以运算后a为11,也就是3。第二步的异或运算里,a为11,b为10,运算后可得b为01,也就是1。到第三步里,a为11,b为01,可得a为10,也就是2。这就不利用临时变量来实现两数交换。位运算在处理数据量比较大的情况下十分的高效,但是由于冒泡排序算法的时间复杂度太高,所以在大数据的情况下还不如换另一种时间复杂度低的算法。

  冒泡排序除了上述利用位运算来优化外还可以通过判断后面的元素是否有交换来提前结束冒泡,优化改进如下:

  在这里,如果判断到后面没有发生交换,则可以判断后面的元素已经有序,则不需要再次遍历数组,提高了算法的性能。

  在用算法的时候,不止要懂原理,也要懂如何根据它的性能来使用到不同的场景中,下面就以三个点来说一下算法性能的分析。

  我们在分析算法的时间复杂度的时候,要分别的列出最好情况、最坏情况合评价情况的时间复杂度。为什么要做区分呢,首先为了算法之间更好的对比性能,其次是有些极端情况,比如说在高度有序或者杂乱无章的情况下执行的时间会各有不同,所以我们要知道排序算法在不同数据下的性能表现。

  除此以外,之前所要忽略的系数、常数、低阶也要考虑进来。我们知道,时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中,我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据,所以,在对同一阶时间复杂度的排序算法性能对比的时候,我们就要把系数、常数、低阶也考虑进来。

  还有一点,在上面说提到的三个基于比较的排序算法,都涉及到比较和替换。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

  算法的内存消耗其实就是算法所额外占用空间的多少,可以通过空间复杂度来衡量。针对排序算法的空间复杂度,这里引入了一个新概念原地排序(Sorted in place)。原地排序算法,就是特指空间复杂度是 O(1) 的排序算法。我们上面讲的三种排序算法,都是原地排序算法。

  仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法,我们还有一个重要的度量指标,稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

  比如一组数据5,2,3,2,6,1。经排序后可得1,2,2,3,5,6。这组数据里有两个 2。经过某种排序算法排序之后,如果两个 2 的前后顺序没有改变,那我们就把这种排序算法叫作稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫作不稳定的排序算法。

  可能看着这个例子看不出什么起来,但是如果要排序的是对象元素,则很容易看出算法的稳定性。比如说,我们现在要给电商交易系统中的“订单”排序。订单有两个属性,一个是下单时间,另一个是订单金额。如果我们现在有 10 万条订单数据,我们希望按照金额从小到大对订单数据排序。对于金额相同的订单,我们希望按照下单时间从早到晚有序。对于这样一个排序需求,我们怎么来做呢?借助稳定排序算法,这个问题可以非常简洁地解决。解决思路是这样的:我们先按照下单时间给订单排序,注意是按照下单时间,不是金额。排序完成之后,我们用稳定排序算法,按照订单金额重新排序。两遍排序之后,我们得到的订单数据就是按照金额从小到大排序,金额相同的订单按照下单时间从早到晚排序的。为什么呢?

  稳定排序算法可以保持金额相同的两个对象,在排序之后的前后顺序不变。第一次排序之后,所有的订单按照下单时间从早到晚有序了。在第二次排序中,我们用的是稳定的排序算法,所以经过第二次排序之后,相同金额的订单仍然保持下单时间从早到晚有序。如果是先排金额再排时间的话,排时间的时候可能某个很前的时间端有个很大的金额,这个时候大金额可能排到前面导致不能满足先金钱有序的前提。下面就以上面的三个算法来更加详细的说明。

  首先以是否是原地排序算法为例。冒泡排序算法涉及到相邻的交换和比较操作,只需要常量级的临时空间,所以空间复杂度是O(1), 是原地排序算法。插入排序和冒泡排序一样也执行了交换和比较操作,所以也是原地排序,空间复杂度为1。同理,由于选择排序和插入排序类似,所以也是原地排序算法。

  再来说一下是否是稳定排序算法。在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

  在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。

  那选择排序是稳定排序算法吗?答案是否定的,选择排序是一种不稳定的排序算法。选择排序的定义里,每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

  有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样:

  比如3,4,6,5,2,1这个数据里,有序度为5,有序元素的对数分别是(3,4), (3,6), (3,5), (4,6), (4,5)。对于有序度是n*(n-1)/2,我们可以把它称作为满有序度,而逆序度的计算公式则是满有序度减有序度。

  我们从上面知道,冒泡排序包含两个操作原子,比较和交换。每交换一次,有序度就加 1。不管算法怎么改进,交换次数总是确定的,即为逆序度,也就是n*(n-1)/2–初始有序度。如上面的3,4,6,5,2,1这个例子,则要进行10次交换操作。

  在这里我们可以得出一个结论,由于选择排序不是一个稳定性排序算法,即使和冒泡和插入排序一样是原地排序算法和时间复杂度一样,但由于这个缺点,所以就选择插入排序或冒泡排序。而在冒泡排序和插入排序中对比,我们可以发现冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。插入排序比冒泡排序少了两个步骤使得它的性能比冒泡排序要好一点。可能在小数据下看不出来,但是涉及到大数据的情况下这点细微的差别就会被放大出来了。

  1.分类1.1时间复杂度为O(n^2)的排序算法1.2时间复杂度为O(nlogn)的排序算法1.3时间复杂度为线.2代码实现2...博文来自:YETA的博客

  从上一篇冒泡排序中,相信大家也掌握到了要点:轮次,每轮相邻两个比较,把最大值(最小值)推到边缘。这一篇主要讲的简单选择排序,思想更加简单。目录1、简单选择排序的思想:2、复杂度分析3、C++实现1、简...博文来自:dongfanglanyi的博客

  快速排序C++异常处理查找与排序:顺序查找、二分查找、哈希表查找、二叉排序查找...博文来自:OldBowl

  一、前言直接插入排序(InsertionSort)序是一种最简单的插入排序。为简化问题,在此我们只讨论升序排序。二、算法思想插入排序:每一趟将一个待排序的记录,按照其关键字的大小插入到有序队列的合适位...博文来自:nageaixiaodenanhai的博客

  数据结构中常见的几种排序算法快速排序目录数据结构中常见的几种排序算法快速排序插入排序希尔排序归并排序堆排序选择排序冒泡排序基数排序快速排序基本思想:基准分割法 a)通过一趟排序将要排序的数据分割成...博文来自:的博客

  简单选择排序(SimpleSelectionsort)简单选择排序是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续...博文来自:swjtuzbko的专栏

  前面两篇中冒泡排序和简单选择排序在武林中的没落,首先是因为希尔排序算法的到来,它终结了时间复杂度只能是O(n^2)的时代,同时呢,直接插入排序又因为是希尔排序算法灵魂的来源,所以,在这儿一并学习。一、...博文来自:dongfanglanyi的博客

  1定义和前置条件1.1定义将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv,在最后的排序结果中,顶点u总是在顶点v的前面。假设我非常想学习一门机器学习的课程,但是在修这么...博文来自:chenliguan的博客

  这一节我们学习一个新的排序算法,准确的来说,应该叫“有向图的拓扑排序”。所谓有向图,就是A-gt;B,但是B不能到A。与无向图的区别是,它的边在邻接矩阵里只有一项(友情提示:如果对图...博文来自:倪升武的博客

  程序员小灰2017年原创汇总 程序员小灰2018年原创汇总博文来自:$firecat的代码足迹$

  这几个月以来,有许许多多的小伙伴在公众号后台询问小灰出书的进展,小灰非常感谢大家的热切关注。今天,小灰终于可以告诉大家一个好消息:小灰的书今天开始预售,4月底正式出版!书......博文来自:程序员小灰的博客

  简单选择排序算法简单选择排序算法:即通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换。排序过程如下所示:具体实现算法如下:voidSimpleSelection...博文来自:

  借鉴博客:目的:1.掌握常见的内部排序算法的思想及其适用条件。2.掌握常见的内部排序算法的程序实现...博文来自:far away

  作者:离散梦欢迎大家给出宝贵的建议! 数据结构之排序算法 稳定排序:冒泡、插入、归并、基数不稳定排序:选择、快速、希尔、堆 口诀就是:快(快速)些(希尔)选(选择)一堆(堆)好朋友来玩吧! 1.冒泡排...博文来自:离散梦

  1.树2.二叉树2.1满二叉树2.2完全二叉树3.二叉树的应用3.1查找3.2维持相对顺序(插入)4.二叉树的遍历5.二叉堆6.优先队列1.树树是n个节点的有限集。当n=0时,称为空树。在任意一个非空...博文来自:YETA的博客

  1.插入排序概念        插入排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。      可以选择不同的方法在已...博文来自:数据结构学习心得

  归并排序的基本思想归并排序法是将两个或以上的有序表合并成一个新的有序表,即把待排序序列分成若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序实例:合并方法:设r[i……n...博文来自:CSDN_564174144的博客

  这次来说一下拓扑排序的东西,仍是基于自己看的资料进行整理的(《数据结构与算法分析c++描述》这本书真的好,强烈推荐)。拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从Vi到Vj的路径,那么...博文来自:陌上行走的博客

  综述完整代码-顺序表版本完整代码-链表版本交换排序冒泡排序快速排序插入排序直接插入排序希尔排序折半插入排序选择排序直接(简单)选择排序堆排序归并排序基数排序参考综述排序大的分类可以分为两种:内排序和外...博文来自:王某的博客

  排序算法有8种:插入排序:直接插入,希尔排序选择排序:简单选择,堆排序交换排序:冒泡排序,快速排序归并排序基数排序上面八种排序我们可以用一个场景进行串联:——打针记忆方法:护士给我们治病打针,用针管插...博文来自:zhouzhenyong的专栏

  经典的排序算法有八种,分别为:Ø 冒泡排序Ø 选择排序Ø 插入排序Ø 归并排序Ø 希尔排序Ø 快速排序Ø 堆排序Ø 基数排序其中冒泡排序、选择排序、插入排序称为三大基本排序。虽然这三大基本排序算法时间...博文来自:qianfeng_dashuju的博客

  一,直接插入排序将前两个个数排序,构成一个有序数列,再将第三个数加入,将三个数进行排序,构成一个有序数列,再将第四个数加入。。。。直到把第n个数加入,并进行排序packageSortingOrder;...博文来自:的博客

  稳定的排序算法:开始的值相同的元素排序过后,相对位置仍然相同1.直接插入排序:无序的序列依次插入有序的序列  复杂度o(n(2));稳定;空间复杂度o(1)publicstaticint[]direc...博文来自:Aye

  八大排序算法概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。  ...博文来自:小哲的博客

  冒泡排序选择排序插入排序归并排序快速排序堆排序希尔排序眼看着就要实习,为了巩固基础,回顾并总结排序算法。参考自:冒泡排序时间复...博文来自:让勤奋成为习惯

  本节介绍三种选择排序算法,分别为:简单选择排序、树形选择排序和堆排序。简单选择排序该算法的实现思想为:对于具有n个记录的无序表遍历n-1次,第i次从无序表中第i个记录开始,找出后序关键字中最小的记录,...博文来自:数据结构入门教程

  临近期末,学了一学期“数据结构”让写课程设计,就选了“内部排序算法的性能分析”。主要是分析关键字的移动次数和比较次数,其中关键字若发生交换,则记为三次移动。下列代码中,“move”记为关键字的移动次...博文来自:冯卿的博客

  实现经典的9种排序算法,分析其时间复杂度以及空间复杂度,并用动画的方式演示。一、冒泡排序步骤:比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。对每一对相邻元素作同样的工作,从开始第一对到结...博文来自:Alan_1550587588的博客

  参考:线性查找二分查找冒泡排序插入排序选择排序快速排序归并排序1线性查找线性查找,又称为顺序...博文来自:的博客

  下面按照课本的分类,做了大致的内排序的归类的图片:下面我们逐个来实现排序的算法:一、插入排序算法:包括:直接插入、折半插入、和希尔排序其中,插入排序的思想都是一样的,都是以首个待排序的数字作为假设已经...博文来自:无涯明月

  冒泡排序的基本思想:两两比较相邻的元素,如果反序则交换,直到没有反序的元素为止。amp;lt;一.冒泡排序的初级版(交换排序)amp;gt;交换排序:当前位置的元素与后面的元素比较...博文来自:小白的博客

  引子:最近老东家要阵亡了,出来另谋生路。排序算法分类:内部排序插入排序1).直接插入排序2).折半插入排序3).希尔排序交换排序1).冒泡排序2).快速排序选择排序1).简单选择排序2).堆排序归并排...博文来自:一只写代码的狐松鼠

  一、排序算法的分类  下图是我掌握的一些排序算法,我将他们做了分类,当然,排序算法远不止这些。本篇博客主要记录插入,选择,以及交换排序的冒泡排序,因为快排和归并算法相对复杂,所以,下一篇博客再细细讲述...博文来自:pointer_y的博客

  主要考察:直接插入排序、冒泡排序、简单选择排序三种常见排序方法解决上述问题的思想:1、直接插入排序的基本思想是:依次将待排序序列中的每一个记录插入到一个已排好序的序列中,直到全部记录都排好序。具体的...博文来自:faker369的博客

  一、排序的介绍1.排序的分类按照排序过程中所依据的原则的不同可以分类为:►插入排序:直接插入排序希尔排序►交换排序:冒泡排序快速排序►选择排序:简单选择排序堆排序►归并排序►基数排序2.排序算法比较 ...博文来自:海吹的技术博客

http://duchtech.com/tongliansuanfa/384.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有