欧美极品高清xxxxhd,国产日产欧美最新,无码AV国产东京热AV无码,国产精品人与动性XXX,国产传媒亚洲综合一区二区,四库影院永久国产精品,毛片免费免费高清视频,福利所导航夜趣136

標題: 算法設計與分析程序 [打印本頁]
作者: 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://m.raoushi.com/bbs/) Powered by Discuz! X3.1