堆排序稳定性举例 |
您所在的位置:网站首页 › 堆排序是不稳定的排序方法 › 堆排序稳定性举例 |
一、不稳定排序算法有哪些 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、快速排序 快速 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |