算法导论读书笔记(6)
本章主要探讨的问题是中位数和顺序统计量,基本是讨论从一个集合中选择最小元素和最大元素的问题。由这个基本的问题再上升到查找第i个顺序统计量(Order Statistic)[该集合中第i小的元素] 名词解释:
Median(中位数):
<p align="center"> 
</p>
顺序统计量 In statistics, the _k_th order statistic of a statistical sample is equal to its _k_th-smallest value。
输入:一个包含n个(互异)数的集合A和一个整数i,i<=i<=n. 输出:元素x∈A，且A中恰好有i-1个其他元素小于它. 最直接的办法就是采用一种排序算法先对集合A进行排序，然后输出第i个元素即可。可以采用前面讲到的归并排序、堆排序和快速排序，运行时间为O(nlgn)。接下来书中由浅入深的讲如何在线性时间内解决这个问题。
- 最小值和最大值 伪代码:
MINIMUM(A) min = A[1] for i = 2 to A.length if min > A[i] min = A[i] return min
可以依据n-1的次数进行替换出来，最大值相似。
- 同时找到最大值和最小值:
其实只需要3(n/2)次比较久可以同时找到最小值和最大值，将他们进行成对比较，具体是记录已知的最小值和最大值，首先将输入的元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较，这样每对两个元素共需要3次比较。
- 图解:
代码:代码思想比较简单，直接copy了一个上来~原博主网站
1 #include
2 #include
3
4 //return max and min value by pointer
5 void get_max_min(int *datas,int length,int* ptrmax,int* ptrmin)
6 {
7 int i,maxtmp,mintmp;
8 //judge length is even or odd
9 if(length %2 == 0)
10 {
11 if(datas[0] > datas[1])
12 {
13 *ptrmax = datas[0];
14 *ptrmin = datas[1];
15 }
16 else
17 {
18 *ptrmax = datas[1];
19 *ptrmin = datas[0];
20 }
21 }
22 else
23 {
24 *ptrmax = datas[0];
25 *ptrmin = datas[0];
26 }
27 for(i=2;i<length;i+=2)
28 {
29 if(datas[i] > datas[i+1])
30 {
31 maxtmp = datas[i];
32 mintmp = datas[i+1];
33 }
34 else
35 {
36 maxtmp = datas[i+1];
37 mintmp = datas[i];
38 }
39 if(*ptrmax < maxtmp)
40 *ptrmax = maxtmp;
41 if(*ptrmin > mintmp)
42 *ptrmin = mintmp;
43 }
44 }
45
46 int main()
47 {
48 int max,min;
49 int i;
50 int datas[6] = {35,20,12,44,2,25};
51 get_max_min(datas,6,&max,&min);
52 printf("All elements in set are:n");
53 for(i=0;i<6;++i)
54 printf("%d ",datas[i]);
55 putchar('n');
56 printf("max=%dtmin=%dn",max,min);
57 exit(0);
58 }
- 期望为线性的选择算法一般的选择问题似乎要比选择最大值和最小值要难，但是这两种问题的运行时间是相同的，都是θ(n)。书中介绍了采用分治算法解决一般的选择问题，其过程与快速排序过程中划分类似。每次划分集合可以确定一个元素的最终位置，根据这个位置可以判断是否是我们要求的第i小的元素。如果不是，那么我们只关心划分产出两个子部分中的其中一个，根据i的值来判断是前一个还是后一个，然后接着对子数组进行划分，重复此过程，直到找到第i个小的元素。划分可以采用随机划分，这样能够保证期望时间是θ(n)（假设所有元素是不同的）。
伪代码:
1 RANDOMIZED_SELECT(A,p,r,i)
2 if p==r
3 then return A[p]
4 q = RANDOMIZED_PARTITION(A,p,r)
5 k = q-p+1;
6 if i==k
7 then return A[q]
8 else if i<k
9 then return RANDOMIZED_SELECT(A,p,q-1,i)
10 else
11 return RANDOMIZED_SELECT(A,p,q-1,i-k)
图示:
Enjoy Reading This Article?
Here are some more articles you might like to read next: