(五)算法基础——分治
目录
基本概念
把一个任务,分成形式和原任务相同,但规模更小的几个部分任务(通常是两个部分),分别完成,或只需要选一部完成。然后再处理完成后的这一个或几个部分的结果,实现整个任务的完成。
实例
称硬币
16硬币,有可能有1枚假币,假币比真币轻。有一架天 平,用最少称量次数确定有没有假币,若有的话,假 币是哪一枚。
这个我们之前应该接触过,解决办法就是一次一次不断分解,两边先称8个,然后4个,然后两个,最后一个,就能得出结果。
- 8 – 8 一称,发现无假币,或假币所在的那8枚
- 4 – 4 一称
- 2 – 2 一称
- 1 – 1 一称
例子
归并排序
步骤
数组排序任务可以如下完成:
- 把前一半排序
- 把后一半排序
- 把两半归并到一个新的有序数组,然后再拷贝回原 数组,排序完成。
代码实现
#include<stdio.h>
void Merge(int a[],int s,int m, int e,int tmp[])
{
//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
//归并操作时间复杂度:O(e-m+1),即O(n)
int pb = 0,i;
int p1 = s,p2 = m+1; // 两个指针,比较大小,把小的放入数组之后再移动
while( p1 <= m && p2 <= e) {
if( a[p1] < a[p2])
tmp[pb++] = a[p1++];
else
tmp[pb++] = a[p2++];
}
while( p1 <= m) // 一个数组以及完成,将另一个数组放入
tmp[pb++] = a[p1++];
while( p2 <= e)
tmp[pb++] = a[p2++];
for(i = 0;i < e-s+1; ++i)// 拷贝
a[s+i] = tmp[i];
}
// 归并排序
void MergeSort(int a[],int s,int e,int tmp[])
{
if( s < e) {
int m = s + (e-s)/2;
MergeSort(a,s,m,tmp);
MergeSort(a,m+1,e,tmp);
Merge(a,s,m,e,tmp);
}
}
int a[10] = { 13,27,19,2,8,12,2,8,30,89};
int b[10];
int main()
{
int size = sizeof(a)/sizeof(int),i;
MergeSort(a,0,size-1,b);
for(i = 0;i < size; ++i)
printf("%d ",a[i]);
return 0;
}
可能有些同学对归并函数(Merge)不是特别熟悉,我们来简单的介绍一下。就是通过两个指针,不断比较大小,然后得到有序数组。
时间复杂度
归并排序的时间复杂度是O(nlog(n)),具体证明方法如下,就不做详细介绍。 对n个元素进行排序的时间:
- T(n) = 2*T(n/2) + a*n (a是常数,具体多少不重要)
- = 2*(2*T(n/4)+a*n/2)+a*n
- = 4*T(n/4)+2a*n
- = 4*(2*T(n/8)+a*n/4)+2*a*n
- = 8*T(n/8)+3*a*n ...
- = 2k *T(n/2k)+k*a*n 一直做到 n/2k = 1 (此时 k = log2n),
- T(n)= 2k *T(1)+k*a*n = 2k *T(1)+k*a*n = 2k+k*a*n = n+a*(log2n)*n
复杂度O(nlogn)
快速排序
步骤
数组排序任务可以如下完成:
- 设k=a[0], 将k挪到适当位置,使得比k小的元素都 在k左边,比k大的元素都在k右边,和k相等的,不关心 在k左右出现均可 (O(n)时间完成)
- 把k左边的部分快速排序
- 把k右边的部分快速排序
1、将第一个元素设为K,偶数时用 j 去比较 i ,如果 j 小于 i ,则交换 i 与 j 的位置。如果 j 大于 i,j --。
j --;
交换;
2、 当交换次数为奇数时,用 i 去比较 j ,如果 i 小于 j ,i++。如果 i 大于 j,则交换 i 与 j 的位置。
i++;
交换;
3、j=i,停止。
代码如下
#include<stdio.h>
void swap(int * a,int * b) //交换变量a,b值
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void QuickSort(int a[],int s,int e)
{
if( s >= e)
return;
int k = a[s];
int i = s,j = e;
while( i != j ) {
while( j > i && a[j] >= k )
--j;
swap(&a[i],&a[j]);
while( i < j && a[i] <= k )
++i;
swap(&a[i],&a[j]);
} //处理完后,a[i] = k
QuickSort(a,s,i-1);
QuickSort(a,i+1,e);
}
int a[] = { 93,27,30,2,8,12,2,8,30,89};
int main()
{
int size = sizeof(a)/sizeof(int),i;
QuickSort(a,0,size-1);
for(i = 0;i < size; ++i)
printf("%d ",a[i]);
return 0;
}
时间复杂度也是 O(nlogn),就不做过多介绍。
例题
输出前m大的数
- 描述
给定一个数组包含n个元素,统计前m大的数并且把这m个数从大到小输出。
- 输入
第一行包含一个整数n,表示数组的大小。n < 100000。 第二行包含n个整数,表示数组的元素,整数之间以一个空格分开 。每个整数的绝对值不超过100000000。 第三行包含一个整数m。m < n。
- 输出
从大到小输出前m大的数,每个数一行。
解题思路
首先是可以选择先排序再输出,复杂度是 O(nlogn);但是除此之外,还可以选择用分治的思想把前m大的都弄到数组最右边,然后对这最右边m个元素排序, 再输出。这样的话复杂度是O(n+mlogm),在大部分情况下,比第一种解法要更好。
操作
如何将前k大的都弄到最右边
- 设key=a[0], 将key挪到适当位置,使得比key小的元素都在 key左边,比key大的元素都在key右边(线性时间完成)
- 选择数组的前部或后部再进行 arrangeRight操作
具体如下所示
#include<stdio.h>
void swap(int * a,int * b) //交换变量a,b值
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void arrangeRight(int a[],int s,int e,int m)
{
if( s >= e)
return;
int k = a[s];
int i = s,j = e;
while( i != j ) {
while( j > i && a[j] >= k )
--j;
swap(&a[i],&a[j]);
while( i < j && a[i] <= k )
++i;
swap(&a[i],&a[j]);
} //处理完后,a[i] = k
if(e-i == m){
return;
//a = k return
}
if(e-i > m){
return arrangeRight(a,i+1,e,m);
//a > k 对最右边a-1个元素再进行arrangeRigth
}
if(e-i < m){
return arrangeRight(a,0,i-1,m-e+i);
//a < k 对左边b个元素再进行arrangeRight
}
}
// 快排其实可以用自带的函数,但我还是用了上面自己写的。
void QuickSort(int a[],int s,int e)
{
if( s >= e)
return;
int k = a[s];
int i = s,j = e;
while( i != j ) {
while( j > i && a[j] >= k )
--j;
swap(&a[i],&a[j]);
while( i < j && a[i] <= k )
++i;
swap(&a[i],&a[j]);
} //处理完后,a[i] = k
QuickSort(a,s,i-1);
QuickSort(a,i+1,e);
}
int main(void)
{
int i,m,n,x;
scanf("%d",&n);
int a[n];
for(i = 0;i < n; ++i)
scanf("%d",&a[i]);
scanf("%d",&m);
//分治
arrangeRight(a,0,n-1,m);
//排序
QuickSort(a,m,n-1);
//输出
for(i = n-m;i < n; ++i)
printf("%d ",a[i]);
return 0;
}
求排列的逆序数
题目 考虑1,2,…,n (n ik, 那么就称(ij ,ik )是这个排列的一个逆序。 一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个 逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。 现给定1,2,…,n的一个排列,求它的逆序数。
解题思路
一开始当然是可以用遍历去解决,但是那样时间复杂度为 O(n^2 ),所以我们采用分治的方法去解决。其实也就是归并排序,其实仔细想想,就会发现需要我们求得刚好就是我们按照升序排序时移动元素的次数。所以我们只需要在之前的归并排序上改动一点点,就能实现我们的需求。
代码实现如下
我没有加上输入,这个比较简单,大家稍作修改就好了。
#include<stdio.h>
int sum = 0;
void Merge(int a[],int s,int m, int e,int tmp[])
{
//将数组a的局部a[s,m]和a[m+1,e]合并到tmp,并保证tmp有序,然后再拷贝回a[s,m]
//归并操作时间复杂度:O(e-m+1),即O(n)
int pb = 0,i;
int p1 = s,p2 = m+1; // 两个指针,比较大小,把小的放入数组之后再移动
while( p1 <= m && p2 <= e) {
if( a[p1] < a[p2])
tmp[pb++] = a[p1++];
else {
tmp[pb++] = a[p2++];
sum += m-p1+1; // 计数
}
}
while( p1 <= m) // 一个数组以及完成,将另一个数组放入
tmp[pb++] = a[p1++];
while( p2 <= e)
tmp[pb++] = a[p2++];
for(i = 0;i < e-s+1; ++i)// 拷贝
a[s+i] = tmp[i];
}
// 归并排序
void MergeSort(int a[],int s,int e,int tmp[])
{
if( s < e) {
int m = s + (e-s)/2;
MergeSort(a,s,m,tmp);
MergeSort(a,m+1,e,tmp);
Merge(a,s,m,e,tmp);
}
}
int a[6] = { 2,6,3,4,5,1};
int b[6];
int main()
{
int size = sizeof(a)/sizeof(int),i;
MergeSort(a,0,size-1,b);
printf("%d",sum); // 输出
return 0;
}
相关文章
- Java 学习笔记 Junit4单元测试使用
- Java 学习笔记 网络编程 使用Socket传输文件 CS模式
- Java 学习笔记 使用并发包ReentrantLock简化生产者消费者模式代码
- Java 学习笔记 使用synchronized实现生产者消费者模式
- Java 学习笔记 观察者模式与适配者模式 监控文件夹
- Java 学习笔记 线程控制
- java学习笔记 线程的实现与同步
- Java 学习笔记 泛型
- Java 学习笔记 反射与迭代器
- Java 学习笔记 正则表达式
- Java 学习笔记 执行外部命令 包装类 枚举类型
- Java 学习笔记 判断一个数组是否有序
- Java 学习笔记 IO流与File操作
- Java小工具 根据文本批量修改文件名
- Java学习笔记 抽象类 接口 多态
- Java Scanner nextLine方法跳过
- Java 学习笔记 两大集合框架Map和Collection
- Java学习笔记——i++与++i问题
- Java学习笔记——判断字符Character类
- Java学习笔记——String与StringBuffer