|
|
算法設(shè)計(jì)與分析部分程序代碼
第三題：假設(shè)A[1……n]是一個(gè)有n個(gè)不同數(shù)的數(shù)組。若i<j且A[ i]>A[j]，則對(duì)偶（i，j）稱為A的一個(gè)逆序?qū)�。給出一個(gè)確定在n個(gè)元素的任何排列中逆序?qū)?shù)量的算法，要求時(shí)間復(fù)雜度為O（nlog2n）
算法分析：
因?yàn)轭}目中要求時(shí)間復(fù)雜度為O（nlog2n），所以不用暴力求解法和插入排序法�？紤]用歸并排序法，只需要在歸并排序的基礎(chǔ)上添加一個(gè)變量counter用來(lái)逆序計(jì)數(shù)即可。具體實(shí)現(xiàn)見(jiàn)如下代碼。時(shí)間復(fù)雜度為O（nlog2n）
- #include<iostream>
- using namespace std;
- int Merge(int* a, int al, int ah, int* b, int bl, int bh, int* c)
- {
- int i, j, k;
- int counter = 0;
- i = al;
- j = bl;
- k = 0;
- while (i <= ah && j <= bh) {
- if (a[i] <= b[j]) {
- c[k] = a[i];
- i++;
- }
- else {
- c[k] = b[j];
- j++;
- counter += ah - i + 1;
- }
- k++;
- }
- while (i <= ah) {
- c[k] = a[i];
- k++;
- i++;
- }
- while (j <= bh) {
- c[k] = b[j];
- k++;
- j++;
- }
- return counter;
- }
- int MergeSort1(int* A, int* temp, int low, int high)
- {
- int mid, i;
- if (low >= high) return 0;
- mid = (low + high) / 2;
- int ans1 = MergeSort1(A, temp, low, mid);
- int ans2 = MergeSort1(A, temp, mid + 1, high);
- int ans3 = Merge(A, low, mid, A, mid + 1, high, temp);
- for (i = 0; i <= high - low; i++) {
- A[low + i] = temp[i];
- }
- return ans1 + ans2 + ans3;
- }
- int MSort(int* A, int n)
- {
- int* temp = new int[n];
- int ans = MergeSort1(A, temp, 0, n - 1);
- free((char*)temp);
- return ans;
- }
- int main()
- {
- int n;
- int number;
- cout << "請(qǐng)輸入數(shù)組的大�。�" << endl;
- cin >> n;
- while (n <= 0) {
- cout << "輸入的數(shù)據(jù)有誤，請(qǐng)重新輸入：" << endl;
- cin >> n;
- }
- int* A = new int[n];
- cout << "請(qǐng)輸入數(shù)組A中的各個(gè)元素：" << endl;
- for (int i = 0; i < n; i++) {
- cin >> A[i];
- }
- number = MSort(A, n);
- cout << "A中逆序?qū)Φ臄?shù)量為：" << number;
- return 0;
- }
51hei.png (63.88 KB, 下載次數(shù): 67)
下載附件
2019-12-11 16:03 上傳
全部資料51hei下載地址：
第四次作業(yè).docx
(256.54 KB, 下載次數(shù): 9)
2019-12-11 10:32 上傳
點(diǎn)擊文件名下載附件
下載積分: 黑幣 -5
|
評(píng)分
-
查看全部評(píng)分
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
