希尔排序、简单选择排序和快速排序是不是稳定的排序方法？试分别

[问答题]

希尔排序、简单选择排序和快速排序是不是稳定的排序方法？试分别举例说明。

随遇而安e

希尔排序(shell)

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

选择排序

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

快速排序

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

发表于 2019-09-28 17:01:06 回复(0)

JaimeWonj

希尔排序，快速排序不是稳定的排序方法；简单选择排序稳定性的判断得看其实现方式，如果用数组实现即，数组实现选择最小值后需要替换未排序数组的第一个值，这是不稳定的。如果使用链表实现，选择最小值之后直接插入在未排序数组第一个值前，这样是稳定的。一般来说，简单选择排序是用数组实现，故是不稳定的排序算法。

希尔排序：

3 _2 2 4

2 _2 3 4

快速排序：

3 _2 4 2

2 _2 3 4

选择排序：

_3 3 2

2 3 _3

编辑于 2019-09-28 14:59:58 回复(0)

提交观点

问题信息

排序

上传者：城市里的养猫者

难度：

2条回答 4收藏 3889浏览

希尔排序、简单选择排序和快速排序是不是稳定的排序方法？试分别

问题信息

热门推荐

相关试题