1 #include <stdio.h> 2 #include <time.h> 3 #include <stdlib.h> 4 void swap(int* A,int i,int j) 5 { 6 int temp=A[i]; 7 A[i]=A[j]; 8 A[j]=temp; 9 } 10 int partition(int* A,int p,int r) 11 { 12 //pivot element 13 int x=A[r-1]; 14 int i=p-1,j=p; 15 for(;j!=r-1;++j) 16 { 17 if(A[j]<=x) 18 swap(A,++i,j); 19 } 20 swap(A,++i,r-1); 21 return i; 22 } 23 int randomized_partition(int* A,int p,int r) 24 { 25 srand((unsigned int)time(0)); 26 swap(A,rand()%r,r-1); 27 return partition(A,p,r); 28 } 29 int randomized_select(int* A,int p,int r,int select) 30 { 31 if(p==r-1) 32 return A[p]; 33 int q=randomized_partition(A,p,r); 34 int k=q-p+1; 35 if(k==select) 36 return A[q]; 37 else if(select<k) 38 return randomized_select(A,p,q,select); 39 else 40 return randomized_select(A,q+1,r,select-k); 41 } 42 int main(int argc, char **argv) 43 { 44 int A[30]; 45 int i=0; 46 printf("Original:\n"); 47 for (;i<30;i++) 48 { 49 A[i]=rand(); 50 printf("%d\t",A[i]); 51 } 52 int result=randomized_select(A,0,30,2); 53 printf("\nyour appointed number is %d\n",result); 54 return 0; 55 }
以上是期望线性时间选择指定顺序位数值的C实现…后面那个最坏线性时间的理论意义大于实际意义，主要是主元选择方法发生了变化…另外为毛上面的select也着色了啊？
exercises：
9.1-1 本题的意思应该是利用9.1部分学到的成对处理，如果n是偶数，那么按顺序划分成n/2对，然后求出smaller one，组成一个新数组；如果n是奇数，那就把最后一个单独做一组；递归以上过程，直至n=2，那么就求出了最小值。次小值一定与最小值比较过，树的高度是lgn，所以…
9.1-2 这个分析正文里面已经给出了…
9.2-1 只有q=p或者q=i时可能产生长度为0的数组，但是i<1和i>r是绝对不会出现的，所以不可能出现在长度为0的数组递归调用的情况。
9.2-2 概率题…忘了怎么做…
9.2-3 Randomized-Selected'(A,p,r,i)
while p≤r
do if p=r
then return A[p]
q←Randomized-Partition(A,p,r)
k←q-p+1
if k=i
then return A[q]
else if k>i
then r=q-1
else do p=q+1
i=i-k
9.2-4 最坏情况就是每次q都选中了数组中的极大值…
9.3-1 如果是每组7个元素：T(n)≤T($\lceil n/7 \rceil$)+T(5n/7+8)+O(n) 【4$\lceil /frac{1}{2}\lceil \frac{n}{7} \rceil -2 \rceil =\frac{2}{7}n-8】
可以用替换法证明其消耗仍然是Θ(n)，但是当每组只有3个元素的时候T(n)≤T($\lceil n/3 \rceil$)+T(2n/3+4)+O(n)，用递归树展开的方法可得下界是Θ(nlgn)。
9.3-2 大于中位数x的元素至少有3n/10-6个，代入n=140，得到36，而140/4=35，所以至少有n/4个元素小于x。
9.3-3 主元选择方法是用9.3提供的Select，而不是以前的随机选择。
9.3-5 主元选择直接用中位数这样就可以得到T(n)=T(n/2)+Θ(n)，线性时间成立（其实就是快排的最佳情况）
9.3-6 此题的意思不是太清楚…k分位数是吧n个元素分解成k个大小相等的集合的k-1个顺序统计量，但是我搞不清楚这里是否包括k本身，比如1 2 3的2分位数就是2，但是这是不包括2本身的…结果我搜了一下，网上的解法都是认为包括这个2的，换句话说，分别是n/k,2n/k...(k-1)n/k这几个顺序统计量。当然，存在k分位数的前提就是n mod k=0.想要将算法由O(nk)降低到O(nlgk)，
设t=n/k，首先用select算法找出分位数的中位数kt/2，对原序列以此中位数为主元进行划分，如果第i个k分位数的i<k/2，那么其对应的值存在于kt/2的左边，否则在右边，递归调用该算法直至找到所有的k中位数。参考这里。
9.3-7 求出中位数(O(n))，求出S中所有元素与该中位数的差的绝对值(O(n))，以该值为key对原序列进行计数排序(O(n))，取排序后的序列前k个数(O(1))。
9.3-8 如果X[i]恰好是两序列合并后的中位数，那么Y中必须有n-i个小于等于X[i]的数，换言之，必有Y[n-i]≤X[i]≤Y[n-i+1]成立。使用二分法搜索满足该条件的下标，如果X[i]小于Y[n-i]，那么X[i]只可能存在于右半边，否则在左半边；如果递归完成未找到符合条件的X[i]，则在Y中再次寻找满足X[n-i]≤Y[i]≤X[n-i+1]的Y[i]。
Median(X,Y)
n←length(X)
median←Find-Median(X,Y,n,1,n)
if median←not-found
then median←Find-Median(Y,X,n,1,n)
return median
Find-Median(A,B,n,low,high)
if low>high
then return not-found
else k←$\lfloor (low+high)/2 \rfloor$
if k=n and A[n]<B[1]
then return A[n]
elseif k<n and B[n-k]≤A[k]≤B[n-k+1]
then return A[k]
elseif A[k]<B[n-k]
then return Find-Median(A,B,k+1,high)
else return Find-Median(A,B,low,k-1)
9.3-9 这是一道数学题…已知所有点的y坐标，求一条直线，使得所有点到该直线距离的和最短，设该直线为y=a，那么所求的距离和即：
|y1-a|+|y2-a|+...+|yn-a|，最小值应该在a=(y1+y2+...+yn)/n时成立。
problems：
9-1 找出序列中已排序的i个最大数
a>如果用排序的方法，最佳的渐进最坏必然是Θ(nlgn)
b>使用最大堆，建堆的时间是O(n)，抽取的时间是O(lgn)，所以总的运行时间是O(n)+O(ilgn)
c>用顺序统计算法求出第i个最大值，需要O(n)的时间，然后partition，需要O(n)的时间【在select的过程中已经进行了划分，这一步其实是不需要的】，排序需要ilgi的时间，所以总时间是O(n)+O(igi)
9-2 加权的中位数
b>直接排序，然后对序列的前i个元素的权值进行累加，直到恰好大于等于1/2，然后取i=i-1，A[i]即为序列的加权中位数
c>找到序列的中位数，对左半边的权值进行累加，如果>1/2，那么对左半边进行递归（并将左半边的权值和加到该元素上），如果<1/2，而右半边>1/2，那么对右半边进行递归（权值和加到该元素上），如果满足条件，返回；如果到达边界条件n=1或n=2（取权值大的），直接计算并返回。
d,e>数学题…表示无力。
9-3 i<n/2时顺序统计量计算的再优化
a>当i≥n/2时直接调用select；否则，将序列以中位数划分，取其左侧(n/2)。成对处理这n/2个数据，将较大值、较小值各组成一个序列(n/4)，递归求出较小值序列中第i个顺序统计量（同时对最大值序列做对等变换），则整个序列的顺序统计量i存在于较大值或较小值序列的前i个数据之中，然后对这2i个数据组成的序列进行求出第i个顺序统计量(T(2i))。
…感觉怎么说呢，速度提升了，但是空间占用也大幅度上升了。
b,c,d都是数学题…表示无力。