精华内容
下载资源
问答
  • 常见排序算法及其稳定性总结
    2021-01-17 13:07:29

    什么是排序算法稳定性?

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的。

    常见排序算法介绍

    插入排序

    通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

    具体实现算法(python)如下图:

    时间复杂度:平均 O(n^2) 最优 O(n) 最差 O(n^2)

    空间复杂度:O(1)

    是否稳定性算法:是

    选择排序

    在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    具体实现算法(python)如下图:

    时间复杂度:平均 O(n^2) 最优 O(n^2) 最差 O(n^2)

    空间复杂度:O(1)

    是否稳定排序算法:是(在判断用>=时,非稳定)

    冒泡排序

    重复走访要排序的序列,两两比较顺序错误就交换,依此类推,直到走完要排序序列,这时最大(最小)数浮动到数列末尾。

    具体算法实现(python)如下图:

    时间复杂度:平均 O(n^2) 最优 O(n^2) 最差 O(n^2)

    空间复杂度:O(1)

    是否稳定排序算法:是

    快速排序

    又称划分交换排序。快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。

    步骤为:

    挑选基准值:从数列中挑出一个元素,称为“基准”(pivot)。

    分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。

    递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

    具体算法实现(python)如下图:

    时间复杂度:平均 O(nlogn) 最优 O(nlogn) 最差O(n^2)

    空间复杂度:O(logn) - 递归堆栈

    是否稳定排序算法:否 (如:[ 4, 2, 3, 2] -> [2, 2, 3, 4])这里的 4 - 2 交换,导致原有的 2、2排序被打乱。

    堆排序

    新建堆然后从堆中逐条取出元素。

    具体算法实现(python)如下图:

    时间复杂度:平均 O(nlogn) 最优 O(nlogn) 最差 O(nlogn)

    空间复杂度:O(logn) - 递归堆栈

    是否稳定排序算法:否

    其它

    完全二叉树:完全二叉树的根节点到倒数第二层节点满足完美二叉树,最后一层节点可以不完全填充,但满足靠左对齐。

    堆:一种树状数据结构,需要满足如下性质:

    1. 堆中的某个节点的值总是大于等于或小于等于其父节点的值;

    2. 堆总是一颗完全二叉树;

    归并排序

    建立在归并操作基础上的一种有效排序方式,采用分治法:

    1、分割:递归地把当前序列平均分割成两半。

    2、集成:将上一步得到的有序子序列集成到一起(归并)。

    具体算法实现(python)如下图:

    时间复杂度:平均 O(nlogn) 最优 O(nlogn) 最差 O(nlogn)

    空间复杂度:O(logn)

    是否稳定性算法: 是

    其它

    归并操作:将两个有序集合合并成一个有序集合。

    希尔排序

    也称递减增量排序算法,是插入排序的一种更高效的改进版本。它是基于插入排序的一下两点性质改进点:

    1、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率

    2、插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

    即通过指定步长排序,使得原有序列变得尽可能有序,从而使得最后一步的插入排序的效率极大提升,从而使得总排序时间高效。

    具体算法实现(python,这里使用的递归 n/2 的步长)如下图:

    时间复杂度:平均 O(nlogn) 最差 O(n^2)

    空间复杂度:O(1)

    是否稳定算法:是(上述代码实现是,有些版本可能不是)

    实现代码:

    更多相关内容
  • 常见排序算法的稳定性分析

    千次阅读 2021-01-17 13:07:29
    一、不稳定排序算法有哪些1、堆排序2、希尔排序3、快速排序4、选择排序口诀:一堆(堆)希尔(希尔)快(快速)选(选择)二、常见排序算法稳定性分析1、堆排序稳定性分析我们知道堆的结构是节点i的孩子为 2*i 和 2*i+1 节点...

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

    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、基数排序

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

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

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

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

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

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

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

    千次阅读 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

    展开全文
  • 侧重点还是在通过遍历或来选择出最值.而冒泡排序就是通过不停交换相邻元素得出最大值,快速排序也在不停交换元素使序列一步步接近有序.侧重在交换)面对这以多排序算法你可能郁闷着要自己排序时用哪种...
  • //联系人:石虎QQ:1224614774昵称:嗡嘛呢叭咪哄QQ群:807236138 群称:iOS 技术交流学习群排序图表:一、插入排序每次将一个待排序的数据,跟前面已经有序的序列的数字一一比较找到自己合适的位置,插入到序列中,直到...
  • 1. 关于排序很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如:数据库脚本,如MSSql, MySql, NoSql 中按多个关键词的升序或降序...
  • 如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。 (2)选择排序 选择排序是给每个位置选择当前元素...
  • 通俗的说就是一数里面排序,有两个相同的数A和B,排序之前A在B前面,排序之后B在A前面,这就是快排的不稳定性。 再看一个比较极端的例子 数组中全是相同的数 全是 1 1 1 1 1 1 1 1 1 1 1 1 1 1 那么i,j从两次扫一...
  • 稳定性的含义:不稳定性是指在原始序列中相等的如果元素按照a1 a2 a3…的顺序排列时,排序之后相等元素的原相对位置改变,比如a3跑到a1前面去了 快速排序过程中:在j运动的时候,j的最终落点要么在i左边,要么在i...
  • 举例:如果初始数组是。 6,5,4,3,2,1 第一次冒泡:索引一开始在0处。6 > 5交换 ,索引变为1,6 大于4 交换,依次,6 大于3交换,6 大于2 交换,6 大于1交换。得到5,4,3,2,1,6 第二次冒泡因为已经...
  • 选择排序介绍: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的...排序算法的稳定性排序前2个相等的数其在序列的前...
  • 排序算法——堆排序

    千次阅读 2019-07-22 14:48:18
    在介绍堆排序之前我们首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无序的数字进行调整,使其按照从大到小或者从小大到的顺序有序排列。既然知道了堆排序的作用了,那么有...
  • js堆排序算法

    2021-11-18 17:24:47
    大顶堆举例 首先其为一个完全二叉树,且其每个节点的值都大于或者等于其左右孩子节点的值。 完全二叉树从上到下,从左到右依次编号,就可以将其进行顺序存储,我们从根节点开始,从0开始编号,存入数组如下: ...
  • 几种排序算法的稳定性分析

    千次阅读 多人点赞 2019-06-25 12:07:02
    为什么要对排序算法提出稳定性的要求?   简单的举个小例子:比如我们班一次期末考试,分高的在前面,对于分数相同的学生的排名需要借助上次考试结果,上次分数高的在前面,那么这个时候就要使用稳定排序。 ...
  • 堆排序、快速排序

    2018-03-19 14:26:05
    排序算法之堆排序 堆排序是基于完全二叉树的排序算法,即二叉树的除最后一层外每一层都达到容纳结点的最大值。最后一层从左至右依次排列。堆排序引入了另一种算法设计技巧,使用一种我们称为“堆”的数据结构来进行...
  • 排序算法稳定性

    2021-10-18 21:27:43
    排序算法的稳定性是要看具体的算法实现,比如一般情况下,直接选择排序,快速排序,希尔排序,堆排序都不是稳定排序算法,基数排序,计数排序,归并排序,插入排序,冒泡排序都是稳定排序算法。 快速排序:A = {2, ...
  • 今天给大家带来的是排序算法中的堆排序,这种排序跟二叉树相关。 我采用图解方式讲解,争取写透彻。话不多说,开始! 思维导图: 堆排序导图 1,堆排序概念 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种...
  • 数据结构中各种排序算法的稳定性比较

    万次阅读 多人点赞 2018-07-05 16:27:46
    堆排序&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (1和2是属于选择排序) 3.直接插入排序 4.希尔排序&nbsp;&nbsp;&nbsp;&nbsp; (3和4属于插入排序,有时把改进后的直接...
  • 各种排序算法稳定性比较

    千次阅读 2017-03-11 15:19:34
    堆排序 (1和2是属于选择排序) 3.直接插入排序 4.希尔排序 (3和4属于插入排序,有时把改进后的直接插入排序叫做二分插入) 5.冒泡排序 6.快速排序 (5和6属于交换排序.交换排序顾名思义是不停的交换数据位置....
  • 快速排序、堆排序、归并排序比较

    千次阅读 2017-12-28 20:55:00
    对于排序算法的稳定性指标,原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。快速排序的最直接竞争者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是
  • 排序算法:堆排序

    2018-12-16 21:30:20
        堆排序是一种选择排序。     选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 二、算法思想     堆排序是利用堆的性质进行的一种选择...
  • 十大排序算法复杂度及稳定性属性表 图片名词解释: n: 数据规模 k: “桶”的个数 In-place: 占用常数内存,不占用额外内存 Out-place: 占用额外内存 1、冒泡排序 冒泡排序算法的原理如下: a. 比较相邻的元素。...
  • 排序算法总结(选择、冒泡、插入、归并、快排、堆排序、桶排序、希尔排序、基数排序、计数排序)选择排序冒泡排序插入排序归并排序快速排序堆排序希尔排序基数排序计数排序算法性能比较(时间复杂度、空间复杂度及...
  • 堆排序是利用堆这种数据结构二设计的一种排序算法,堆排序是一种选择排序,他的最好最坏,平均复杂度都为O(nlogn), 它也是不稳定排序 堆是具有一下性质的完全二叉树:每个节点的值都大于或者等于其左右孩子节点的值,...
  • 戳蓝字“CSDN云计算”关注我们哦!作者 |CoderJed责编 | 阿秃1. 图示过程大根的性质:顶的数一定是所有元素的最大值任何一颗子树的根元素一定是该子树的最大元素某节点的左...
  • 堆排序

    2017-10-11 17:08:03
    堆的概念要点算法分析  堆排序算法的总体情况  时间复杂度  算法稳定性完整参考代码  JAVA版本参考资料相关阅读 堆的概念 在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。 堆是一棵顺序存储的完全...
  • 排序算法的稳定性 排序算法相信大部分同学都非常熟悉,也是必备知识点。但我也相信,有相当一部分同学被问到**哪些排序算法的稳定的?**这个问题时,还是一脸懵逼。然后开始百度,取找类似这样的表(此处举例,如有...
  • 常见的排序方法,详细图解,代码,测试结果。插入类排序:直接插入排序、希尔排序;交换类排序:冒泡排序、快速排序;选择类排序:简单选择排序、堆排序;归并类排序:递归和非递归形式的归并排序。
  • 排序算法的稳定性

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,563
精华内容 5,025
热门标签
关键字:

堆排序稳定性举例