标题: 算法设计与分析程序 [打印本页]
作者: 1371797138    时间: 2019-12-11 10:32
标题: 算法设计与分析程序
算法设计与分析部分程序代码

第三题：假设A[1……n]是一个有n个不同数的数组。若i<j且A[ i]>A[j]，则对偶（i，j）称为A的一个逆序对。给出一个确定在n个元素的任何排列中逆序对数量的算法，要求时间复杂度为O（nlog2n）
算法分析：
因为题目中要求时间复杂度为O（nlog2n），所以不用暴力求解法和插入排序法。考虑用归并排序法，只需要在归并排序的基础上添加一个变量counter用来逆序计数即可。具体实现见如下代码。时间复杂度为O（nlog2n）
  1. #include<iostream>
  2. using namespace std;
  3. int Merge(int* a, int al, int ah, int* b, int bl, int bh, int* c)
  4. {
  5.         int i, j, k;
  6.         int counter = 0;
  7.         i = al;
  8.         j = bl;
  9.         k = 0;
  10.         while (i <= ah && j <= bh) {
  11.                 if (a[i] <= b[j]) {
  12.                         c[k] = a[i];
  13.                         i++;
  14.                 }
  15.                 else {
  16.                         c[k] = b[j];
  17.                         j++;
  18.                         counter += ah - i + 1;
  19.                 }
  20.                 k++;
  21.         }
  22.         while (i <= ah) {
  23.                 c[k] = a[i];
  24.                 k++;
  25.                 i++;
  26.         }
  27.         while (j <= bh) {
  28.                 c[k] = b[j];
  29.                 k++;
  30.                 j++;
  31.         }
  32.         return counter;
  33. }
  34. int MergeSort1(int* A, int* temp, int low, int high)
  35. {
  36.         int mid, i;
  37.         if (low >= high) return 0;
  38.         mid = (low + high) / 2;
  39.         int ans1 = MergeSort1(A, temp, low, mid);
  40.         int ans2 = MergeSort1(A, temp, mid + 1, high);
  41.         int ans3 = Merge(A, low, mid, A, mid + 1, high, temp);
  42.         for (i = 0; i <= high - low; i++) {
  43.                 A[low + i] = temp[i];
  44.         }
  45.         return ans1 + ans2 + ans3;
  46. }
  47. int MSort(int* A, int n)
  48. {
  49.         int* temp = new int[n];
  50.         int ans = MergeSort1(A, temp, 0, n - 1);
  51.         free((char*)temp);
  52.         return ans;
  53. }
  54. int main()
  55. {
  56.         int n;
  57.         int number;
  58.         cout << "请输入数组的大小：" << endl;
  59.         cin >> n;
  60.         while (n <= 0) {
  61.                 cout << "输入的数据有误，请重新输入：" << endl;
  62.                 cin >> n;
  63.         }
  64.         int* A = new int[n];
  65.         cout << "请输入数组A中的各个元素：" << endl;
  66.         for (int i = 0; i < n; i++) {
  67.                 cin >> A[i];
  68.         }
  69.         number = MSort(A, n);
  70.         cout << "A中逆序对的数量为：" << number;
  71.         return 0;
  72. }
复制代码


全部资料51hei下载地址：
第四次作业.docx (256.54 KB, 下载次数: 9)





欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1