排序习题文档格式.docx
- 文档编号:8510914
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:14
- 大小:103.64KB
排序习题文档格式.docx
《排序习题文档格式.docx》由会员分享,可在线阅读,更多相关《排序习题文档格式.docx(14页珍藏版)》请在冰点文库上搜索。
B、堆排序
C、冒泡排序
D、快速排序
例题2、
写出下列算法的时间复杂度。
(1)冒泡排序;
(2)选择排序;
(3)插入排序;
(4)二分插入排序;
(5)快速排序;
(6)堆排序;
(7)归并排序
写出希尔排序算法程序,并说明最坏的情况下需要进行多少次的比较和交换。
程序略,需要O(n^2)次的比较
设要将序列(Q,
H,
C,
Y,
P,
A,
M,
S,
R,
D,
F,
X)中的关键码按字母序的升序重新排列,则:
冒泡排序一趟扫描的结果是
Q,
X
Y
;
初始步长为4的希尔(shell)排序一趟的结果是
H,M,
Y
二路归并排序一趟扫描的结果是
Y,A,
快速排序一趟扫描的结果是
Y,X
堆排序初始建堆的结果是
Y,P,
。
在插入和选择排序中,若初始数据基本正序,则选用
插入排序(到尾部)
若初始数据基本反序,则选用
选择排序
下述几种排序方法中,平均查找长度(ASL)最小的是
A.
插入排序
B.快速排序
C.
归并排序
D.
选择排序
对于整数序列100,99,98,…3,2,1,如果将它完全倒过来,分别用冒泡排序,它们的比较次数和交换次数各是多少?
答:
冒泡排序的比较和交换次数将最大,都是1+2+…+n-1=n(n-1)/2=50×
99=4545次。
把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,不能申请额外的空间。
事实上,这道题放到冒泡排序这里不知道是不是特别合适,只是有一种解法是类似冒泡的思想,如下解法一
解法一、
每次遇到大写字母就往后冒,最后结果即为所求
[cpp]
viewplaincopy
1.#include
<
stdio.h>
2.#include
string.h>
3.//题目以及要求:
把一个字符串的大写字母放到字符串的后面,
4.//各个字符的相对位置不变,不能申请额外的空间。
5.//判断是不是大写字母
6.int
isUpperAlpha(char
c){
7.if(c
>
=
'
A'
&
c
Z'
){
8.return
1;
9.}
10.return
0;
11.}
12.//交换两个字母
13.void
swap(char
*a,
char
*b){
14.char
temp
*a;
15.*a
*b;
16.*b
temp;
17.}
18.char
*
mySort(char
*arr,
int
len){
19.if(arr
==
NULL
||
len
0){
20.return
NULL;
21.}
22.int
i
0,
j
k
23.for(i
len;
i++){
24.for(j
-
1
j--){
25.if(isUpperAlpha(arr[j])){
26.for(k
j;
k++){
27.swap(&
arr[k],
arr[k
+
1]);
28.}
29.break;
30.}
31.//遍历完了字符数组,但是没发现大写字母,所以没必要再遍历下去
32.if(j
0
!
isUpperAlpha(arr[j])){
33.//结束;
34.
return
arr;
35.}
36.}
37.}
38.//over:
39.return
40.}
41.int
main(){
42.char
arr[]
"
aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc"
;
43.printf("
%s\n"
mySort(arr,
strlen(arr)));
44.return
45.}
解法二。
步骤如下
1、两个指针p1和p2,从后往前扫描
2、p1遇到一个小写字母时停下,
p2遇到大写字母时停下,两者所指向的char交换
3、p1,
p2同时往前一格
代码如下:
3.//判断是不是大写字母
4.int
5.if(c
6.return
7.}
10.//交换两个字母
11.void
12.char
13.*a
14.*b
15.}
16.char
Reorder(char
17.if(arr
18.return
19.}
20.int
*p1
21.int
*p2
22.While(p1<
arr+len
p2<
arr+len){
23.While(
isUpperAlpha(*p1)
24.P1++;
25.}
26.While(
isUpperAlpha(*p2)
27.P2++;
29.swap(p1,
p2)
31.//结束
32.return
33.}
34.int
35.char
36.printf("
Reorder(arr,
37.return
最小的k个数,输入n个整数,找出其中最下的k个数,例如输入4、5、1、6、2、7、3、8、1、2,输出最下的4个数,则输出1、1、2、2。
当然,博主也知道这题可以建大小为k的大顶堆,然后用堆的方法解决。
但是这个题目可也以仿照快速排序,运用partition函数进行求解,不过我们完整的快速排序分割后要递归地对前后两段继续进行分割,而这里我们需要做的是判定分割的位置,然后再确定对前段还是后段进行分割,所以只对单侧分割即可。
1.void
GetLeastNumbers_by_partition(int*
input,
n,
int*
output,
k)
2.{
3.
if(input
output
n
0)
4.
return;
5.
start
6.
end
7.
index
Partition(input,
start,
end);
8.
while(index
1)
9.
{
10.
if(index
11.
12.
13.
14.
}
15.
else
16.
17.
18.
19.
20.
21.
for(int
k;
++i)
22.
output[i]
input[i];
23.}
判断数组中出现超过一半的数字
当然,这道题很多人都见过,而且最通用的一种解法是数对对消的思路。
这里只是再给大家提供一种思路,快排partition的方法在很多地方都能使用,比如这题。
我们也可以选择合适的判定条件进行递归。
1.bool
g_bInputInvalid
false;
2.bool
CheckInvalidArray(int*
numbers,
length)
3.{
if(numbers
length
true;
g_bInputInvalid;
8.}
9.bool
CheckMoreThanHalf(int*
length,
number)
10.{
times
length;
if(numbers[i]
times++;
bool
isMoreThanHalf
if(times
2
23.
isMoreThanHalf;
24.}
25.int
MoreThanHalfNum_Solution1(int*
26.{
27.
if(CheckInvalidArray(numbers,
length))
28.
29.
middle
30.
31.
32.
Partition(numbers,
33.
middle)
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
result
numbers[middle];
47.
if(!
CheckMoreThanHalf(numbers,
result))
48.
49.
result;
50.}
例题3、
有一个由大小写组成的字符串,现在需要对他进行修改,将其中的所有小写字母排在大写字母的前面(不要求保持原顺序)
这题可能大家都能想到的方法是:
设置首尾两个指针,首指针向后移动寻找大写字母,尾指针向前移动需找小写字母,找到后都停下,交换。
之后继续移动,直至相遇。
这种方法在这里我就不做讨论写代码了。
但是这题也可以采用类似快排的partition。
这里使用从左往后扫描的方式。
字符串在调整的过程中可以分成两个部分:
已排好的小写字母部分、待调整的剩余部分。
用两个指针i和j,其中i指向待调整的剩余部分的第一个元素,用j指针遍历待调整的部分。
当j指向一个小写字母时,交换i和j所指的元素。
向前移动i、j,直到字符串末尾。
iostream>
2.using
namespace
std;
3.void
Proc(
*str
)
4.{
5.int
7.//移动指针i,
使其指向第一个大写字母
8.while(
str[i]
\0'
a'
z'
i++;
9.if(
11.//指针j遍历未处理的部分,找到第一个小写字母
12.for(
j=i;
str[j]
j++
13.{
14.if(
15.{
tmp
str[i];
17.str[i]
str[j];
18.str[j]
tmp;
19.i++;
20.}
22.}
24.int
main()
25.{
26.char
data[]
SONGjianGoodBest"
27.Proc(
data
);
28.return
29.}
30.例题1、
31.编写算法,从10亿个浮点数当中,选出其中最大的10000个。
典型的Top
K问题,用堆是最典型的思路。
建10000个数的小顶堆,然后将10亿个数依次读取,大于堆顶,则替换堆顶,做一次堆调整。
结束之后,小顶堆中存放的数即为所求。
代码如下(为了方便,这里直接使用了STL容器):
33.例题1、
34.题目输入一个数组,数组元素的大小在0->
999.999.999的范围内,元素个数为0-500000范围。
题目要求通过相邻的元素的交换,使得输入的数组变为有序,要求输出交换的次数
这题求解的其实就是一个逆序对。
我们回想一下归并排序的过程:
归并排序是用分治思想,分治模式在每一层递归上有三个步骤:
分解:
将n个元素分成个含n/2个元素的子序列。
解决:
用合并排序法对两个子序列递归的排序。
合并:
合并两个已排序的子序列已得到排序结果。
在归并排序算法中稍作修改,就可以在n
log
n的时间内求逆序对。
将数组A[1...size],划分为A[1...mid]
和
A[mid+1...size].那么逆序对数的个数为
f(1,
size)
mid)
f(mid+1,
s(1,
mid,
size),这里s(1,
size)代表左值在[1---mid]中,右值在[mid+1,
size]中的逆序对数。
由于两个子序列本身都已经排序,所以查找起来非常方便。
42.代码如下:
有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。
要求你按照query的频度排序。
1、hash映射:
顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。
这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
2、hash统计:
找一台内存在2G左右的机器,依次对用hash_map(query,
query_count)来统计每个query出现的次数。
注:
hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
3、堆/快速/归并排序:
利用快速/堆/归并排序按照出现次数进行排序。
将排序好的query和对应的query_cout输出到文件中。
这样得到了10个排好序的文件(记为)。
对这10个文件进行归并排序(内排序与外排序相结合)。
归并一个左右两边分别排好序的数组,空间复杂度要求O
(1)。
使用原地归并,能够让归并排序的空间复杂度降为O
(1),但是速度上会有一定程度的下降。
一年的全国高考考生人数为500
万,分数使用标准分,最低100
,最高900
,没有小数,你把这500
万元素的数组排个序。
对500W数据排序,如果基于比较的先进排序,平均比较次数为O(5000000*log5000000)≈1.112亿。
但是我们发现,这些数据都有特殊的条件:
100=<
score<
=900。
那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
创建801(900-100)个桶。
将每个考生的分数丢进f(score)=score-100的桶中。
这个过程从头到尾遍历一遍数据只需要500W次。
然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。
而且可以很容易的得到100分有***人,501分有***人。
实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。
所以桶排序有其局限性,适合元素值集合并不大的情况。
在一个文件中有
10G
个整数,乱序排列,要求找出中位数。
内存限制为
2G。
只写出思路即可(内存
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 习题