请教一道排序题
用某种排序方法对关键序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则所采用的排序方法是___________
A 选择排序 B 希尔排序 C 归并排序 D 快速排序
希望能得到较详细的解答。thanks
[247 byte] By [
boyh] at [2008-2-14]
好像是快速排序法还是希尔?我记不清了。不过方法我知道
方法是选择第一个数作为标准,从最后一个元素开始同标准比较到比标准小就交换标志和该元素位置,再从前第二个元素开始比较,比标准大就交换,一直到没有交换就产生了两个两个子序列,一个所有元素都大于标准(在标准的右部),一个都小于标准(在左),
再对子序列按同样的方法处理,到没有位置交换时排序结束
快速排序,方法就如 xdspower() 说的,你再找本<<数据结构>>的书看一下
能否以得到第一次序列为例,具体说明一下。thanks
boyh at 2007-10-19 >

用某种排序方法对关键序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
第一次以25为标准,经过比较和移动比25小的全到了左别,比25大的全到了右边
然后左边以20为标准,又用相同的方法排序右边以47为标准排序得到
15,20,21,25,35,27,47,68,84
最后再分解
还是相同的方法得到 15,20,21,25,27,35,47,68,84
快速排序就是选定一个基准,以此基准将当前无序区划分为左右两个较小的子区间,使左区间全小于基准,右区间全大于基准
然后再递归调用,对左右子区间进行排序
直到得出结果
It is obviously quicksort!
我不理解的是第一次以25为标准,比25大移到25右边,以右边为例,其顺序为何是47,27,68,35,84,而不是其他,可否详细说明一下是如何移到右边的.thanks
boyh at 2007-10-19 >

25,84,21,47,15,27,68,35,20
第一次的过程可以看做是这样的:
1、25从最右开始比较:25>20 交换--> 20,84,21,47,15,27,68,35,25
2、25从最左开始比较:20<25 --> 不变
84>25 交换--> 20,25,21,47,15,27,68,35,84
3、重复步骤1:遇到比25大的数,则不变;遇到比25小的数,则交换 -->
20,15,21,47,25,27,68,35,84
4、重复步骤2:遇到比25小的数,则不变;遇到比25大的数,则交换 -->
20,15,21,25,47,27,68,35,84
得到第一次过程的结果。
47,27,68,35,84,的时候,第一次以47为准,从84开始向左找比47小的,就是35,把35移到47的位置,就是35 27 68 ( )84 暂时不放47,再从35向右找比47大的就是68,这时有35 27 ()68 84 ,68放在第一次的()处。同样再84开始向左找比47小的,没有了,则第一次排序结束,35 27 47 68 84 同样以上的步骤在重复就行了
47,27,68,35,84,的时候,第一次以47为准,从84开始向左找比47小的,就是35,把35移到47的位置,就是35 27 68 ( )84 暂时不放47,再从35向右找比47大的就是68,这时有35 27 ()68 84 ,68放在第一次的()处。同样再84开始向左找比47小的,没有了,则第一次排序结束,35 27 47 68 84 同样以上的步骤在重复就行了
47,27,68,35,84,的时候,第一次以47为准,从84开始向左找比47小的,就是35,把35移到47的位置,就是35 27 68 ( )84 暂时不放47,再从35向右找比47大的就是68,这时有35 27 ()68 84 ,68放在第一次的()处。同样再84开始向左找比47小的,没有了,则第一次排序结束,35 27 47 68 84 同样以上的步骤在重复就行了