目录
把一个任务,分成形式和原任务相同,但规模更小的几个部分任务(通常是两个部分),分别完成,或只需要选一部完成。然后再处理完成后的这一个或几个部分的结果,实现整个任务的完成。
16硬币,有可能有1枚假币,假币比真币轻。有一架天 平,用最少称量次数确定有没有假币,若有的话,假 币是哪一枚。
这个我们之前应该接触过,解决办法就是一次一次不断分解,两边先称8个,然后4个,然后两个,最后一个,就能得出结果。
步骤
数组排序任务可以如下完成:
代码实现
#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个元素进行排序的时间:
复杂度O(nlogn)
步骤
数组排序任务可以如下完成:
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),就不做过多介绍。
给定一个数组包含n个元素,统计前m大的数并且把这m个数从大到小输出。
第一行包含一个整数n,表示数组的大小。n < 100000。 第二行包含n个整数,表示数组的元素,整数之间以一个空格分开 。每个整数的绝对值不超过100000000。 第三行包含一个整数m。m < n。
从大到小输出前m大的数,每个数一行。
解题思路
首先是可以选择先排序再输出,复杂度是 O(nlogn);但是除此之外,还可以选择用分治的思想把前m大的都弄到数组最右边,然后对这最右边m个元素排序, 再输出。这样的话复杂度是O(n+mlogm),在大部分情况下,比第一种解法要更好。
操作
如何将前k大的都弄到最右边
具体如下所示
#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;
}