快速排序的问题对下列关键字序列用快速排序的方法进行排序时,速度最快的的情形是()A{21,25,5,17,9,23,30
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/13 14:35:23
快速排序的问题
对下列关键字序列用快速排序的方法进行排序时,速度最快的的情形是()
A{21,25,5,17,9,23,30} B{25,23,30,17,21,5,9}
C{21,9,17,30,25,23,5} D{5,9,17,21,23,25,30}
这个我知道原始序列有序性越强,快速排序的效率就越差.但怎么判断那个序列有序性强?可能这道题也不是完全靠有序性,
不好意思答案是A,您也许应该排序一下,这个我排完了,但没发现从选项上看到有什么简便算法. 序列是从小到大的. 大家不要忘了分成两股才算一趟排序.多趟才构成整个的快速排序.
lazysunboy 你说的跟我想的一样,答案太der了我感到,可他为什么会选第一个?(我持C的态度),他们对c的讲解很可笑.
对下列关键字序列用快速排序的方法进行排序时,速度最快的的情形是()
A{21,25,5,17,9,23,30} B{25,23,30,17,21,5,9}
C{21,9,17,30,25,23,5} D{5,9,17,21,23,25,30}
这个我知道原始序列有序性越强,快速排序的效率就越差.但怎么判断那个序列有序性强?可能这道题也不是完全靠有序性,
不好意思答案是A,您也许应该排序一下,这个我排完了,但没发现从选项上看到有什么简便算法. 序列是从小到大的. 大家不要忘了分成两股才算一趟排序.多趟才构成整个的快速排序.
lazysunboy 你说的跟我想的一样,答案太der了我感到,可他为什么会选第一个?(我持C的态度),他们对c的讲解很可笑.
这道题的话我不清楚是不是应该把每个选项的步骤给列下来,但是我很迷惑.
快速排序实际上是以每次都以当前数组的第一位作为基准作为比较的,所以说第一位的值的位置更靠中间(排序好的),二分法后就均匀,速度就会越快.
A选项第一次选择21将会换到17的位置,第一次变换后变为:
17,9,5,21,25,23,30
再进行一次变换,就已经排好序了
C选项同理,第一次选择将21换到30的位置,变换后变为:
5,9,17,21,25,23,30
A、C两选项第一次选择的比较次数和交换次数都相同,所以时间就看第二轮了
(17,9,5)和(5,9,17)谁快?应该是(5,9,17)快一步,因为(17,9,5)还要交换一步变成(5,9,17),然后再剩下(5,9),而(5,9,17)第一步不变化,然后剩下(9,17),两个剩下的时间(即5,9和9,17再比较一次且都是已排序的)肯定都是一样的.
所以时间就差在需要交换的一步上:
(17,9,5)->(5,9,17)->(5,9)+(17)第一步需要3步比较和一次交换;
(5,9,17)->(5,9,17)->(5)+(9,17)第一步需要3步比较无需交换;
所以选C
看了你的图,我补充下:
答案对A的解释在第一步上有误啊,怎么会变成(9,17,5,21,23,25,30)呢?
A选项第一次查找将会交换25和9的位置,9只能出现在第二位的.然后再交换21和17,只会变成17,9,5,21,25,23,30啊,答案有误!
另外对于其他答案,我认为,对于算法不仅仅是交换,比较也是要算时间的,快速排序在已经排序好的数列上花的时间是最大的,平方级
但是这些在规模较小的情况下因素太多了~
快速排序实际上是以每次都以当前数组的第一位作为基准作为比较的,所以说第一位的值的位置更靠中间(排序好的),二分法后就均匀,速度就会越快.
A选项第一次选择21将会换到17的位置,第一次变换后变为:
17,9,5,21,25,23,30
再进行一次变换,就已经排好序了
C选项同理,第一次选择将21换到30的位置,变换后变为:
5,9,17,21,25,23,30
A、C两选项第一次选择的比较次数和交换次数都相同,所以时间就看第二轮了
(17,9,5)和(5,9,17)谁快?应该是(5,9,17)快一步,因为(17,9,5)还要交换一步变成(5,9,17),然后再剩下(5,9),而(5,9,17)第一步不变化,然后剩下(9,17),两个剩下的时间(即5,9和9,17再比较一次且都是已排序的)肯定都是一样的.
所以时间就差在需要交换的一步上:
(17,9,5)->(5,9,17)->(5,9)+(17)第一步需要3步比较和一次交换;
(5,9,17)->(5,9,17)->(5)+(9,17)第一步需要3步比较无需交换;
所以选C
看了你的图,我补充下:
答案对A的解释在第一步上有误啊,怎么会变成(9,17,5,21,23,25,30)呢?
A选项第一次查找将会交换25和9的位置,9只能出现在第二位的.然后再交换21和17,只会变成17,9,5,21,25,23,30啊,答案有误!
另外对于其他答案,我认为,对于算法不仅仅是交换,比较也是要算时间的,快速排序在已经排序好的数列上花的时间是最大的,平方级
但是这些在规模较小的情况下因素太多了~
快速排序的问题对下列关键字序列用快速排序的方法进行排序时,速度最快的的情形是()A{21,25,5,17,9,23,30
2.给出利用快速排序方法对线性表(25,84,21,47,15,27,68,35,20)进行升序排序的序列变化情况.
在快速排序, 堆排序,归并排序中 哪个是最稳定的排序方法?
给定一个关键字序列(24,19,32,43,38,6,13,22),进行快速排序,扫描一趟后的结果是?
对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序,最省时间的算法是___________
采用快速排序算法,对关键字序列(28,56,78,60,12,25)按从小到大次序排序
用某种排序方法对序列(29,98,24,47,15,27,68,35,18)进行排序,记录序列的变化情况如下 18,15
对下列关键字序列(15,4,38,51,9,17,80,2)进行直接插入排序?
数据结构中堆排序,快速排序,归并排序排序的时间复杂度顺序快慢依次是什么?
一、实验目的:掌握常用的查找与排序算法.二、实验内容 1、用简单插入排序法,对关键字值序列为:9,2,
下列各个排序算法中,要求辅助空间最大的是 A.希尔排序法 B.快速排序法 C.堆排序法 D.二路归并排序法
用简单插入排序法,对关键字值序列:9,2,20,45,3,18按从小到大的顺序进行排列,试打印出每趟排序的结果.