简单排序算法的稳定性的问题

试题:
用某排序方法对一元素序列进行非递减排序时,若该方法可保证在排序前后排序码相同者的相对位置不变,则称该排序方法是稳定的。简单选择排序法排序方法是不稳定的,()可以说明这个性质。
A.21 48 21* 63 17

B.17 21 21* 48 63
C.63 21 48 21* 17

D.21* 17 48 63 21

3个回答

正确答案给的是 D 。我觉得答案应该是A。
有高手能帮忙解释一下么?

自己顶一个,在线等答案。

简单选择排序是从数据底部开始选择,注意这一点,答案应该就是A

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
排序算法(python):--排序算法的稳定性
排序算法(python):–排序算法的稳定性
排序算法稳定性
摘自百度百科,排序算法稳定性 概述 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。 判断方法: 对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法
排序算法的稳定性
排序算法的稳定性是指序列在排序后是否能保持相对的位置顺序,如序列(2,1,1),用快速排序算法后,我们将key=2,然后从右边开始进行选择比key小的值,即下标为2的1,然后进行交换,交换后的序列为(1,1,2),这样下标为2的1就跑到下标为1的1前面去了,这样的话就导致了他俩的相对位置发生了变化,像这样的排序算法就是不稳定的,排序算法中,稳定性稳定的算法有:冒泡排序,选择排序,插入排序,不稳定的
稳定性排序算法
冒插搞基 1.冒泡 2.插入 3.归并 4.基数排序
排序算法(稳定性&&时空复杂度&&稳定性)
先上图 稳定性 值一样的2个树,再排序过后的相对位置是否改变 意义: 如果是单纯的数字排序,稳定性没有意义。 如果排序的内存是复杂对象的多个数字属性,并且这些数字属性是有意义的,则需要用到稳定行算法。 例如;排序的对象是一组书,他们是按价格从高到低排序的。如今要求按销量排序,并排序过程中同销量的书保持价格从高到低的排序,此时则用到稳定性排序。(如果没有保持初始排序条件的话,稳定性算法也毫无意...
排序算法的稳定性及其意义
稳定性的定义       假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。 判断方法 对于不稳定的排序算法,只要举出一个实例,即可说明它的不稳定性;而对于稳定的排序算法,必须对算法进行分析从而得到稳定的特性。需
排序算法番外篇 算法的稳定性
定义: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,d=r,且排序前d在r之前,而在排序后的序列中,d仍在r之前,则称这种排序算法是稳定的;否则称为不稳定的。 通常情况: 堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 但是,对于不稳
排序算法稳定性分析
分析一下常见的排序算法的稳定性,每个都给出简单的理由。 冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。 ...
冒泡排序算法、时间复杂度和稳定性
冒泡排序 冒泡排序一般是我们学习排序算法时第一个接触的算法,下面来介绍一下冒泡排序。 算法原理 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一步,最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 算法分析 ...
关于排序算法稳定性的疑惑
[code=csharp]rn int [] a=6,2,2,1,5rn //冒泡排序(稳定)rn public static void BubbleSort(int[] a, ref int count)rn rn int n = a.Length - 1;rn int i, j;rn int tmp;rn bool isChange;rn for (i = 0; i < n; i++)rn rn isChange = false;rn for (j = 0; j < n - i; j++)rn rn if (a[j] > a[j + 1])//若果条件改成a[j]>=a[j+1] 就算相邻的两个数相等位置也会发生变化rn rn tmp = a[j];rn a[j] = a[j + 1];rn a[j + 1] = tmp;rn isChange = true;rn rn count++;rn rn if (!isChange)rn rn return;rn rnrn rn return;rn rn //直接选择排序(不稳定)rn public void Dir_Choose(int[] A, int n) rn rn int k, t;rn for (int i = 0; i < n - 1; i++)rn rn k = i;rn for (int j = i + 1; j < n; j++)rn rn if (A[j] < A[k]) k = j;rn rn if (k != i)rn rn t = A[i];rn A[i] = A[k];rn A[k] = t;rn rn rn rn[/code]rnrn问rn1、若果冒泡条件改成a[j]>=a[j+1] 相等的两个数的位置也会发生变化,怎么冒泡排序还是稳定的呢?rn2、这里的选择排序,相等的两个数明显没有发生位置变化,怎么选择排序是不稳定的呢?
排序算法稳定性的好处
排序算法稳定性概念: 在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中 r[i] = r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。  选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, 而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 ...
归并排序算法、时间复杂度和稳定性
归并排序 算法原理 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法分析 排序的思想就是将元素无限拆分,直到无可拆分为止,再将拆分的元素两两按序合并。 归并排序的原理可以通过下面这张图看清楚: 代码实现 /** * @Title: mergeSort ...
理解排序算法中的稳定性
排序算法中的稳定它只表示两个值相同的元素在排序前后是否有位置变化。如果前后位置变化,则排序算法是不稳定的,否则是稳定的。稳定性的定义符合常理,两个值相同的元素无需再次交换位置,交换位置是做了一次无用功。 比如快排中,待排序数组为5,7,7,1,1。那么若以数组中第一元素做为换分依据,第一次划结果为1,1,5,7,7。但是(从左往右)第一个7和第二个1交换,第二个7和第一个1交换,所以交换后1和1
各种排序算法的复杂度和稳定性
参考《天勤高分笔记-数据结构》一书中常见的排序算法整理 高清图:http://t.cn/RE0bvzX PDF下载点击:http://download.csdn.net/download/u012104219/10268468
排序算法的稳定性、时间和空间复杂度
排序算法的依据——关键字排序的稳定性当待排序记录的关键字均不相同时,排序结果是唯一的,否则排序结果不唯一。若存在多个关键字相同的记录,经过排序后,这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;否则称这种排序方法是不稳定的。 稳定的排序(sort) 时间复杂度 空间复杂度 气泡排序(bubble) 最差、平均都是O(n
几种排序算法的稳定性分析
稳定指的是什么? &nbsp; 稳定排序是指原来相等的两个元素前后相对位置在排序后依然不变。 &nbsp; 为什么要对排序算法提出稳定性的要求? &nbsp; 简单的举个小例子:比如我们班一次期末考试,分高的在前面,对于分数相同的学生的排名需要借助上次考试结果,上次分数高的在前面,那么这个时候就要使用稳定排序。 又比如,我们需要对学生先进行年龄排名,然后再根据身高排名,身高相同的,要求年龄大的在前...
排序算法:稳定性,时间复杂度,空间复杂度
排序是十分常用的算法,所以来一起看以下几种排序: 稳定性的定义:若两个数相等,那么排序之后,两个数字的相对位置保持不变 时间复杂度:对排序数据的操作次数 空间复杂度:算法在执行时所需要存储空间的大小 冒泡排序的基本思想:依次比较,相邻是逆序的就交换,经过多次比较,最终得到有序的序列,如下图 ...
排序算法的稳定性 以及 代表
1、稳定性定义        通俗地讲,排序前两个相等的数其在序列的前后位置顺序,在排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。 2、稳定性的应用场景 举个例子: 假如发奖学金,排在前三个的分别获一、二、三等奖,结果一排序把原来并列第二名的排成第三名了,他估计不会乐意。  3、典型排序算法的稳定性 ...
什么是排序算法的稳定性
排序算法的稳定性,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。    稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其
数据结构之内部排序性能比较
内部排序方法 最优复杂度 最坏复杂度 平均复杂度 空间复杂度 稳定性 插入排序 O(n) O(n2n^2) O(n2n^2) O(1) 稳定 折半插入 O(n) O(n2n^2) O(n2n^2) O(1) 稳定 希尔排序 O(n^1.5) O(1) 不稳定 冒泡排序 O(n) O(n2n^2)
排序算法的稳定性和不稳定性
七大排序算法的稳定性和不稳定性,先看这里点击打开链接,先给出结果:    选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法 具体待我整理。
各种排序算法的稳定性
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 ////////////////////// 首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。      其
排序算法时间复杂度和稳定性
速查表
排序算法 及其稳定性解释
排序算法的稳定性是指在待排序的序列中,存在多个相同的元素,若经过排序后这些元素的相对词序保持不变,即Xm=Xn,排序前m在n前,排序后m依然在n前,则称此时的排序算法是稳定的。下面针对常见的排序算法做个简单的介绍。 稳定排序算法:冒泡排序、插入排序、归并排序、基数排序 不稳定排序算法:选择排序、快速排序、希尔排序、堆排序
排序算法的稳定性总结
1.首先我们来看看插入排序,从第2个元素开始,把每个元素依次插入前面有序的序列中。 因为只有小于前面的元素时,才进行插入和移动操作,所以不会改变相同元素的相对顺序。 所以该算法是稳定,但是如果把a[j]>a[i]改为a[j]>=a[i]那就是不稳定的了。//直接插入排序 void InsertSort(int a[],int n){ for(int i=1;i<n;i++){
排序算法的稳定性和时间复杂度小结
小排序算法的稳定性和时间复杂度
算法 排序算法的稳定性
排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。 当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。然而,...
排序专题(1)——排序算法与排序算法稳定性
排序算法及其稳定性排序算法排序算法稳定性 排序算法 排序算法:一种能将一串数据依照特定的顺序进行排列的算法。 排序算法稳定性 排序算法稳定性:稳定排序算法会让原本有相等key值的记录维持相对次序。 如果一个排序算法是稳定的,当有两个相等key值的纪录R和S,且在原本的列表中R出现在S之前,则在排序过的列表中依旧会保持R在S之前的状态。以下面的数对排序举例, (4, 1) (3, 1) (3, 7)...
排序算法总结(应用场景,稳定性及时间复杂度)
排序总结: 排序算法的应用场景: (1)从平均时间性能而言,快速排序最佳,其所需时间是最省,但快速排序在最坏的情况下的时间性能不如堆排序和归并排序。 (2)当空间大资源足,要求时间效率时,可采用归并排序。 (3)堆排序虽然较之快排慢一些,但特别适合海量数据的排序。如在100万个数据里面找出前1000大的数据。可以用建立一个小顶堆存储1000元素。 (4)当序列中的记录基本有序或n值较小,...
排序算法: 时间复杂度、空间复杂度、稳定性总结
参考: http://bigocheatsheet.com/
各种排序算法的稳定性和时间复杂度小结
各种排序算法的稳定性和时间复杂度小结,包含各种排序算法,对找工作,做项目都有帮助
各种排序算法的稳定性和时间复杂度总结
各种排序算法的稳定性和时间复杂度总结。希望大家能有所收获。
文章标题 排序算法稳定性总结
稳定性总结 思想:2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。 好处:(1)稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。(2)对基于比较的排序算法而言,元素交换的次数可能会少一些。这两个好处是在网上找到的。**如何改进:算法导论习题8.3-2说:如果对于不稳定的算法进行改进,使得那些不稳
十大排序算法时间复杂度和稳定性对比
相关术语: 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面; 内排序:所有排序操作都在内存中完成;外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行; 时间复杂度: 一个算法执行所耗费的时间。空间复杂度: 运行完一个程序所需内存的大小。 ...
常用排序算法的时间复杂度和空间复杂度及稳定性
一、时间复杂度 二、空间复杂度   冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引) 快速排序空间复杂度为O(logn)~O(n)(就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为logn,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归...
实用:python直接插入排序(稳定性排序算法)
m_list = [[1,2,3,4,5,6,7,8,9], [9,8,7,6,5,4,3,2,1], [3,5,4,1,2,6,7,8,9], [1,1,1,1,1,1,1,1,1] ] lst = [0] + m_list[2] print(lst) n = len(lst) for i in range(2,n): lst[0] = lst[...
排序算法时间复杂度、空间复杂度、稳定性整理
涉及排序算法包括:简单选择排序、直接插入排序、希尔排序、归并排序、冒泡排序、快速排序、堆排序、基数排序 时间复杂度:快些以nlogn的速度归队 此句表示时间复杂度为O(nlogn)的排序,“快”表示快速排序,“些”表示希尔排序,“归”表示归并排序,“队”表示堆排序,其他排序均为O(n²),特殊的基数排序为O(nlog(r)m)。 注:快排的最坏情为O(n²),此时待排序的序列为正序或者逆序。
排序算法时间复杂度,稳定性综合一览表
原始图片来自于国外某人的博客 写道 http://singaraju.com/blogs/gautam/files/2009/09/sorting1.jpg             比较次数       交换次数   空间 类型 稳定性statble 适用范围   最优 平均 ...
【每日算法】排序算法总结(复杂度&稳定性)
一、插入排序:稳定,时间复杂度O(n^2)想象你在打扑克牌,一开始左手是空的,接着右手开始从桌上摸牌,并将其插入到左手的一把牌中的正确位置上。为了找到这个正确位置,我们需要从右到左将它与手中的牌比较,直到找到合适的位置插入。整个过程的特点是,左手的牌是排好序的了。详见: 插入排序二、选择排序:不稳定,时间复杂度O(n^2)每趟从未排序部分选出最小的元素,然后通过交换将其添加到已排序部分中。详见:
常见排序算法的复杂度以及稳定性
序号 排序类别 时间复杂度 空间复杂度 稳定性 1 插入排序 O(n^2) 1 √ 2 冒泡排序 O(n^2) 1 √ 3 归并排序 O(nlogn) O(n) √ 4
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池