说明
本文我先写在我的CSDN上后再转到该博客系统的,有些链接会跳转我的CSDN上
分治法基本思想
- 将一个难以直接解决的大问题,分割成一些规模较小的k个相同问题,以便·各个击破,分而治之·。
- 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为若干个子问题,如此
递归
的进行下去,直到问题规模足够小,很容易求出其解为止。 - 将求出的小规模的问题的解合并为一个更大规模的问题的解,
自底向上逐步求出原来问题的解
。
递归是实现分治算法思想的技术
。:point_right:查看递归的介绍
合并排序的例子
分治法的适用条件
分治法所能解决的问题一般具有以下几个特征
:
- 该问题的规模缩小到一定的程度就可以容易地解决
因为问题的计算复杂性一般是随着问题规模的增加而增加,大部分问题满足这个特征。
- 该问题可以分解为若干个规模较小的
相同
问题
这条特征是应用分治法的前提
,它也是大多数问题可以满足的,此特征反映了递归思想的应用
- 利用该问题分解出的子问题的解可以合并为该问题的解
能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征,;而不具备第三条特征,则可以考虑贪心算法
或动态规划
。
- 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题
如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划
较好。
分治法的基本步骤
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(P)算法求解,不必继续分解。
实践表明,在用分治法设计算法时,最好使子问题的规模大致相同
。即将一个问题分成大小相等的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。
合并问题:不需要合并子问题。
递归填充的四种情况
如果黑方块在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看做黑色方块,然后递归填充左上子棋盘。
如果黑方块在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看做黑色方块,然后递归填充右上子棋盘。
如果黑方块在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看做黑色方块,然后递归填充左下子棋盘。
如果黑方块在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的右下角,将左上角看做黑色方块,然后递归填充右下子棋盘。
复杂度分析
:point_right:可参考分治的基本复杂度分析
算法
#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]
√ 分解出的各个子问题是相互独立的。
二分搜索算法
//二分搜索
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;
}
完整算法
:point_right:快排和二分搜索的实验记录
快速排序
基本思想
基于分治策略的排序在快速排序中,记录的比较和交换是从两端向中间进行的
,关键字较大(小)的记录一次就能交换到后(前)面单元,总的比较和移动次数较少
。
基本思想:对于输入子数组a[p: r]
分解:
以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在划分过程中确定.递归求解
: 分别对a[p: q-1]和a[q+1:r]进行递归排序.合并
: 将排好序的a[p: q-1]和a[q+1:r]直接合并, 即得a[p: r].
例子
主要算法
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(),其实思想差不多
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_;
}
复杂度分析
平均时间复杂度
:point_right: 可参考分治的基本复杂度分析
最坏时间复杂度
在最坏的情况下,待排序的序列为逆序,每次划分产生的两个区域分别包含(n-1)
个元素和1
个元素。如果递归树画出来,它就是一棵斜树。此时需要执行(n‐1次)
递归调用,且第i次划分需要经过(n‐i)次关键字的比较
才能找到第i个记录,也就是基准元素的位置,因此比较次数为
针对最坏情况的算法改进
- 快速排序算法的性能取决于
划分的对称性
。 - 通过修改算法partition,可以设计出采用
随机选择策略
的快速排序算法。 - 在快速排序算法的每一步中,当数组还没有被划分时,
可以在a[p:r]中随机选出一个元素作为划分基准
,这样可以使划分基准的选择是随机的,从而可以期望划分是较对称的。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); }
:point_right: 如果想研究随机选择策略,可以看一下线性时间选择问题的基本求解
算法
#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,并开始进行排序和归并
归并算法
复杂度分析
:point_right: 可参考分治的基本复杂度分析
计算过程
原式等价于 T(n)=2T(n/2)+n
递推得: 2T(n/2)=2(2T(n/2^2^)+n/2)=22T(n/2^2^)+n
T(n)= 2^2^T(n/2^2^)+2n
又有: 2^2^T(n/2)=2^3^T(n/2^3^)+n
故: T(n)= 2^3^T(n/2^3^)+3n
………………….
T(n)=2^k^T(n/2^k^)+kn
令k=logn,即n/2^k^=1
得:
T(n)=nT(1)+nlogn=O(nlogn)
自然排序
自然排序是合并排序算法的一个变形。eg:{4,8,3,7,1,5,6,2}
- 用一次对初始数组的扫描找出所有已排好序的子数组段;{4,8},{3,7},{1,5,6},{2}
- 将相邻排好序的数组两两合并,直至完成整个数组的排序. {3,4,7,8},{1,2,5,6}, …………
算法MergeSort平均时间复杂度:O(nlogn)
(logn次合并)
最好时间复杂度:O(n) (初始已排好序
)
算法
#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小元素
。
思想:对输入数组递归划分,但仅对划分出的子数组之一进行递归处理。
主要算法
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(n^2^)计算时间。
完整算法
//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(n^2^)变成了O(n)。接下来的问题就是如何寻找划分基准?
寻找划分基准-O(n)算法
基本思想
- 定义查找第k小元素算法为 Select(Type a[], int p, int r, int k)
- 将n个输入元素划分成$\lceil n/5 \rceil$个组,
每组5个元素
,只可能有一个 组不是5个元素。 - 用任意一种排序算法,
将每组中的元素排好序
,并取出每组的中位数,共$\lceil n/5 \rceil$个。 - 递归调用算法select来对$\lceil n/5 \rceil$个组
按照中位数排序
,同时,找 出这
$\lceil n/5 \rceil$个中位数元素的中位数
。 如果
$\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
。
主要算法
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)
算法
//中位数线性时间选择
#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