💎一站式轻松地调用各大LLM模型接口,支持GPT4、智谱、星火、月之暗面及文生图 广告
# 一、概念 第i个顺序统计量是该集合中第i小的元素。 当n为奇数时,中位数是出现在i=(n+1)/2处的数。当n为偶数时,中位数分别出现在i=n/2和i=(n+1)/2处。 在本文中,忽略n的奇偶性,中位数是指出现在i=(n+1)/2处的数。 本文假设集合中的数互异。 # 二、代码 ~~~ #include <iostream> using namespace std; //书中的程序 int length_A; void Print(int *A) { int i; for(i = 1; i <= length_A; i++) cout<<A[i]<<' '; cout<<endl; } /*******线性时间求最小值****************************/ int Minimun(int *A) { int Min = A[1], i; //依次查看集合中的每个元素 for(i = 2; i < length_A; i++) //记录比较过程中最小的元素 if(Min > A[i]) Min = A[i]; return Min; } /*******通过3n/2次比较求最小值和最大值****************************/ void MinAndMax(int *A,int &Min, int &Max) { int i; //如果n是奇数 if(length_A % 2 == 1) { //将最大值和最小值设置为第一个元素 Min = A[1]; Max = A[1]; i = 2; } //如果n是偶数 else { //将前两个元素作一次比较,以决定最大值怀最小值的初值 Min = min(A[1], A[2]); Max = A[1] + A[2] - Min; i = 3; } //成对地处理余下的元素 for(; i <= length_A; i=i+2) { //将一对输入元素互相比较 int a = min(A[i], A[i+1]); int b = A[i] + A[i+1] - a; //把较小者与当前最小值比较 if(a < Min) Min = a; //把较大者与当前最大值比较 if(b > Max) Max = b; } } /********以期望线性时间作选择********************/ //已经出现很多次了,不解释 int Partition(int *A, int p, int r) { int x = A[r], i = p-1, j; for(j = p; j < r; j++) { if(A[j] <= x) { i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } int Randomized_Partition(int *A, int p, int r) { //随机选择数组中一个数作为主元 int i = rand() % (r-p+1) + p; swap(A[r], A[i]); //划分 return Partition(A, p, r); } //i是从1开使计数的,不是从p开始 int Randomized_Select(int *A, int p, int r, int i) { if(p == r) return A[p]; //以某个元素为主元,把数组分为两组,A[p..q-1] < A[q] < A[q+1..r],返回主元在整个数组中的位置 int q = Randomized_Partition(A, p, r); //主元是整个数组中的第q个元素,是A[p..r]数组中的第k个元素 int k = q - p + 1; //所求的i中A[p..r]中的第i个元素 if(i == k)//正是所求的元素 return A[q]; else if(i < k)//所求元素<主元,则在A[p..q-1]中继续寻找 return Randomized_Select(A, p, q-1, i); else//所求元素>主元,则在A[q+1..r]中继续寻找 return Randomized_Select(A, q+1, r, i-k); } /*******最坏情况线性时间的选择**************************/ int Select(int *A, int p, int r, int i); //对每一组从start到end进行插入排序,并返回中值 //插入排序很简单,不解释 int Insert(int *A, int start, int end, int k) { int i, j; for(i = 2; i <= end; i++) { int t = A[i]; for(j = i; j >= start; j--) { if(j == start) A[j] = t; else if(A[j-1] > t) A[j] = A[j-1]; else { A[j] = t; break; } } } return A[start+k-1]; } //根据文中的算法,找到中值的中值 int Find(int *A, int p, int r) { int i, j = 0; int start, end, len = r - p + 1; int *B = new int[len/5+1]; //每5个元素一组,长度为start到end,对每一组进行插入排序,并返回中值 for(i = 1; i <= len; i++) { if(i % 5 == 1) start = i+p-1; if(i % 5 == 0 || i == len) { j++; end = i+p-1; //对每一组从start到end进行插入排序,并返回中值,如果是最后一组,组中元素个数可能少于5 int ret = Insert(A, start, end, (end-start)/2+1); //把每一组的中值挑出来形成一个新的数组 B[j] = ret; } } //对这个数组以递归调用Select()的方式寻找中值 int ret = Select(B, 1, j, (j+1)/2); //delete []B; //很奇怪,这句话应该是没问题的,但是怎么一运行到这句话就死机呢? return ret; } //以f为主元的划分 int Partition2(int *A, int p, int r, int f) { int i; //找到f的位置并让它与A[r]交换 for(i = p; i < r; i++) { if(A[i] == f) { swap(A[i], A[r]); break; } } return Partition(A, p, r); } //寻找数组A[p..r]中的第i大的元素,i是从1开始计数,不是从p开始 int Select(int *A, int p, int r, int i) { //如果数组中只有一个元素,则直接返回 if(p == r) return A[p]; //根据文中的算法,找到中值的中值 int f = Find(A, p, r); //以这个中值为主元的划分,返回中值在整个数组A[1..len]的位置 //因为主元是数组中的某个元素,划分好是这样的,A[p..q-1] <= f < A[q+1..r] int q = Partition2(A, p, r, f); //转换为中值在在数组A[p..r]中的位置 int k = q - p + 1; //与所寻找的元素相比较 if(i == k) return A[q]; else if(i < k) return Select(A, p, q-1, i); else //如果主元是数组中的某个元素,后面一半要这样写 return Select(A, q+1, r, i-k); //但是如果主元不是数组中的个某个元素,后面一半要改成Select(A, q, r, i-k+1) } int main() { cin>>length_A; int *A = new int[length_A+1], i, cnt; //生成测试数据 for(i = 1; i <= length_A; i++) A[i] = rand() % 100; cin>>cnt; //显示测试数据 Print(A); //输出结果 if(cnt <= length_A) cout<<Select(A, 1, length_A, cnt)<<endl; return 0; } ~~~ # 三、习题 ### 9.1 最小值和最大值 9.1-1 见[算法导论 9.1-1 求第二小元素](http://blog.csdn.net/mishifangxiangdefeng/article/details/7983809) ### 9.2 以期望线性时间做选择 ~~~ 9.2-3 RANDOMIZED-SELECT(A, p, r, i) 1 while true 2 if p = r 3 then return A[p] 4 q <- RANDIMIZED-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 q <- q-1 10 else 11 q <- q + 1 12 i <- i - k 9.2-4 A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1} ==> A = {3, 2, 0, 7, 5, 4, 8, 6, 1, 9} ==> A = {3, 2, 0, 7, 5, 4, 6, 1, 8, 9} ==> A = {3, 2, 0, 5, 4, 6, 1, 7, 8, 9} ==> A = {3, 2, 0, 5, 4, 1, 6, 7, 8, 9} ==> A = {3, 2, 0, 4, 1, 5, 6, 7, 8, 9} ==> A = {3, 2, 0, 1, 4, 5, 6, 7, 8, 9} ==> A = {2, 0, 1, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ==> A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ~~~ ### 9.3 最坏情况线性时间的选择 9.3-3 先中SELECT选择中值,再用这个中值进行划分,代码见[算法导论-9.3-3](http://blog.csdn.net/mishifangxiangdefeng/article/details/7687733) ~~~ QUICKSORT(A, p, r) 1 if p > r 2 then return 3 i <- (r-p+1) / 2 4 x <- SELECT(A, p, r, i) 5 q <- PARTITION(A, p, r, x) //以x为主元的划分 6 QUICKSORT(A, p, q-1) 7 QUICKSORT(A, q+1, r) ~~~ 9.3-5 ~~~ SELECT(A, p, r, i) 1 if p = r 2 then return A[p] 3 x <- MEDIAN(A, p, r) 4 q <- PARTITION(A, p, r, x) //以x为主元的划分 5 k <- q - p + 1 6 if i = k 7 then return A[q] 8 else if i < k 9 then return SELECT(A, p, q-1, i) 10 else return SELECT(A, q+1, r, i-k) ~~~ 9.3-6 令每个子集合的元素个数为t = n / k,A[j]是数组A中下标为j的元素,A(j)是数组是第j大的元素 则所求的k分位数是指A(t),A(2t),A(3t),……,A((k-1)t) 按顺序依次求这k-1个数的运行时(k-1)*n 要使运行时间为O(nlgk),改进方法是不要依次寻找这k-1个数,而是借用二分的方法来找。 先找第k/2个分位数,再以这个分位数为主元把数组分为两段,分别对这两段来找分位数,这个时候找的范围变小了,效率也就提高了 见[算法导论-9.3-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7689102) 9.3-7 step1:求出数组的中位数的值O(n) step2:计算数组每个数与中位数差的绝对值,存于另一个数组B中O(n) step3:求出数组B中第k小的数ret O(n) step4:计算数组S中与ret差的绝对值小于ret的数并输出O(n) 其中,step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数 代码见[算法导论-9.3-7](http://blog.csdn.net/mishifangxiangdefeng/article/details/7689900) 9.3-8 递归求解该问题,解题规模不断减半,最后剩下4个元素时,得到问题的解 分别取两个数组的中值minA和minB进行比较 如果minA=minB,那么这个值就是结果 否则,小的那个所在的数组去掉前面一半,大的那个去掉后面一半。(对于两个数组的中值,共有n-1个元素,有n个元素比它大。但是对于min(minA,minB),最多只有n-2个元素比它小,所以一定不是所求的结果,同理去掉大的一半) 然后对剩余的两个数组,用同的方法求它们的中值,直到两个数组一共剩下4个元素 代码见[算法导论-9.3-8](http://blog.csdn.net/mishifangxiangdefeng/article/details/7690461) 9.3-9 这题其实挺简单的,就是不一定能找到这个规律。 为了简化这道题,不考虑点的y坐标,假设所有的点都在一条与管道垂直的线上 假如有两个点AB,分别在管道l的上下,那么不管这条管道在什么位置(只要在AB之间),d[Al]+d[bl]=d[AB]。 根据以上规律,把每两个点分为一组,第i组中的点是(第i大的点,第i小的点),只要管道在每组的两个点之间,就能保证长度总和最小。 由以上推理得出答案: 令所以x作为的中值为s(i), 如果点的个数是奇数,管道过s(i)点 如果点的个数是偶数,管道位于点s(i)和s(i+1)之间(包括这两点) # 四、思考题 ### 9-1 已排序的i个最大数 ~~~ a)合并排序和堆排序,O(nlgn) b)堆排序,O(n+ilgn) c)快速排序,O(n+ilgi) ~~~ ### 9-2 带权中位数 b) 使用最坏情况时间为O(nlgn)的排序算法对每个元素进行排序 依次累加元素的权重,直到满足题目中公式 c) step1:利用SELECT中寻找中值的中值的算法,找到主元 step2:用主元把数组分为三段,即A[1..q-1] < A[q] < A[q+1..r] step3:计算A[1..q-1]<0.5和A[1..q]>=0.5的权值和,是否满足题目中的公式 step4:若满足,A[q]就是所求的数 step5:若不满足,就继续递归使用本算法进行递归查找。偏大就找前半段,偏小就找后半段 代码见[算法导论-9-2-c-带权中位数](http://blog.csdn.net/mishifangxiangdefeng/article/details/7690962) 邮局位置问题: 关键是d)的结论 ### 9-3 小型顺序统计量 a)待解决