算法設計與分析部分程序代碼
第三題：假設A[1……n]是一個有n個不同數的數組。若i<j且A[ i]>A[j]，則對偶（i，j）稱為A的一個逆序對。給出一個確定在n個元素的任何排列中逆序對數量的算法，要求時間復雜度為O（nlog2n）
算法分析：
因為題目中要求時間復雜度為O（nlog2n），所以不用暴力求解法和插入排序法。考慮用歸并排序法，只需要在歸并排序的基礎上添加一個變量counter用來逆序計數即可。具體實現見如下代碼。時間復雜度為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 << "請輸入數組的大小：" << endl;
- cin >> n;
- while (n <= 0) {
- cout << "輸入的數據有誤，請重新輸入：" << endl;
- cin >> n;
- }
- int* A = new int[n];
- cout << "請輸入數組A中的各個元素：" << endl;
- for (int i = 0; i < n; i++) {
- cin >> A[i];
- }
- number = MSort(A, n);
- cout << "A中逆序對的數量為：" << number;
- return 0;
- }
全部資料51hei下載地址：
第四次作業.docx
(256.54 KB, 下載次數: 9)
2019-12-11 10:32 上傳
點擊文件名下載附件
|
