绿色健康小清新

耐得住寂寞,守得住繁华

分治法思想与案例

说明


本文我先写在我的CSDN上后再转到该博客系统的,有些链接会跳转我的CSDN上。并且在CSDN上将内容分开了!


分治法基本思想

  • 将一个难以直接解决的大问题,分割成一些规模较小的k个相同问题,以便·各个击破,分而治之·。
  • 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为若干个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
  • 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解

递归是实现分治算法思想的技术。👉查看递归的介绍

 合并排序的例子


分治法的适用条件

分治法所能解决的问题一般具有以下几个特征

  1. 该问题的规模缩小到一定的程度就可以容易地解决

    因为问题的计算复杂性一般是随着问题规模的增加而增加,大部分问题满足这个特征。

  1. 该问题可以分解为若干个规模较小的相同问题

    这条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用

  1. 利用该问题分解出的子问题的解可以合并为该问题的解

    能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征,;而不具备第三条特征,则可以考虑贪心算法动态规划

  1. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题

    如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。


分治法的基本步骤

1
2
3
4
5
6
7
8
divide-and-conquer(P)
{
if ( | P | <= n0) adhoc(P); //解决小规模的问题, adhoc(P)是基本子算法
divide P into smaller subinstances P1,P2,...,Pk;//分解问题
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //递归的解各子问题
return merge(y1,...,yk); //将各子问题的解合并为原问题的解
}

| P | 表示问题的规模,n0是规模的阈值,表示当问题P的规模不超过n0时,直接用adhoc§算法求解,不必继续分解。

  实践表明,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。


分治法的复杂性分析

  • 分治法将规模为n的问题,分成k个规模为n/m的子问题去解。当然并不一定都是n/m。参考快速排序的最坏情况的复杂度
  • 设分解规模阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。
  • 再设将原问题分解( divide )为k个子问题,以及用merge将k个子问题的解合并(merge)为原问题的解,需用f(n)个单位时间。

 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:

通过迭代法求得方程的解:

求解步骤:




大整数的乘法

 请设计一个有效的算法,可以进行两个n位二进制大整数的乘法运算

  • 小学的方法:O(n2)      ×效率太低

  • 分治法:XY = ac 2n + (ad+bc) 2n/2 + bd    O(n^2)    ×效率太低

为了降低时间复杂度,必须减少乘法的次数。

  • XY = ac 2^n + ((a-b)(d-c)+ac+bd) 2^n/2 + bd

  • XY = ac 2^n + ((a+b)(d+c)-ac-bd) 2^n/2 + bd

细节问题:两个XY的复杂度都是O(nlog3),但考虑到a+b,d+c可能得到m+1位的结果,使问题的规模变大,故不选择第2种方案


复杂度分析

参考上面的分治复杂度一般公式




Strassen矩阵乘法


若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i][j],需要做n次乘法和n-1次加法。因此,算出矩阵C的n2个元素所需的计算时间为O(n3)

  • 传统方法:O(n^3)
  • 分治法:
     使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:

  由此可得:
      

复杂度分析


为了降低时间复杂度,必须减少乘法的次数。

复杂度分析

  Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法

  在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)







棋盘覆盖问题

问题描述

  棋盘覆盖问题。有一个2k∗2k的方格棋盘,恰有一个方格是黑色的,其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖,且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为L型牌的4种旋转方式。

思路分析

分治三步骤
  划分问题:将2k∗2k的棋盘划分为2k−1∗2k−1 这样的子棋盘4块。
   递归求解:递归填充各个格子,填充分为四个情况,在下面会有解释,递归出口为k=0也就是子棋盘方格数为1。
   合并问题:不需要合并子问题。



递归填充的四种情况
   如果黑方块在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看做黑色方块,然后递归填充左上子棋盘。
   如果黑方块在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看做黑色方块,然后递归填充右上子棋盘。
   如果黑方块在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看做黑色方块,然后递归填充左下子棋盘。
   如果黑方块在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的右下角,将左上角看做黑色方块,然后递归填充右下子棋盘。


复杂度分析


   

 👉可参考分治的基本复杂度分析


算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>

using namespace std;

const int MAXNUM=100;

int chess[MAXNUM][MAXNUM];

//相同的L牌为同一个数字,除了第一个黑色单为0
int cur;

