首页 > 试题广场 >

下列哪些排序算法不是稳定的?

[不定项选择题]
下列哪些排序算法不是稳定的?
  • 快速排序
  • 冒泡排序
  • 选择排序
  • 归并排序
A C
先解释一下稳定性是什么东西:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 。
举个例子,如果原来序列是 1 2 3 3(*) 4,可以看到这里边有两个3,给第二个3做了一个*标记,如果排序之后序列是1 2 3(*) 3 4,虽然排序结果是正确的,但是原来两个3的相对位置发生了改变,所以这种排序就是不稳定的。

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

发表于 2017-03-03 17:59:13 回复(0)
发表于 2017-01-05 23:21:33 回复(0)
选择排序是从序列当中每次选择一个最优的元素放在序列的开始位置,此时发生了大范围的元素的交换,很显然是不稳定的。而归并和冒泡排序则是很稳定,因为交换只发生在相邻元素之间。
发表于 2021-08-03 19:14:02 回复(0)
首先,稳定性是指如果待排序数据中有多个相同的元素,如果在排序完后相同元素的顺序不发生改变,则为稳定的排序,否则为非稳定的排序。
A.快速排序就是利用切分算法依次确定n个元素的最终位置。所以,我们直接来分析切分算法。举例来说, 有待切分子数组: 5 8 3 7 3 9 7,切分元素为5,从后遍历得到第一个小于切分元素5的数据为3(index = 5),从前遍历得到第一个大于5的元素为8,交换3和8,这样,元素3的稳定性就被破坏了。

B.冒泡排序为依次从前往后与相邻值比较交换从而将未排序的最大值移至最后。如 9 8 6 9 0 ,当第一个9移至 8 6 9 9 0时,只要我们保证只有当前一个元素大于(而不是大于等于)下一个元素时才交换,就可保证排序的稳定性。

C.选择排序为每一次从第i个元素后面选择一个最小元素放入第i个位置.(i从0 到 n -1)。
举例 4 5 4 3,在第一轮交换中,我们找到最小元素3(index = 3),需要将其与第一个元素 4(indx = 1)。我们发现,当第i个元素和它后面的最小元素中间还存在 元素i 时将破坏元素i的稳定性  

D.归并排序同样是分治并合并两个有序子数组的过程。因此,和快速排序一样,我们只需要考察合并有序子数组的算法即可。 当合并有序子数组时,我们会利用辅助数组,每一次都将两个子数组中较小的元素放入即可辅助数组,直至全部放入。只要我们保证当遍历到当前两个子数组值相同时,先将第一个元素放入即可保证排序后的稳定性。所以,归并排序是稳定性。

最终:答案为A  C。
发表于 2017-01-06 13:58:50 回复(0)
学的别人的,不稳定的排序就是,快(快排)选(选择排序)堆(堆排序)希(希尔排序)。。
发表于 2019-04-25 19:59:01 回复(0)