若对一个已经排好序的序列进行排序,在下列4种方法中,哪种方法比较好?
A.冒泡法
B.直接选择法
C.直接插入法
D.归并法
A.冒泡法
B.直接选择法
C.直接插入法
D.归并法
若对一个已经排好了序的序列进行排序,在下列4种方法中,哪一种方法比较好?
A.冒泡法
B.直接选择法
C.直接插入法
D.归并法
用下列4种排序方法,对一个已排好序(由小到大)的序列进行排序(由小到大),哪种方法最好?
A.冒泡排序
B.直接选择排序
C.直接插入排序
D.归并排序
(1)这种排序方法结束的条件是什么?
(2)写出奇偶交换排序的算法。
(3)当待排序排序码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换排序过程中的排序码比较次数是多少?
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i一1
个整数已经排好序,将第i个整数依次和第i.,i-2,…个整数进行比较,找到应该插入
的位置。现采用插入排序算法对6个整数{5 2,4,6,1,3}进行从小到大排序,则需要进行
(31)次整数之间的比较。对于该排序算法,输入数据具有(32)特点时,对整数进
行从小到大排序,所需的比较次数最多。
A.9
B.10
C.12
D.13
(32)A.从小到大
B.从大到小
C.所有元素相同
D.随机分布
请帮忙给出每个问题的正确答案和分析,谢谢!
阅读下列函数说明和C代码,回答下面问题。
[说明]
冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时,只需1趟扫描,而数据初态为反序时,需进行n-1趟扫描。在冒泡排序中,一趟扫描有可能无数据交换,也有可能有一次或多次数据交换,在传统的冒泡排序算法及近年的一些改进的算法中[2,3],只记录一趟扫描有无数据交换的信息,对数据交换发生的位置信息则不予处理。为了充分利用这一信息,可以在一趟全局扫描中,对每一反序数据对进行局部冒泡排序处理,称之为局部冒泡排序。
局部冒泡排序的基本思想是:对于N个待排序数据组成的序列,在一趟从前向后扫描待排数据序列时,两两比较相邻数据,若反序则对后一个数据作一趟前向的局部冒泡排序,即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第—对数据对,若反序,对第2个数据向前冒泡,使前两个数据成为,有序序列;扫描第二对数据对,若反序,对第3个数据向前冒泡,使得前3个数据变成有序序列;……;扫描第i对数据对时,其前i个数据已成有序序列,若第i对数据对反序,则对第i+1个数据向前冒泡,使前i+1个数据成有序序列;……;依次类推,直至处理完第n-1对数据对。当扫描完第n-1对数据对后,N个待排序数据已成了有序序列,此时排序算法结束。该算法只对待排序列作局部的冒泡处理,局部冒泡算法的
名称由此得来。
以下为C语言设计的实现局部冒泡排序策略的算法,根据说明及算法代码回答问题1和问题2。
[变量说明]
define N=100 //排序的数据量
typedef struct{ //排序结点
int key;
info datatype;
......
}node;
node SortData[N]; //待排序的数据组
node类型为待排序的记录(或称结点)。数组SortData[]为待排序记录的全体称为一个文件。key是作为排序依据的字段,称为排序码。datatype是与具体问题有关的数据类型。下面是用C语言实现的排序函数,参数R[]为待排序数组,n是待排序数组的维数,Finish为完成标志。
[算法代码]
void Part-BubbleSort (node R[], int n)
{
int=0 ; //定义向前局部冒泡排序的循环变量
//暂时结点,存放交换数据
node tempnode;
for (int i=0;i<n-1;i++) ;
if (R[i].key>R[i+1].key)
{
(1)
while ((2) )
{
tempnode=R[j] ;
(3)
R[j-1]=tempnode ;
Finish=false ;
(4)
} // end while
} // end if
} // end for
} // end function
阅读下列函数说明和C代码,将应填入(n)处的字句写在的对应栏内。
A.9
B.10
C.12
D.13
inciude<stdio.h> inciude<stdlib.h> define MAX 65536 void merge(int arr[],int p,int q,int r) { int *left, *right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) { perror("malloc error"); exit(1); } for(i=0;i<n1;i++){ left[i]=arr[p+i]; } left[i]=MAX; for(i=0; i<n2; i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0; j=0; for(k=p; (1) ; k++) { if(left[i]> right[j]) { (2) ; j++; }else { arr[k]=left[i]; i++; } } } void mergeSort(int arr[],int begin,int end){ int mid; if((3) ){ mid=(begin+end)/2; mergeSort(arr,begin,mid); (4) ; merge(arr,begin,mid,end); } }
【问题1】 根据以上说明和C代码,填充1-4。 【问题2】 根据题干说明和以上C代码,算法采用了(5)算法设计策略。 分析时间复杂度时,列出其递归式位(6),解出渐进时间复杂度为(7)(用O符号表示)。空间复杂度为(8)(用O符号表示)。 【问题3】 两个长度分别为n1和n2的已经排好序的子数组进行归并,根据上述C代码,则元素之间比较次数为(9)。
A.一个表的不同字段可设置为不同的字体
B.在“开始”选项卡中的“高级”下拉菜单中“按窗体筛选”功能可以排序
C.筛选和排好序的表数据不能被保存
D.可在数据表视图中删除字段和记录,删除后不能被恢复