精华内容
下载资源
问答
  • 2)空间复杂度(Space Complexity)是对一个算法在运行过程临时占用存储空间大小的量度。有算法需要占用临时工作单元数与解决问题规模n有关,它随着n增大而增大,当n较大时,将占用较多存储单元,例如快速...

    空间复杂度

    基本介绍
    1)类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。
    2)空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况
    3)在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

    展开全文
  • 基本数据结构中各种排序比较(时间复杂度,空间复杂度和稳定性) 插入排序   插入类的排序就好像是军训时来了一个迟到的同学,整个同学会“插入”到队伍的合适位置。 1.直接插入排序   每趟将一个新的关键字按照...

    基本数据结构中各种内部排序比较(时间复杂度,空间复杂度和稳定性)

    插入排序

      插入类的排序就好像是军训时来了一个迟到的同学,这个同学会“插入”到队伍的合适位置。
    1.直接插入排序
      每趟将一个新的关键字按照值的大小比较插入到已经有序的队伍中,直到所有的关键字都被插入有序序列。
    2.折半插入排序
      这里的插入方式和直接插入排序一样,区别在比较方法不一样,这里是用折半查找法来查找插入位置。与直接插入相比较,查找位置的效率大大增加,插入时移动次数都是一样的。
    3.希尔排序
      又叫做缩小增量排序,是将待排序列按照某种规则(增量)分成几个子序列,分别对这几个子序列进行直接插入排序,然后将增量减半,再分为几个子序列进行直接插入排序,当增量减少为1时,可以直接将其理解为直接插入排序,这时所得序列为有序序列。
      那直接用直接插入排序不就好了吗,为什么会用到希尔排序,举这样一个例子:7 9 8 5 4 0 6 2 3 1
    以增量5分割序列,我们将这个序列分为5个子序列:
    子1:7       0
    子2: 9       6
    子3:  8       2
    子4:   5       3
    子5:    4       1
    将子序列分别进行直接插入排序:
    子1:0       7
    子2: 6       9
    子3:  2       8
    子4:   3       5
    子5:    1       4
    得到序列:0 6 2 3 1 7 9 8 5 4
      不难看出大一点的数基本被排在了后面,虽然这是一个特例,但是每趟希尔排序都会使整个序列变得更有序,整体上是减少了直接插入排序移动次数,使排序效率增高。
    增量的选取注意:增量序列的最后一个值一定取1,增量序列中的值应尽量们没有除1之外的公因子。

    选择排序

      选择类排序的核心是“选择”,即每一趟排序都会选择出最大或最小的来放到队头或者队尾,就像军训中会让个子最小的站到队头,然后在其他人中再找到最小的,放在队头,直到最后一个,就得到一个有序序列。
    1.简单选择排序
      就像例子中讲的那样,简单选择排序就是选择其中最小(最大)的值,选择的关键就是和所有的值进行比较,比任何其他值都小的就是最小值(最大也一样),将其插入有序队列的队尾就可以了。
    2.堆排序
      堆是一种数据结构,可以将其看作是一棵完全二叉树,满足:任何一个非叶子结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小,叫做大顶堆(大根堆),反之,叫做小顶堆(小根堆)。一次堆排序就是将无序序列调整为符合堆定义的完全二叉树,然后将“最大”或者“最小”值与最后一个值交换位置,再进行下一次堆排序。这样每次堆排序的目的就是将无序序列中断最大(最小)值找出来。

    交换排序

      交换类排序的核心是“交换”,就像是军训时刚来的时候,队伍都是随便站的,这时教官会要求同学按身高排序,一个个子高的同学就会不停的和他身边的同学进行比较,交换位置直至合适他自己的位置。
      交换类排序和插入类排序的区别在于交换类排序每趟执行都会将一个元素放置到它最终的位置上去,而插入类排序一趟排序并不能确保一个关键字到达其最终位置,对于1,2,3,0,这样的最小元素最后插入的情况,整个序列没有任何一个关键字在最后一趟排序前到达其最终位置。
    1.冒泡排序
      冒泡就好像它自己的名字,在冒泡排序过程里,大元素好像石头一样逐渐沉底,小元素像气泡一样逐渐向上,但是每一次冒泡都会使一个元素放到它最终位置上去,冒泡排序的结束条件是一趟排序里面没有发生关键字的交换。
    冒泡排序就是两两比较和交换,以非递减排序为例,首先第一个元素和第二个比较,前面的大,就交换,否则不交换;接着比较第二个和第三个元素,以此类推,到最后一个元素为完成了一趟冒泡排序。
    2.快速排序
      快速排序是通过多次“划分”操作实现。和冒泡排序一样,快速排序的一次划分会将一个元素放在它最终位置上,虽然时间复杂度也有和其一样的排序算法,但同级别算法的基本操作执行次数多项式为X*nlog2n(X是系数),快速排序的X是最小的,所以是同级别中最好的,因此得名。快速排序是典型的以空间为代价减少时间,在其递归算法中需要用到栈的辅助。
      

    二路归并排序

      归并类排序就是将两个或者两个以上的有序序列合并成一个新的有序序列,这个例子不太好举,如果硬是拿之前的例子套的话,就像是队伍中前后两个人一组先排序,然后四个,然后八个,直到全部排好。算法上这是一种分而治之的过程,从宏观上看就是将队伍分成两部分,每部分再进行分治,这样每次总和时都会认为时两个有序序列的排序,但是微观上就是例子所举的那样,其实是子序列从多到少。这部分有疑问,建议看看算法书中的分治法。

    基数排序

      上面几种排序都是基于比较和交换,而基数排序是不基于比较的,它的思想是“多关键字排序”。就好像扑克牌有花色和数字,先按花色分堆,再按照A到K的顺序摘出来,就会得到有序序列。
      基数主要有两种实现方式:最高位优先(MSD)和最低位优先(LSD),最高位优先是先按最高位排成若干子序列,再对每个子序列按次高位排序;最低位优先不必分子序列,每次排序全体都会参与,不基于比较的,而是通过“分配”和“收集”,原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

    稳定性

      稳定性是指当待排序序列中有两个或两个以上相同的关键字时,排序前和排序后这些关键字的相对位置有没有改变,如果改变就说它不稳定,如果不改变就说它是稳定的。稳定性只是一个算法性质,并不能衡量一个算法的优劣。

    排序类型 平均时间复杂度 平均空间复杂度 稳定性 是否支持顺序存储和链式存储
    直接插入法 O(n2) O(1) 稳定 都支持
    折半插入法 O(n2) O(1) 稳定 顺序存储
    希尔排序 O(n2) O(1) 不稳定 顺序存储
    简单选择排序 O(n2) O(1) 不稳定 都支持
    堆排序 O(nlog2n) O(1) 不稳定 都支持
    冒泡排序 O(n2) O(1) 稳定 都支持
    快速排序 O(nlog2n) O(log2n) 不稳定 都支持
    二路归并排序 O(nlog2n) O(n) 稳定 都支持
    基数排序 O(d(n+rd)) O(rd) 稳定 都支持

    复习时部分总结,有错误欢迎指正,立改,谢谢!

    展开全文
  • 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程需要访问外存。 各种内部排序按所采用的基本思想(策略)可分为...

    原文链接

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

        各种内部排序按所采用的基本思想(策略)可分为:插入排序、交换排序、选择排序、归并排序和基数排序,它们的基本策略是:

    1、插入排序:依次将无序序列中的一个记录,按关键字值的大小插入到已排好序一个子序列的适当位置,直到所有的记录都插入为止。具体的方法有:直接插入、表插入、2-路插入和shell排序。

    2、交换排序:对于待排序记录序列中的记录,两两比较记录的关键字,并对反序的两个记录进行交换,直到整个序列中没有反序的记录偶对为止。具体的方法有:冒泡排序、快速排序。

    3、选择排序:不断地从待排序的记录序列中选取关键字最小的记录,放在已排好序的序列的最后,直到所有记录都被选取为止。具体的方法有:简单选择排序、堆排序。

    4、归并排序:利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并,直到合并为一个有序序列为止。

    5、基数排序:按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中,再按桶的编号依次将记录进行收集,最后得到一个有序序列。

       常见的内部排序算法有:插入排序(insertion sorting)、希尔排序(Shell Sort)、选择排序(Selection sort)、堆排序(Heapsort)、冒泡排序(Bubble Sort)、快速排序(quick sort)、归并排序(Merge sort)、基数排序(Radix sort)。

       下图列出了各种排序算法的时间复杂度、空间复杂度和稳定性情况。其中,空间复杂度仅列举了平均情况下的复杂度,由于希尔排序的时间复杂度依赖于增量函数,所以这里无法准确地给出其时间复杂度。


    ————————————————
    版权声明:本文为CSDN博主「官方全村的希望」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/qq_29720657/article/details/78399558

    展开全文
  • 各种排序算法时间复杂度比较 如下图: 相关术语解释: 稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然...空间复杂度:运行完一个程序所需内存的大小。 n: 数据规模 k: “桶”个数 In-place:不占用额外内存 O

    各种排序算法时间复杂度比较

    如下图:

    在这里插入图片描述

    相关术语解释:
    稳定:如果 a 原本在 b 前面,而 a=b,排序之后 a 仍然在 b 的前面;
    不稳定:如果 a 原本在 b 的前面,而 a=b,排序之后 a 可能会出现在 b 的后面;
    内排序:所有排序操作都在内存中完成;
    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度:运行完一个程序所需内存的大小。
    n: 数据规模
    k: “桶”的个数
    In-place:不占用额外内存
    Out-place: 占用额外内存

    展开全文
  • 数据结构之冒泡排序

    2020-09-22 23:32:43
    排序算法在排序过程消耗的内存可以通过其空间复杂度表现,特指空间复杂度O(1)的排序算法为原地排序。 冒泡排序(Buddle Sort)图解与原理冒泡排序的代码实现冒泡排序的复杂度分析冒泡排序的优化 图解与原理 冒泡...
  • 在刷面试题中的算法题经常出现时间复杂度O(n),空间复杂度O(1)很多时候不知道是什么意思 空间复杂度与时间复杂度是数据结构的复杂度,在现在储存设备越来越便宜的时代,时间复杂度是决定程序运行速度的重要因素 算法...
  • 堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据。我将用c++实现一个堆来简单分析一下。 堆排序的基本思想为: 1、升序...
  • 数据结构之桶排序

    千次阅读 2014-09-03 17:38:12
    /* * 桶排序 * 思路:将读入数据序列放入不同的桶, * 桶个数=数据中最大的数据+1;... * 空间复杂度O(N+M)N:代排序数据大小,M:桶个数. * 桶排序:用空间换时间. * 桶排序是稳定的排序算法。
  • #if 0 //各种排序算法实现以及时空复杂度等问题 #include<stdio.h> #include<stdbool.h> #include<malloc.h>.../***插入排序****/ ...//算法空间复杂度O(1) //查找总比较次数以及移动次数约为 n^2.
  • 数据结构排序总结

    2018-08-16 18:25:00
    数据结构排序总结 排序概念: 1,排序要素:稳定性(相同关键字时,相对顺序是否发生变化),时间复杂度,空间复杂度: 2,排序分类:内部排序(内排序适用于记录个数不很多小文件,计算在内存),外部排序...
  • 内部排序算法比较和应用 比较 注意图颜色对应 亮黄色框住代表特殊情况下时间复杂度,需要特别记忆。...其中快排适合初始序列无序情况,若初始序列基本有序,或者需要O(1)的空间复杂度,则不应选择快排
  • 排序 定义 对一序列对象根据某个关键字进行排序。 术语 稳定:如果a原本在b前面...空间复杂度:运行完一个程序所需内存的大小。 时间复杂度总结 n: 数据规模 k: “桶”个数 In-place: 占用常数内存,不占用额外
  • 数据结构排序

    2018-07-27 19:21:53
    1. 冒泡排序 ...以升序冒泡排序为例,冒泡排序就是要每趟排序过程通过两两比较相邻元素,将小数字放到前面,大数字放在后面。 空间复杂度:O(N) 时间复杂度:O(N^2) 稳定排序 void Swap...
  • 插入排序是算法是每次将1个待排序的记录按其关键字大小,插入到前面己排好序子序列,直到全部记录插入完成。 直接插入排序 空间复杂度:仅使用了常数个辅助单元,O(1)O(1)O(1) 时间复杂度:最好情况下为O(n)O(n...
  • 排序算法好坏衡量指标:时间效率(时间复杂度、比较次数),空间效率(空间复杂度、占内存辅助空间大小),稳定性(关键字值相等记录A和B在排序后先后次序不变则稳定) 内部排序概念:待排序记录都在内存。 ...
  • 一.常见排序算法 插入排序 1.直接插入排序 2.希尔排序 ...算法描述:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序有序序列,直到所有记录插入完为止,得到一个新有序序列 。 voi...
  • 排序算法总结 常用的排序算法对比 相关术语解释: 1)稳定:如果a原本在b前面,而a=b,排序之后a...6)空间复杂度:运行完一个程序所需内存的大小。 7)n: 数据规模 8)k: “桶”的个数 9)In-place: 不占用额外内存
  • 代码全部C语言实现,后续有机会补上 1.冒泡排序:思想是两两比较,每次选出一个相对最大数,直至所有数都完成排序...3.快速排序:随机从数组选择一个数作为参考,然后将剩余数据按比之大小分成左右两部分,递归执行以
  • 排序算法性能包括时间复杂度、空间复杂度和稳定性。后面给出每种算法思想、python3实现和性能分析。本文包括如下内容: 比较类排序 非比较类排序 leetcode题目解析 比较类排序 在比较类排序方法,又根据
  • ins @ngladc文末左下方阅读原文指向了本人博客链接,不含广告。...这样话,算时间复杂度和空间复杂度就很有问题。因此,我最近几天查阅了网上相关资料,并进行归纳和整理。开始我以为复制粘贴就行了,但是呢...
  • 将要排序的序列按照每个值的大小逐个插入到一个已经排好序有序序列,直到所有记录插完 特点: 元素集合越接近有序,直接排序效率越高 时间复杂度:O(N^2) 空间复杂度:O(1) 稳定性:稳定 画图说明:...
  • 数据结构排序总结1

    千次阅读 2012-05-20 14:55:37
    1.插入排序是一种简单直观的排序算法,其思想在于每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的合适位置,知道全部记录插入完成为止。一趟排序后,并没有是一个记录到达其最终位置,这是...
  • 排序(Bucket Sort): 首先将元素分在不同的桶中,再对每个桶中的元素排序排序的表现取决于数据的分布,也就是需要对不同的数据排序时采取不同的分桶策略 平均情况复杂度: O(n+k) 最坏情况时间复杂度: O(k * n^2)...
  • 数据结构研究数据之间关系 ...空间复杂度:是一个算法在运行过程临时占用存储空间大小的度量 时间复杂度:是一个算法在运行过程所需要计算工作量 时间复杂度是将输入值趋近无穷情况 比如: pub...
  • 因为每次合并都需要申请大小为 n 的临时数组用于保存合并之后的结果,所以空间复杂度为O(n)。 3、稳定性排序? 属于稳定排序算法。为了达到上述目的,只需要在合并时将前后两部分相同的元素中的属于前面部分的...
  • 一、常用排序算法对比 二、相关术语解释 稳定:如果a原本在b前面,而a=b,排序...空间复杂度:运行完一个程序所需内存的大小。 In-place: 不占用额外内存 Out-place: 占用额外内存 k: “桶”个数 n: 数据规模 .
  • 排序是根据(A)的大小重新安排各元素的顺序。A.关键字B.数组C....内排序是指在排序的整个过程,全部数据都在计算机的(A)完成的排序。A.内存B.外存C.内存和外存D.寄存器4.直接插入排序...

空空如也

空空如也

1 2 3 4 5
收藏数 82
精华内容 32
关键字:

数据结构中的排序空间复杂度大小排序

数据结构 订阅