精华内容
下载资源
问答
  • 稳定排序哪
    千次阅读
    2019-08-25 10:38:00

    基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序

    更多相关内容
  • 12种排序及时间复杂度稳定性: 计数排序 基数排序 冒泡 插入 折半插入 归并 锦标赛 快速 希尔 桶排序 选择排序排序
  • 种排序算法的稳定

    千次阅读 2021-01-17 13:07:27
    如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。(2)选择排序选择排序是给每个位置选择当前元素...

    (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个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

    文献参考:https://blog.csdn.net/next_page_lv/article/details/48929487

    展开全文
  • 稳定排序和不稳定排序

    千次阅读 2021-01-17 13:07:27
    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些...

    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些不是稳定的,做起来应该可以轻松搞定。本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。

    首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

    其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。

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

    (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个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

    展开全文
  • 8常用排序算法稳定性分析

    千次阅读 2019-02-09 18:45:08
    选择排序、快速排序、希尔排序、堆排序不是稳定排序算法 冒泡排序、插入排序、归并排序和基数排序都是稳定排序算法。 【1】为什么要区分排序算法的稳定性? 排序算法的稳定性通俗地讲就是能保证排序前两个相等的...

    选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法
    冒泡排序、插入排序、归并排序和基数排序都是稳定的排序算法。

    【1】为什么要区分排序算法的稳定性?

    排序算法的稳定性通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。

    再简单具体一点,如果A i == A jAi 原来在 Aj 位置前,排序后 Ai仍然是在 Aj 位置前。

    下面我们分析一下稳定性的好处:

    ① 如果排序算法是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所利用。

    基数排序就是这样,先按低位排序,逐次按高位排序,那么,低位相同的数据元素其先后位置顺序即使在高位也相同时是不会改变的。

    ② 学习排序原理时,可能编的程序里面要排序的元素都是简单类型,实际上真正应用时,可能是对一个复杂类型(自定义类型)的数组排序,

    而排序的键值仅仅只是这个元素中的一个属性,对于一个简单类型,数字值就是其全部意义,即使交换了也看不出什么不同。

    但是,对于复杂类型,交换的话可能就会使原本不应该交换的元素交换了。比如:一个“学生”数组,欲按照年龄排序,“学生”这个对象不仅含有“年龄”,还有其它很多属性。

    假使原数组是把学号作为主键由小到大进行的数据整理。而稳定的排序会保证比较时如果两个学生年龄相同,一定不会交换。

    那也就意味着尽管是对“年龄”进行了排序,但是学号顺序仍然是由小到大的要求。


    【2】8种常见排序算法稳定性分析

    ① 冒泡排序

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

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

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

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


    ② 选择排序

    选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的,在剩余元素里面给第二个位置选择次小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。

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

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

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


    ③ 插入排序

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

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

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

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


    ④ 快速排序

    快速排序有两个方向,左边的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]交换的时刻。


    ⑤ 归并排序

    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。

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

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

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

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


    ⑥ 基数排序

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

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

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


    ⑦ 希尔排序

    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快。当元素基本有序时,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(N^2)好一些。

    由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。

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


    ⑧ 堆排序

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

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

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

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

    参考博文:
    常见排序算法稳定性分析

    展开全文
  • 种排序算法的稳定性分析

    千次阅读 多人点赞 2019-06-25 12:07:02
    稳定排序是指原来相等的两个元素前后相对位置在排序后依然不变。   为什么要对排序算法提出稳定性的要求?   简单的举个小例子:比如我们班一次期末考试,分高的在前面,对于分数相同的学生的排名需要...
  • 排序算法问题:稳定排序与不稳定排序

    万次阅读 多人点赞 2019-05-26 12:52:02
    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,...
  • 基于比较的三种稳定排序算法

    千次阅读 2019-12-04 18:14:02
    本文主要介绍七大常见基于...两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算法是具备稳定性的排序算法。 1.插入排序 基本原理: 每次选择无序区间的第一个元素,在有序区间内选...
  • 归并排序稳定排序

    千次阅读 2021-06-15 22:05:30
    归并排序稳定排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按...
  • 稳定排序与不稳定排序方法的分类和总结

    千次阅读 多人点赞 2019-09-21 14:03:41
    排序算法的稳定性是指排序前 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。简单来说就是,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。 排序算法如果是稳定的,那么从一个...
  • 常见排序算法的稳定性分析

    千次阅读 2021-01-17 13:07:29
    一、不稳定排序算法有哪些1、堆排序2、希尔排序3、快速排序4、选择排序口诀:一堆(堆)希尔(希尔)快(快速)选(选择)二、常见排序算法稳定性分析1、堆排序稳定性分析我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点...
  • 对于稳定排序 插入排序,归并排序(合并排序),冒泡排序,基数排序; 不稳定排序 快速排序,堆排序,选择排序 这些排序的介绍,以及简要说明稳定以及不稳定的原因。
  • 稳定排序与不稳定排序

    万次阅读 2018-07-17 11:20:18
    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些...
  • 插入排序及其稳定性介绍

    千次阅读 2021-04-05 20:38:17
    3.分析其稳定性 【问题解决】 1.插入排序算法实现代码: package algorithm; public class InsertionSort { public static void main(String[] args) { int[] arr= {9,4,3,1,3,7,8,6,2,5}; insertionSort...
  • 归并排序稳定性分析

    千次阅读 2021-05-29 10:38:51
    归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中,如果 A[p…m]和 A[m+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放...
  • 排序稳定性的意义

    千次阅读 2018-10-08 11:07:06
    首先,为什么会有排序算法稳定性的说法?只要能排好不就可以了吗? 看例子 第1行是数字2 记作 1 2 第2行是数字4 记作 2 4 第3行是数字2 记作 3 2 排序后的结果(如果看不懂命令的意思,参照这个博客) 那么引入...
  • 【算法】计数排序 + 各个排序算法的稳定

    千次阅读 多人点赞 2021-11-25 22:29:09
    之前介绍的排序算法: 【算法】插入排序——希尔排序+直接插入排序_Rinne’s blog-CSDN博客 【算法】选择排序——堆排序+直接选择排序_Rinne’s blog-CSDN博客 【算法】交换排序——快速排序+冒泡排序(更新了非...
  • 简单选择排序稳定

    千次阅读 2020-12-23 11:07:05
    稳定的简单选择排序
  • 哪些排序是不稳定的?稳定又意味着什么?

    万次阅读 多人点赞 2019-06-21 14:48:37
    对于排序稳定性的意义: 通俗地讲就是待排序的序列中有两元素相等,排序之后它们的先后顺序不变。例如:如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。 其次就是稳定性带来的好处: 我们平时自...
  • 【C++】稳定排序和不稳定排序

    千次阅读 2018-08-20 21:01:13
    这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些...
  • 选择排序是一个稳定排序算法吗?

    万次阅读 2020-06-28 09:30:05
    选择排序是一简单直观的排序算法,无论什么数据都是O(n^2)的时间复杂度。所以用到它的时候,数据规模越小越好。 算法步骤 从数组中找出最小的那个元素,然后与最开始的元素交换位置 忽略第一步中找到的最小元素,...
  • 8大排序算法的稳定和不稳定分析

    千次阅读 2020-06-12 11:48:38
    在笔试题时,可能会遇到一个关于常见排序算法稳定性判别的问题,往往还是多选。当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些不是稳定的,做起来应该可以轻松搞定。本文是针对老是记不住这个或者想...
  • 快速排序稳定性分析

    万次阅读 多人点赞 2019-04-20 11:39:05
    快速排序是一个不稳定排序算法,本文将着重分析该算法不稳定的原因所在。 首先,考虑下图中对一个关键字都为 1 的序列所进行的交换操作。 如图,交换前,枢纽元已放置在最后一个位置。图中,当遇到和...
  • 稳定排序算法有哪些

    千次阅读 2020-10-03 09:09:56
    1、堆排序稳定性分析 我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点,大顶堆要求父节点大于等于其 2 个子节点,小顶堆要求父节点小于等于其 2 个子节点。 在一个长为 n 的序列,堆排序的过程是从第 n/2 开始...
  • 选择排序(Selection sort)是一简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,直到全部待排序的数据元素排完。选择排序是不稳定排序...
  • 选择排序(每次选出未排序最小的和未排序首位置交换)、 快速排序(随机选取一个值为基准,把基准放到最前面或者最后面,这就决定你...这几个不是稳定排序算法, 冒泡排序、插入排序、归并排序(虽然和快排都是...
  • 冒泡排序及其稳定性介绍

    千次阅读 2021-04-05 19:41:29
    3.说明冒泡排序稳定性。 【问题解决】 1.冒泡排序实例代码: public class BubbleSort { public static void main(String[] args) { int[] arr= {9,4,1,3,7,8,6,2,5}; bubbleSort(arr); printIntArray...
  • 稳定排序与不稳定排序的定义

    千次阅读 2020-02-25 14:16:08
    如果队列中存在两个相等的数字排序过程中 这两个数字的先后顺序如果不会发生变化 就叫做稳定排序反之叫做不稳定 参考文章:稳定排序和不稳定排序. ...
  • 排序算法稳定性的好处

    千次阅读 2018-09-21 15:45:58
    排序算法稳定性概念: 在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中 r[i] = r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 225,423
精华内容 90,169
关键字:

哪种排序稳定