当前位置：首页 > article >正文

算法-分治

article 2025/3/26 8:05:14

分治的基本概念

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

称假币

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;
}