算法设计与分析部分程序代码
第三题：假设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)
|
