首页 > 试题广场 > 设一组初始记录关键字序列为(45,80,55,40,42,8
[单选题]
设一组初始记录关键字序列为(45,80,55,40,42,85), 则以第一个记录关键字45为基准而得到-一趟快速排序的结果是( )
  • 40,42,45,55,80,83
  • 42,40,45,80,85,88
  • 42,40,45,55,80,85
  • 42,40,45,85,55,80
推荐

答案:c
解析:
初始序列:(45,80,55,40,42,85)
①从右往左找出小于45的值
②将该值交换到45的位置
③交换后,从左往右找大于45的值
结果为:42,80,55,40,42,85

①从左往右找出大于45的值
②将该值交换到粗体42的位置
③交换后,从右往左找小于45的值
结果为:42,80,55,40,80,85、

①从右往左找小于45的值
②将该值交换到粗体80的位置
③交换后,从左往右找大于45的值
结果为:42,40,55,40,80,85

①从左往右找大于45的值
②交换该值到粗体40的位置
③交换后,从右往左找小于45的值
结果为:42,40,55,55,80,85

此时第一趟排序结束 ,将粗体55替换成45
最终排序结果为 :42,40,45,55,80,85

编辑于 2019-09-19 14:13:56 回复(0)
C。考察的是快速排序的过程。
快速排序选定基准元素后,有两种元素交换方法:双边循环单边循环
原序列:(45,80,55,40,42,85),结合选项考虑用的是双边循环
  1. 设置两个指针分别指向数列起始和结束位置,左指针代表小于基准元素的区域,反之右指针大于基准。
  2. 从右指针处开始元素遍历,如果遍历到大于基准元素的,继续向后遍历。如果小于基准元素的,将指针位置与基准交换。
第一次:从后往前 查找比45小的数 42比45小 他俩交换位置:42,80,55,40,45,85
第二次:从前往后 找比45大的数 80>45 交换位置:42,45,55,40,80,85
第三次:从后往前 找比45小的数 40<45 交换位置:42,40,55,45,80,85
第四次:从前往后 找比45大的数 55>45 交换位置:42,40,4555,80,85
所以选C。
发表于 2019-09-19 07:41:34 回复(0)

C
42,40,45,55,80,85

发表于 2019-09-18 16:33:03 回复(0)