精华内容
下载资源
问答
  • 下列排序算法中,哪几个算法的时间复杂度与初始排序无关()
    2021-03-14 00:48:44

    直接插入排序:

    算法思想:将第i个记录插入到前面已经排好序的i - 1个记录中去。

    算法要点: 使用监视哨r[0]临时保存带插入记录

    从后往前查找应插入的位置

    查找与移动用同一循环完成

    算法时间复杂度:o(n^2)

    折半插入排序:

    算法思想:利用折半查找的思想找到需要插入的位置

    算法时间复杂度:o(n^2),虽然减少了查找插入位置的次数,但是移动元素的时间仍未改变

    希尔排序:

    算法思想:将待排序的关键字序列分成若干个较小的子序列,对子序列进行直接插入排序,使整个待排序序列排好序。

    算法时间复杂度:o(n^1.5)

    快速排序:

    算法思想:从待排序记录中选择一个记录为枢纽,设为K,将其余大于K的记录移动至K的后面,小于K的移动至前面,此过程称为一趟快速排序。当然就是对接下来的两个字表进行相同的操作,直到子表的长度不超过1

    算法时间复杂度:o(Knlog2n),K为常数因子,且在所有O(nlogn)复杂度中,快排的K值最小

    简单选择排序:

    算法思想:

    第一趟:从第一个记录开始,通过n-1次关键字比较,从n个记录中选出最小的并和第一个记录交换;

    第二趟:从第二个记录开始,通过n-2次关键字比较,从n -1个记录中选出最小的并和第二个记录交换;

    ...

    算法时间复杂度:o(n^2)

    堆排序:

    算法思想:将向量中存储的数据看成一棵完全二叉树,利用完全二叉树中双亲节点和孩子节点之间的内在关系选择关键字最小的记录。

    大根堆:各节点关键字满足:a[i] >= a[2i]并且a[i] >= a[2i + 1]

    小根堆:各节点关键字满足:a[i] <= a[2i]并且a[i] <= a[2i+1]

    算法时间复杂度:o(nlogn)

    归并排序:

    算法思想:设初始序列长度为n,将这n个序列看成n个有序的子序列,然后辆辆合并,得到一个ceil(n/2)长度为2的有序子序列。

    在此基础上再对长度为2 的有序子序列进行归并排序,得到若干长度为4的子序列,如此重复直到得到一个长度为n的有序子序列为止

    时间复杂度:o(nlogn)

    选堆快希不稳(稳定性) 选堆归基不变(时间复杂度的变化特性)

    更多相关内容
  • 如果排序结束后,a[0]可以保证一定在a[3]前头,也就是他们原有的顺序不变,那这种排序算法就是稳定的。(比如常见的冒泡排序、基数排序、插入排序、归并排序、桶排序、二叉树排序等都是稳定排序算法) 反之,如果...

     

    有两个6,a[0]和a[3]。排序结果就有两种可能

    如果排序结束后,a[0]可以保证一定在a[3]前头,也就是他们原有的顺序不变,那这种排序算法就是稳定的。(比如常见的冒泡排序、基数排序、插入排序、归并排序、桶排序、二叉树排序等都是稳定的排序算法)

    反之,如果不能保证原有顺序,这种算法就是不稳定的。(比如常见的选择排序,希尔排序,堆排序,快速排序等都是不稳定的排序算法)

    要证明一种排序算法不稳定,举出一组例子就OK了;但要证明算法稳定,就要对算法设计进行彻底分析了。

    注:本文转自【白话简述:排序算法的稳定性 (什么样的排序是不稳定的)

    展开全文
  • 稳定排序算法有哪些

    千次阅读 2020-10-03 09:09:56
    二、常见排序算法稳定性分析 1、堆排序稳定性分析 我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点,大顶堆要求父节点大于等于其 2 个子节点,小顶堆要求父节点小于等于其 2 个子节点。 在一个长为 n 的序列...

    一、不稳定排序算法有哪些

    1、堆排序

    2、希尔排序

    3、快速排序

    4、选择排序

     

    口诀:一堆(堆)希尔(希尔)(快速)(选择)

     

     

    二、常见排序算法稳定性分析

    1、堆排序稳定性分析

    我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点,大顶堆要求父节点大于等于其 2 个子节点,小顶堆要求父节点小于等于其 2 个子节点。

    在一个长为 n 的序列,堆排序的过程是从第 n/2 开始和其子节点共 3 个值选择最大(大顶堆)或者最小(小顶堆),这 3 个元素之间的选择当然不会破坏稳定性。

    但当为 n/2-1, n/2-2, ...1 这些个父节点选择元素时,就会破坏稳定性。

    有可能第 n/2 个父节点交换把后面一个元素交换过去了,而第 n/2-1 个父节点把后面一个相同的元素没有交换,那么这 2 个相同的元素之间的稳定性就被破坏了。

    所以,堆排序不是稳定的排序算法。

     

    2、希尔排序

    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;

    当元素基本有序时,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比 O(N^2) 好一些。

    由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,

    但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。

    所以 shell 排序是不稳定的排序算法。 

     

    3、快速排序

    快速排序有两个方向,左边的 i 下标一直往右走(当条件 a[i] <= a[center_index] 时),其中 center_index 是中枢元素的数组下标,一般取为数组第 0 个元素。

    而右边的 j 下标一直往左走(当 a[j] > a[center_index] 时)。

    如果 i 和 j 都走不动了,i <= j, 交换 a[i] 和 a[j],重复上面的过程,直到 i>j。交换 a[j] 和 a[center_index],完成一趟快速排序。

    在中枢元素和 a[j] 交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11 

    现在中枢元素 5 和 3(第 5 个元素,下标从 1 开始计)交换就会把元素 3 的稳定性打乱。

    所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和 a[j] 交换的时刻。 

     

    4、选择排序

    选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的,在剩余元素里面给第二个位置选择次小的,

    依次类推,直到第 n-1 个元素,第 n 个元素不用选择了,因为只剩下它一个最大的元素了。

    那么,在一趟选择时,如果当前锁定元素比后面一个元素大,而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面,那么交换后位置顺序显然改变了。

    举个例子:序列5 8 5 2 9, 我们知道第一趟选择第 1 个元素 5 会与 2 进行交换,那么原序列中两个5的相对先后顺序也就被破坏了。

    所以选择排序不是一个稳定的排序算法。 

     

    5、冒泡排序 

    冒泡排序就是把小的元素往前调(或者把大的元素往后调)。注意是相邻的两个元素进行比较,而且是否需要交换也发生在这两个元素之间。

    所以,如果两个元素相等,我想你是不会再无聊地把它们俩再交换一下。

    如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个元素相邻起来,最终也不会交换它俩的位置,所以相同元素经过排序后顺序并没有改变。

    所以冒泡排序是一种稳定排序算法。 

     

    6、插入排序

    插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有 1 个元素,也就是第一个元素(默认它有序)。

    比较是从有序序列的末尾开始,也就是把待插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面。

    否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的,那么把待插入的元素放在相等元素的后面。

    所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序仍是排好序后的顺序,所以插入排序是稳定的。 

     

    7、归并排序

    归并排序是把序列递归地分成短序列,递归出口是短序列只有 1 个元素(认为直接有序)或者 2 个序列(1 次比较和交换),

    然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。

    可以发现,在 1 个或 2 个元素时,1 个元素不会交换,2 个元素如果大小相等也没有人故意交换,这不会破坏稳定性。

    那么,在短的有序序列合并的过程中,稳定是是否受到破坏?

    没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。

    所以,归并排序也是稳定的排序算法。 

     

    8、基数排序

    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。

    有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序结果就是高优先级高的在前,高优先级相同的情况下低优先级高的在前。

    基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

    展开全文
  • 下面哪种排序算法是不稳定的() A.插入排序 B.冒泡排序 C.快速排序 D.归并排序 答案:C 现在分析一下常见的排序算法稳定性,每个都给出简单的理由。 (1)冒泡排序 ...

    (转自:https://www.nowcoder.com/questionTerminal/1ed2cf389c134a2ebc9d14ecdd8de3b0

    下面哪种排序算法是不稳定的()

    • A.插入排序
    • B.冒泡排序
    • C.快速排序
    • D.归并排序

    答案:C

     

    现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

       (1)冒泡排序

            冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

    (2)选择排序

          选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

    (3)插入排序
         插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    (4)快速排序
        快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

    (5)归并排序
        归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

    (6)基数排序
       基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

    (7)希尔排序(shell)
        希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

    (8)堆排序
       我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    总结:选堆希快不稳。

     

     

     

    展开全文
  • PAGE 实 验 报 告 课程名称 数据结构 实验名称 常用的内部排序算法 作者 育人 一实验目的 掌握常见的...2内容通过一个简单的菜单分别实现下列排序要求采用几组不同数据测试各排序算法的性能比较次数和移动次数及稳定
  • 1.时间复杂度为O(n^2)排序稳定性:原序列相同的值,在排好顺序之后,能够保证原来的相同的值相对顺序保持不变。在一个算法中,如果所有相同值,在排完序之后,值的顺序不会被打乱,那么这个算法就是稳定的。如果...
  • 排序算法稳定性 所谓稳定性是指待排序的序列有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2. 稳定性的定义 假定在待排序的记录序列,存在多个...
  • 存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列,r[i]仍在r[j]之前,则称这种排序算法稳定的;否则称为不稳定的。 ...
  • 常见排序算法的时间空间复杂度、稳定性比较 一、排序算法比较 注: 1、归并排序可以通过手摇算法将空间复杂度降到O(1),但是时间复杂度会提高。 2、 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数...
  • 1 如何评价、分析一个排序算法?很多语言、数据库都已经封装了关于排序算法的实现代码。所以我们学习排序算法目的更多的不是为了去实现这些代码,而是灵活的应用这些算法和解决更为复杂的问题,所以更重要的是学会...
  • 下列排序方法,不稳定的方法有 正确答案: C 你的答案: C (正确) 归并排序与基数排序 插进排序与希尔排序 堆排序与快速排序 选择排序与冒泡排序 添加笔记 收藏 纠错 这道题同:将一个从大...
  • 快速排序、希尔排序不是稳定排序算法,而冒泡排序、直接插入排序是稳定排序算法。 (1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。...
  • 排序算法之分治排序

    2020-01-18 22:40:57
    归并排序是基于分治法实现的。归并排序将待排序的元素序列分为两个长度相等的子序列,为每一个子序列排序,然后再将它们合并成一...归并排序时稳定排序算法,但是由于空间复杂度为O(n)因此不是原地排序算法。 算...
  • 算法 时间复杂度 空间复杂度       稳定性           关联性        最好          最差        平均 ...
  • 2. 在下列排序方法,不稳定的方法有() A. 归并排序与基数排序 B. 插进排序与希尔排序 C. 堆排序与快进排序 D. 选择排序与冒泡排序 答:C 3. 一个递归算法包括() A. 递归部分 B. 终止条件和递归部分 C. 迭代...
  • 目录写在前面参考源码1.选择排序特点算法步骤复杂度改进2.冒泡排序特点算法步骤复杂度最好情况最坏情况改进3....本文主要写了七种常见排序算法:选择排序、冒泡排序、插入排序、希尔排序、归并排序、快速排序、
  • 在后续数据结构与算法的编码过程中都要使用到递归,比如DFS深度优先,二叉树前后序遍历等。 1. 概念 程序调用自身的编程技巧称为递归( recursion),所有的递归问题都可以使用递推公式来表示。构成递归需具备的...
  • 排序也叫排序算法,排序是将一组数据,依指定的顺序进行排列的过程。 排序的分类: 1)内部排序:指将需要处理的所有数据都加载到内部存储器进行排序。 2)外部排序:数据量过大,无法全部加载到内存,需要...
  • 时间复杂度为O(nlogn)的排序算法(归并排序、快速排序),比时间复杂度O(n²)的排序算法更适合大规模数据排序。归并排序归并排序的核心思想采用“分治思想”,将要排序的数组从中间分成前后两个部分,然后对前后两个...
  • 不知道有没有童鞋和我一样,总是记不住哪些排序方法是...1 北京理工大学2005一、10 (1分)】排序算法稳定性是指( )。A.经过排序之后,能使值相同的数据保持原顺序的相对位置不变 B.经过排序之后,能使值相同的数据保持
  • 排序算法 目录排序算法一、概念二、插入排序1、直接插入排序2、希尔排序三、交换排序1、冒泡排序2、快速排序四、选择排序1、简单选择排序五、归并排序1、2-路归并排序六、各种排序方法的比较1、性能比较2、选择排序...
  • 八大排序,三大查找是《数据结构》当中非常基础的知识点,在这里为了复习顺带总结了一下常见的八种排序算法。 常见的八大排序算法,他们之间关系如下:     排序算法.png   他们的性能比较:     ...
  • 1、冒泡排序 时间复杂度:O(n^2) 基本思想:相邻的元素两两进行比较,反序则交换,这样每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序。 代码实现如下: public class BubbleSort { /** * 冒泡...
  • 排序算法-递归排序

    2019-08-14 00:50:27
    归并排序是一种稳定排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并 实现 把长度为n的输入序列分成两个...
  • 排序算法-----归并排序算法 详解及实现(C++版)

    千次阅读 多人点赞 2019-04-22 14:03:27
    算法描述 ...首先,归并排序是一种稳定排序,所谓“稳定”,是指给定的待排序列如果含有若干个相等的元素,在排序后,相等的元素之间的相对位置不会被改变。如:原始序列{5a,3a,4,2,6,1,3b,3c,7,5b...
  • 排序算法及其稳定性排序算法排序算法稳定性 排序算法 排序算法:一种能将一串数据依照特定的顺序进行排列的算法。 排序算法稳定排序算法稳定性:稳定排序算法会让原本有相等key值的记录维持相对次序。 如果一个...
  • 常见排序算法稳定性分析和结论

    万次阅读 多人点赞 2010-05-31 12:26:00
    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些...
  • 这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些...
  • 排序算法稳定性判断(既稳定的还是不稳定的) 大白解释:对于一个序列{5,6,4,4,1,2,3}的七个数字,你会发现第三个和第四个都是'4',没错,这里为方便叙述,计为4(1)和4(2),且记住4(1)领先于4(2)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,057
精华内容 5,622
关键字:

下列排序算法中,稳定的是