第9章 排序和顺序统计学算法导论
最后更新于：2022-04-01 07:35:19
# 一、概念
第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）待解决