//row为最上边行,column为最左边列,x和y是当前黑色方格的位置,size_是棋盘的大小
//row对应y,column对应x
void chessBoard(int row,int column,int x,int y,int size_){
if(size_==1){
return;
}

int s=size_/2;

int cur_=++cur;

//获取中间的位置
int row_center=row+s;
int column_center=column+s;

//左上角判断
if(x<column_center&&y<row_center){
chessBoard(row,column,x,y,s);
}else{
chess[column_center-1][row_center-1]=cur_;
chessBoard(row,column,column_center-1,row_center-1,s);
}

//右上角判断
if(x>=column_center&&y<row_center){
chessBoard(row,column_center,x,y,s);
}else{
chess[column_center][row_center-1]=cur_;
chessBoard(row,column_center,column_center,row_center-1,s);
}

//在下角判断
if(x<column_center&&y>=row_center){
chessBoard(row_center,column,x,y,s);
}else{
chess[column_center-1][row_center]=cur_;
chessBoard(row_center,column,column_center-1,row_center,s);
}

//右下角判断
if(x>=column_center&&y>=row_center){
chessBoard(row_center,column_center,x,y,s);
}else{
chess[column_center][row_center]=cur_;
chessBoard(row_center,column_center,column_center,row_center,s);
}

}

void print(int len){
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
cout<<chess[i][j]<<"\t";
}
cout<<endl<<endl<<endl;
}
}


int main(){
int row,column,size_;
cout<<"请输入棋盘的大小:";
cin>>size_;
cout<<"请输入棋盘中初始时黑色方格的位置(输入格式:x y):";
cin>>row>>column;
if(size_==0){
return 0;
}
cur=1;
chess[column][row]=0;
chessBoard(0,0,row,column,size_);
print(size_);


}

测试结果






二分搜索

问题描述

  给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。


分析

是否满足分治法的特征?

   该问题的规模缩小到一定的程度就可以容易地解决;
   该问题可以分解为若干个规模较小的相同问题;
   分解出的子问题的解可以合并为原问题的解;
   分解出的各个子问题是相互独立的。


 给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。

分析:如果n=1即只有一个元素,则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件

   该问题的规模缩小到一定的程度就可以容易地解决;


分析:比较x和a的中间元素a[mid],mid=(left+right)/2

  • 若x=a[mid],则x在L中的位置就是mid;
  • 如果x<a[mid],则x在a[mid]的前面;
  • 如果x>a[mid],则x在a[mid]的后面。

 无论在哪部分查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。这就说明此问题满足分治法的第二个第三个适用条件
   该问题可以分解为若干个规模较小的相同问题;
   分解出的子问题的解可以合并为原问题的解;


分析:很显然此问题分解出的子问题相互独立,即在a[mid]的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件:

           a[0,…, mid-1,mid, mid+1,…,n]

   分解出的各个子问题是相互独立的。


二分搜索算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//二分搜索
int binarySearch(int arr[],int len,int target){
int left=0;
int right=len-1;
int mid;
while(left<=right){
mid=(left+right)/2;
if(target<arr[mid]){
right=mid-1;
}else if(target>arr[mid]){
left=mid+1;
}else if(target==arr[mid]){
return mid;
}

}

return -1;
}

完整算法

  👉快排和二分搜索的实验记录







快速排序

基本思想

 基于分治策略的排序在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大(小)的记录一次就能交换到后(前)面单元,总的比较和移动次数较少


 基本思想:对于输入子数组a[p: r]

  1. 分解: 以a[p]为基准元素将a[p: r]划分成三段a[p: q-1], a[q] 和a[q+1:r], 使得a[p: q-1]中任一元素<= a[q], a[q+1:r]中任一元素>= a[q]. q在划分过程中确定.
  2. 递归求解: 分别对a[p: q-1]和a[q+1:r]进行递归排序.
  3. 合并: 将排好序的a[p: q-1]和a[q+1:r]直接合并, 即得a[p: r].

例子


主要算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<class Type>
void QuickSort (Type a[ ], int p, int r)
{
if (p<r) {
int q=Partition(a,p,r);
QuickSort (a,p,q-1); //对左半段排序
QuickSort (a,q+1,r); //对右半段排序
}
}

