算法-分治

分治的基本概念

把一个任务，分成形式和原任务相同，但规模更小的几个部分任务（通常是两个部分），分别完成，或只需要选一部完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。

称假币

16硬币，有可能有1枚假币，假币比真币轻。有一架天平，用最少称量次数确定有没有假币，若有的话，假币是哪一枚。

8 – 8 一称，发现无假币，或假币所在的那8枚
4 – 4 一称
2 – 2 一称
1 – 1 一称
数组排序任务可以如下完成：
- 1把前一半排序
- 2 把后一半排序
- 3 把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

#include <iostream>
using namespace std;
int a[10]={ 13,27,19,2,8,12,2,8,30,89};
int b[10];
// 合并两个有序数组
void Merage(int a[],int s,int m,int e,int tem[]){int pb=0;int p1=s;int p2=m+1;// 将两个有序数组合并成一个有序数组while(p1<=m&&p2<=e){if(a[p1]<a[p2])tem[pb++]=a[p1++];else tem[pb++]=a[p2++];}// 将剩余的元素添加到合并后的数组中while(p1<=m)tem[pb++]=a[p1++];while(p2<=e)tem[pb++]=a[p2++];// 将合并后的数组复制回原数组for(int i=0;i<e-s+1;i++)a[s+i]=tem[i];}
// 归并排序
void MerageSort(int a[],int s,int e,int tem[]){if(s<e){int m=s+(e-s)/2;// 递归地将数组分成两部分进行排序MerageSort(a,s,m,tem);MerageSort(a,m+1,e,tem);// 合并两个有序数组Merage(a,s,m,e,tem);}}
int main(){int size=sizeof(a)/sizeof(int);// 对数组进行排序MerageSort(a,0,size-1,b);// 输出排序后的数组for(int i=0;i<size;i++){cout<<a[i]<<",";}return 0;
}

2,2,8,8,12,13,19,27,30,89

归并排序的时间复杂度

对n个元素进行排序的时间：

T(n) = 2*T(n/2) + a*n = 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 14

复杂度O(nlogn)

快速排序

数组排序任务可以如下完成：

1设k=a[0], 将k挪到适当位置，使得比k小的元素都在k左边,比k大的元素都在k右边，和k相等的，不关心在k左右出现均可（O（n)时间完成）
2把k左边的部分快速排序
3把k右边的部分快速排序

#include <iostream>
using namespace std;
int a[] = { 93,27,30,2,8,12,2,8,30,89};
// 交换两个元素的值
void swap(int &a, int &b){int temp = a;a = b;b = temp;
}
// 快速排序函数
void quicksort(int a[], int s,int e){// 如果数组长度小于等于1，则直接返回if(e<=s){return;}// 选择第一个元素作为基准值int k=a[s];int i = s;int j=e;// 从数组的两端开始比较while(i!=j){// 从右向左找到第一个小于基准值的元素while(a[j]>=k&&i<j)j--;// 交换两个元素的位置swap(a[i],a[j]);// 从左向右找到第一个大于基准值的元素while(a[i]<=k&&i<j)i++;// 交换两个元素的位置swap(a[i],a[j]);}// 递归调用快速排序函数，对基准值左边的数组进行排序quicksort(a,s,i-1);// 递归调用快速排序函数，对基准值右边的数组进行排序quicksort(a,i+1,e);}
int main(){// 计算数组的大小int size= sizeof(a)/sizeof(int);// 调用快速排序函数quicksort(a,0,size-1);// 输出排序后的数组for(int i=0;i<size;i++)cout<<a[i]<<" ";cout<<endl;return 0;
}

2 2 8 8 12 27 30 30 89 93

输出前m大的数

描述

给定一个数组包含n个元素，统计前m大的数并且把这m个数从大到小输出。

输入

第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行包含一个整数m。m< n。

输出

从大到小输出前m大的数，每个数一行。

排序后再输出，复杂度O(nlogn)

用分治处理：复杂度O(n+mlogm)

思路：

把前m大的都弄到数组最右边，然后对这最右边m个元素排序，再输出

关键：

O(n)时间内实现把前m大的都弄到数组最右

引入操作 arrangeRight(k): 把数组(或数组的一部分）前k大的都弄到最右边

如何将前k大的都弄到最右边

1设key=a[0], 将key挪到适当位置，使得比key小的元素都在 key左边，比key大的元素都在key右边（线性时间完成）

2选择数组的前部或后部再进行arrangeRight操作

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 辅助函数：arrangeRight(k)
// 将数组的前k个元素移动到数组的右边
void arrangeRight(vector<int>& arr, int k) {int n = arr.size();nth_element(arr.begin(), arr.begin() + k, arr.end());rotate(arr.begin(), arr.begin() + k, arr.end());
}int main() {int n, m;cin >> n;vector<int> arr(n);for (int i = 0; i < n; ++i) {cin >> arr[i];}cin >> m;// 将前m大的数移动到数组的最右边arrangeRight(arr, n - m);// 输出前m大的数，从大到小for (int i = n - m; i < n; ++i) {cout << arr[i] << endl;}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。

左半边和右半边都是排好序的。比如，都是从大到小排序的。这样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的逆序个数。

#include <iostream>
#include <vector>using namespace std;// 辅助函数：合并两个有序数组并统计逆序数
int merge(vector<int>& nums, vector<int>& temp, int left, int mid, int right) {int i = left, j = mid + 1, k = left;int inv_count = 0;// 合并两个有序数组while (i <= mid && j <= right) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];inv_count += (mid - i + 1); // 统计逆序数}}// 将剩余的元素复制到临时数组while (i <= mid) {temp[k++] = nums[i++];}while (j <= right) {temp[k++] = nums[j++];}// 将临时数组中的元素复制回原数组for (i = left; i <= right; i++) {nums[i] = temp[i];}return inv_count;
}// 辅助函数：使用归并排序统计逆序数
int mergeSort(vector<int>& nums, vector<int>& temp, int left, int right) {int inv_count = 0;if (left < right) {int mid = (left + right) / 2;// 递归排序左半部分和右半部分inv_count += mergeSort(nums, temp, left, mid);inv_count += mergeSort(nums, temp, mid + 1, right);// 合并两个有序部分并统计逆序数inv_count += merge(nums, temp, left, mid, right);}return inv_count;
}// 主函数：计算排列的逆序数
int countInversions(vector<int>& nums) {vector<int> temp(nums.size());return mergeSort(nums, temp, 0, nums.size() - 1);
}int main() {int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}int inversions = countInversions(nums);cout << "number: " << inversions << endl;return 0;
}