循这些标准。所以就是 D 了。
答案:D
9. 体育课的铃声响了,同学们都陆续地奔向操场,按老师的要求从高到矮站成一排。每
个同学按顺序来到操场时,都从排尾走到排头,找到第一个比自己高的同学,并站在他的
后面。这种站队的方法类似于( )算法。
A. 快速排序
B. 插入排序
C. 冒泡排序
D. 归并排序
解析:此题考查学员对各种排序思想的掌握。
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割
成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按此方
法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有
序序列。
假设要排序的数组是 A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关
键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为
一躺快速排序。一躺快速排序的算法是:
1)、设置两个变量 I、J,排序开始的时候 I:=1,J:=N;
2)以第一个数组元素作为关键数据,赋值给 X,即 X:=A[1];
3)、从 J 开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于 X 的值,两
者交换;
4)、从 I 开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于 X 的值,两
者交换;
5)、重复第 3、4 步,直到 I=J;
插入排序的基本思想:每次将一个待排序的记录按其关键字的大小插入到前面已经排好序
的子文件的适当位置,直到 全部的记录插入完成为止。
冒泡排序的基本思想是:将被排序的记录数组 R[1..n]垂直排列,每个记录 R[i]看作是
重量为 R[i].key 的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组 R:凡
扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡
都是轻者在上,重者在下为止。
归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文
件合并成一个有序的文件。
两路归并算法基本思路
设 两 个 有 序 的 子 文 件 ( 相 当 于 输 入 堆 ) 放 在 同 一 向 量 中 相 邻 的 位 置 上 :
R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量 R1(相当于输出堆)中,待合
并完成后将 R1 复制回 R[low..high]中。
合并过程中,设置 i,j 和 p 三个指针,其初值分别指向这三个记录区的起始位置。合
并时依次比较 R[i]和 R[j]的关键字,取关键字较小的记录复制到 R1[p]中,然后将被复制记
录的指针 i 或 j 加 1,以及指向复制位置的指针 p 加 1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将
另一非空的子文件中剩余记录依次复制到 R1 中即可。
评论1
最新资源