深度学习
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 (4)D (5)C (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> |
3、描述 49,38,27,67,39,87快速排序的过程
下面是具体算法步骤:
设要排序的数组是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