template<class Type>
int Partition (Type a[], int p, int r)
{
int i = p, j = r + 1;
Type x=a[p];
// 将< x的元素交换到左边区域
// 将> x的元素交换到右边区域
while (true) {
while (a[++i] <x);
while (a[- -j] >x);
if (i >= j) break;
Swap(a[i], a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}

上述的Partition (Type a[], int p, int r)适用于指定了某个基准元素,然后以该基准元素进行比较

另一种Partition(),其实思想差不多

1
2
3
4
5
6
7
8
9
10
11
12
int Partition (int arr[],int start_,int end_){
int value=arr[start_];

while(start_<end_){
while(start_<end_&&arr[end_]>=value) end_--;
arr[start_]=arr[end_];
while(start_<end_&&arr[start_]<=value) start_++;
arr[end_]=arr[start_];
}
arr[end_]=value;
return end_;
}

复杂度分析

平均时间复杂度
     
 👉 可参考分治的基本复杂度分析

最坏时间复杂度
  在最坏的情况下,待排序的序列为逆序,每次划分产生的两个区域分别包含(n-1)个元素和1个元素。如果递归树画出来,它就是一棵斜树。此时需要执行(n‐1次)递归调用,且第i次划分需要经过(n‐i)次关键字的比较才能找到第i个记录,也就是基准元素的位置,因此比较次数为

     


针对最坏情况的算法改进

  • 快速排序算法的性能取决于划分的对称性
  • 通过修改算法partition,可以设计出采用随机选择策略的快速排序算法。
  • 在快速排序算法的每一步中,当数组还没有被划分时,可以在a[p:r]中随机选出一个元素作为划分基准,这样可以使划分基准的选择是随机的,从而可以期望划分是较对称的。
1
2
3
4
5
6
7
template<class Type>
int RandomizedPartition (Type a[ ], int p, int r)
{
int i = Random(p,r);
Swap(a[i], a[p]);
return Partition (a, p, r);
}

 👉 如果想研究随机选择策略,可以看一下线性时间选择问题的基本求解


算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>

using namespace std;

int Partition (int arr[],int start_,int end_);


//先进行快排,将我们的数组进行排序,再进行二分搜索
void quickSort(int arr[],int startV,int endV){
if(startV<endV){
int mid=Partition (arr,startV,endV);
quickSort(arr,startV,mid-1);
quickSort(arr,mid+1,endV);
}
}

//获取中间的数
int Partition (int arr[],int start_,int end_){
int value=arr[start_];

while(start_<end_){
while(start_<end_&&arr[end_]>=value) end_--;
arr[start_]=arr[end_];
while(start_<end_&&arr[start_]<=value) start_++;
arr[end_]=arr[start_];
}
arr[end_]=value;
return end_;

}





int main(){
int len; //数组长度

cout<<"请输入长度:";
cin>>len;
int* arr=new int[len];
cout<<endl<<"请输入数字:";
for(int i=0;i<len;i++){
cin>>arr[i];
}

quickSort(arr,0,len-1);
cout<<"排序后的数组: ";
for(int i=0;i<len;i++){
cout<<arr[i]<<" ";
}
}

测试样例

输入

请输入长度:10
请输入数字:2 8 9 4 3 50 10 66 0 8

删除

排序后的数组: 0 2 3 4 8 8 9 10 50 66







合并排序

基本思想

 将n个元素分成2个大小相同的子集合,分别对子集合进行排序,最终将排好序的子集合合并为有序集合。n=1时中止。


算法分析

当最小规模为4时,进行排序和归并,将已经比较好的较小的值依次排好序放在一个临时的数组中

上面的是规模为4时的分析,归并算法中,一般把规模缩小到2,并开始进行排序和归并


归并算法


复杂度分析


 👉 可参考分治的基本复杂度分析

计算过程

  原式等价于 T(n)=2T(n/2)+n
  递推得: 2T(n/2)=2(2T(n/22)+n/2)=22T(n/22)+n
       T(n)= 22T(n/22)+2n
   又有: 22T(n/2)=23T(n/23)+n
    故: T(n)= 23T(n/23)+3n
     ………………….
      T(n)=2kT(n/2k)+kn
    令k=logn,即n/2^k^=1 得:
      T(n)=nT(1)+nlogn=O(nlogn)


自然排序

 自然排序是合并排序算法的一个变形。eg:{4,8,3,7,1,5,6,2}

  1. 用一次对初始数组的扫描找出所有已排好序的子数组段;{4,8},{3,7},{1,5,6},{2}
  2. 将相邻排好序的数组两两合并,直至完成整个数组的排序. {3,4,7,8},{1,2,5,6}, …………

 算法MergeSort平均时间复杂度:O(nlogn)(logn次合并)

 最好时间复杂度:O(n) (初始已排好序)



算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
void Merge(int a[], int left, int mid, int right)
{
int t_pos = 0, low = left, high = mid + 1;
int lenth = right - left + 1;
int temp[lenth];
while(low <= mid && high <= right)
{
if(a[low] < a[high])
{
temp[t_pos++] = a[low++];
}
else
{
temp[t_pos++] = a[high++];
}
}
while(low <= mid)
{
temp[t_pos++] = a[low++];
}
while(high <= right)
{
temp[t_pos++] = a[high++];
}
for(int i = 0; i < lenth; ++i)
{
a[left++] = temp[i];
}
}
void MergeSort(int a[], int left, int right)
{
if(left >= right)
return;
else
{
int mid = (left + right) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right);
}
}
int main()
{
int a[MAX];
int num;
cout<<"请输入数字的个数:";
cin>>num;
cout<<"请输入要排序的数字:";
for(int i = 0; i < num; ++i)
{
cin>>a[i];
}

MergeSort(a, 0, num - 1);
cout<<"归并排序后的数字:";
for(int i = 0; i < num; ++i)
{
cout<<a[i]<<" ";
}
}

测试样例

输入

请输入数字的个数:10
请输入要排序的数字:2 8 9 4 3 50 10 66 0 8

输出

归并排序后的数字:0 2 3 4 8 8 9 10 50 66






线性时间选择

问题描述

 给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。在线性时间内O(n)

  • k=1; 最小元素 O(n)
  • k=n; 最大元素 O(n)
  • k=(n+1)/2: 中位数 O(n)?

算法思想

 线性时间选择问题的分治法:模仿快速排序算法,找第k小元素

思想:对输入数组递归划分,但仅对划分出的子数组之一进行递归处理。


主要算法

1
2
3
4
5
6
7
8
9
10
11
template<class Type>
Type RandomizedSelect(Type a[ ], int p, int r, int k)
{
if (p==r) return a[p];
//一次快速排序,随机选择基准元素,划分数组
int i=RandomizedPartition(a,p,r),
j=i-p+1; // j为a[p,i]中元素个数
if (k<=j) return RandomizedSelect(a,p,i,k);
//返回第k-j小元素
else return RandomizedSelect(a,i+1,r,k-j);
}

小例子

 有一个数组:{ 4, 2, 5, 7, 4, 9, 6, 21 }


复杂度分析

平均时间复杂度

        

 可以证明,算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素


最坏时间复杂度

 在最坏情况下(找最小,但总在最大处划分),算法randomizedSelect需要O(n2)计算时间。
      

        


完整算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//2d9-1 随机划分线性时间选择
#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

int a[] = {5,7,3,4,8,6,9,1,2};

template <class Type>
void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
int Partition(Type a[],int p,int r);

template<class Type>
int RandomizedPartition(Type a[],int p,int r);

template <class Type>
Type RandomizedSelect(Type a[],int p,int r,int k);

int main()
{
for(int i=0; i<9; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<RandomizedSelect(a,0,8,3)<<endl;
}

template <class Type>
void Swap(Type &x,Type &y)
{
Type temp = x;
x = y;
y = temp;
}

inline int Random(int x, int y)
{
srand((unsigned)time(0));
int ran_num = rand() % (y - x) + x;
return ran_num;
}

template <class Type>
int Partition(Type a[],int p,int r)
{
int i = p,j = r + 1;
Type x = a[p];

while(true)
{
while(a[++i]<x && i<r);
while(a[--j]>x);
if(i>=j)
{
break;
}
Swap(a[i],a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}

template<class Type>
int RandomizedPartition(Type a[],int p,int r)
{
int i = Random(p,r);
Swap(a[i],a[p]);
return Partition(a,p,r);
}

template <class Type>
Type RandomizedSelect(Type a[],int p,int r,int k)
{
if(p == r)
{
return a[p];
}
int i = RandomizedPartition(a,p,r);
int j = i - p + 1;
if(k <= j)
{
return RandomizedSelect(a,p,i,k);
}
else
{
//由于已知道子数组a[p:i]中的元素均小于要找的第k小元素
//因此,要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
return RandomizedSelect(a,i+1,r,k-j);
}
}

别急!这个算法有很大的缺陷,接下来我们来解决一下最坏时间复杂度的问题


最坏时间复杂度的问题思考

 若能在O(n)内找到一个划分基准,使得所划分的2个子数组长度,都至少为原数组长度的ε倍(0<ε <1 ),则在最坏情况下用O(n)时间完成选择任务。

 例如,若ε=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以,在最坏情况下,算法所需的计算时间T(n)满足递归式:
           T(n)≤T(9n/10)+O(n)

           由此可得T(n)=O(n)

 是不是一下子就把最坏时间复杂度从O(n2)变成了O(n)。接下来的问题就是如何寻找划分基准?


寻找划分基准-O(n)算法

基本思想

  • 定义查找第k小元素算法为 Select(Type a[], int p, int r, int k)
  • 将n个输入元素划分成n/5\lceil n/5 \rceil个组,每组5个元素,只可能有一个 组不是5个元素。
  • 用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共n/5\lceil n/5 \rceil个。
  • 递归调用算法select来对n/5\lceil n/5 \rceil个组按照中位数排序,同时,找 出这n/5\lceil n/5 \rceil个中位数元素的中位数
  • 如果n/5\lceil n/5 \rceil是偶数,就找它的2个中位数中较大的一个。以这个 元素作为划分基准。

将中位数的中位数x,作为基准元素

      

简单划分案列


计算大于和小于基准X的元素数目

 组中除了中位数,小于基准x的元素个数有:

中位数中小于基准x的个数为:




 因此,小于基准x的元素个数至少为:

 同理,大于基准x的元素个数至少为:

红框表示的是一定小于基准X的元素
蓝框表示的是一定大于基准X的元素
两者的值理论上是相等的


要注意一下n≥75的情况

  当n≥75时,3(n-5)/10≥n/4。所以,按此基准划分所得的2个子数组的长度都至少缩短1/4


主要算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Type Select(Type a[], int p, int r, int k)
{
if (r-p<75) {
//用某个简单排序算法对数组a[p:r]排序;
return a[p+k-1];
};
for ( int i = 0; i<=(r-p-4)/5; i++ ) // i代表组数
{
//将元素每5个分成一组,分别排序
BubbleSort(a, p+5*i, p+5*i+4);
//将该组中位数与a[p+i]交换位置,即: 将a[p+5*i] 至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
Swap(a[p+5*i+2], a[p+i]);
} // O(n)
//找中位数的中位数
Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); // T(n/5)
int i=Partition(a, p, r, x), // O(n)
j=i-p+1;
if (k<=j) return Select(a, p, i, k);
else return Select(a,i+1,r,k-j);
}


复杂度分析

设找第K小元素的算法的时间复杂性是: T(n)

 找中位数的中位数:  T(n/5)

 调用快速排序partition函数对每个数组进行排序:  O(n):

 按照上述方法所选的基准x进行划分,得到的两个子数组分别至多有3n/4个元素:T(3n/4)

     


算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//中位数线性时间选择
#include <ctime>
#include<stdlib.h>
#include <iostream>
#include<algorithm>
using namespace std;

template <class Type>
void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
void BubbleSort(Type a[],int p,int r);

template <class Type>
int Partition(Type a[],int p,int r,Type x);

template <class Type>
Type Select(Type a[],int p,int r,int k);

int main()
{
//初始化数组
int a[100];

//数字索引
int k;

//必须放在循环体外面
srand((unsigned)time(0));

for(int i=0; i<100; i++)
{
a[i] = Random(0,500);
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl;


cout<<"请输入您要获取的数字索引(从1开始):";
cin>>k;


cout<<"第"<<k<<"个元素是"<<Select(a,0,100,k)<<endl;



//重新排序,对比结果
BubbleSort(a,0,100);

for(int i=0; i<100; i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl;
}

template <class Type>
void Swap(Type &x,Type &y)
{
Type temp = x;
x = y;
y = temp;
}

inline int Random(int x, int y)
{
int ran_num = rand() % (y - x) + x;
return ran_num;
}

//冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
//记录一次遍历中是否有元素的交换
bool exchange;
for(int i=p; i<r-1;i++)
{
exchange = false ;
for(int j=0; j<r-1-i; j++)
{
if(a[j]>a[j+1])
{
Swap(a[j],a[j+1]);
exchange = true;
}
}
//如果这次遍历没有元素的交换,那么排序结束
if(false == exchange)
{
break ;
}
}

}

template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
int i = p-1,j = r ;

while(true)
{
while(a[++i]<x && i<r);
while(a[--j]>x);
if(i>=j)
{
break;
}
Swap(a[i],a[j]);
}
return j;
}


template <class Type>
Type Select(Type a[],int p,int r,int k)
{
if(r-p<75)
{

//BubbleSort(a,p,r);
sort(a + p, a + r);
return a[p+k-1];
}


for(int i=0; i<=(r-p-4)/5; i++)
{
//将元素每5个分成一组,分别排序,并将该组中位数与a[p+i]交换位置
//使所有中位数都排列在数组最左侧,以便进一步查找中位数的中位数
//BubbleSort(a,p+5*i,p+5*i+4);
sort(a+p+i*5,a+p+5*i+4);
Swap(a[p+5*i+2],a[p+i]);
}


//找中位数的中位数
Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);




int i = Partition(a,p,r,x);


int j = i-p+1;



if(k<=j)
{
return Select(a,p,i,k);
}
else
{
return Select(a,i+1,r,k-j);
}

}

该代码还是有一些小bug,输出的值有时候有一些偏差,并且用冒泡算法代替sort()也有一些小问题。暂时不想去改了,以后有时间再看吧。


测试用例

随机产生的100个数据
a[0]:402 a[1]:436 a[2]:336 a[3]:309 a[4]:130 a[5]:154 a[6]:348 a[7]:96 a[8]:141 a[9]:168 a[10]:375 a[11]:159 a[12]:253 a[13]:269 a[14]:137 a[15]:228 a[16]:254 a[17]:385 a[18]:301 a[19]:185 a[20]:169 a[21]:48 a[22]:472 a[23]:131 a[24]:353 a[25]:457 a[26]:360 a[27]:315 a[28]:211 a[29]:278 a[30]:395 a[31]:430 a[32]:489 a[33]:296 a[34]:108 a[35]:489 a[36]:255 a[37]:78 a[38]:433 a[39]:320 a[40]:370 a[41]:213 a[42]:53 a[43]:319 a[44]:469 a[45]:294 a[46]:444 a[47]:63 a[48]:101 a[49]:351 a[50]:89 a[51]:270 a[52]:151 a[53]:306 a[54]:171 a[55]:5 a[56]:159 a[57]:164 a[58]:215 a[59]:472 a[60]:103 a[61]:78 a[62]:405 a[63]:499 a[64]:297 a[65]:314 a[66]:129 a[67]:296 a[68]:262 a[69]:27 a[70]:32 a[71]:386 a[72]:175 a[73]:136 a[74]:479 a[75]:424 a[76]:234 a[77]:434 a[78]:159 a[79]:100 a[80]:485 a[81]:397 a[82]:341 a[83]:82 a[84]:348 a[85]:234 a[86]:12 a[87]:351 a[88]:277 a[89]:486 a[90]:365 a[91]:303 a[92]:151 a[93]:381 a[94]:291 a[95]:115 a[96]:243 a[97]:324 a[98]:279 a[99]:319

输入
请输入您要获取的数字索引(从1开始):25

输出
第25个元素是151

排序好的数组
a[0]:5 a[1]:12 a[2]:27 a[3]:32 a[4]:48 a[5]:53 a[6]:63 a[7]:78 a[8]:78 a[9]:82 a[10]:89 a[11]:96 a[12]:100 a[13]:101 a[14]:103 a[15]:108 a[16]:115 a[17]:129 a[18]:130 a[19]:131 a[20]:136 a[21]:137 a[22]:141 a[23]:151 a[24]:151 a[25]:154 a[26]:159 a[27]:159 a[28]:159 a[29]:164 a[30]:168 a[31]:169 a[32]:171 a[33]:175 a[34]:185 a[35]:211 a[36]:213 a[37]:215 a[38]:228 a[39]:234 a[40]:234 a[41]:243 a[42]:253 a[43]:254 a[44]:255 a[45]:262 a[46]:269 a[47]:270 a[48]:277 a[49]:278 a[50]:279 a[51]:291 a[52]:294 a[53]:296 a[54]:296 a[55]:297 a[56]:301 a[57]:303 a[58]:306 a[59]:309 a[60]:314 a[61]:315 a[62]:319 a[63]:319 a[64]:320 a[65]:324 a[66]:336 a[67]:341 a[68]:348 a[69]:348 a[70]:351 a[71]:351 a[72]:353 a[73]:360 a[74]:365 a[75]:370 a[76]:375 a[77]:381 a[78]:385 a[79]:386 a[80]:395 a[81]:397 a[82]:402 a[83]:405 a[84]:424 a[85]:430 a[86]:433 a[87]:434 a[88]:436 a[89]:444 a[90]:457 a[91]:469 a[92]:472 a[93]:472 a[94]:479 a[95]:485 a[96]:486 a[97]:489 a[98]:489 a[99]:499

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道