当前位置:首页 » 数据结构练习题 » 正文

数据结构-排序-练习题

1884 人参与  2018年09月10日 21:49  分类 : 数据结构练习题  评论

1选择题

(1)直接插入排序算法的时间复杂度为(     )

A.O(N)  B.O(1)    C.O(N2)    D.O(LOGN)

(2)下列排序方法中,从平均时间而言最佳的是(    )

A.快速    B.希尔    C.基数    D.归并

(3)下列是稳定的排序方法的(   )

A.快速    B.希尔    C.堆    D.基数

(4)所需辅助空间为O(N)的排序方法为(    )

A.快速    B.希尔    C.基数    D.归并

(5)如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列,用(    )方法最快。

   A.起泡排序

   B.快速排序

   C.简单选择排序

   D.堆排序

(6)下列选项中,(    )需要的附加存储开销最大。

   A.快速排序

   B.堆排序

   C.归并排序

   D.插入排序

参考答案: (1 C    (2 A     (3 D    (4D     (5C    (6)C

2选择排序的基本思想是什么?给定初始关键字 [49 38 65 97 76 13 27 49],请写出具体排序过程及程序实现。

基本思想:

①初始状态:无序区为R[1..n],有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
优点:稳定,比较次数与冒泡排序一样;
缺点:相对之下还是慢。

初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 76 76]
第六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最后排序结果 13 27 38 49 49 76 76 97

参考代码如下:

#include <iostream>
using namespace std;
void main()
{
int i,j,k,t;
int R[8]={49,38,65,97,76,13,27,49};
for(i=0;i<7;i++)
{
k=i;
for(j=i+1;j<8;j++)
if(R[j]<R[k])
k=j;
if(k!=i)
{

t=R[j];R[j]=R[k];R[k]=t;

}
}
for(i=0;i<8;i++)
cout<<R<<endl;
}

3描述 493827673987快速排序的过程

下面是具体算法步骤:

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;

2)以第一个数组元素作为关键数据,赋值给X,即 X=A[0];

3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,让该值与X交换(找到就行.找到后i大小不变);

4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,让该值与X交换(找到就行.找到后j大小不变);

5)重复第3、4步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)

下面是排序结果:

49      38   65    97    76    13      27     

27    38    13      49     76    97       65     49

13     27     38     49    65      76     97

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=355

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!