蛮力法和分治法求解逆序数

问题描述

给定一个随机数数组，求取这个数组中的逆序对总个数。要求时间效率尽可能高。

---

那么，何为逆序对？

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。 如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。 例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

---

解决方案

蛮力法,使用蛮力是最直接也最简单的方法，但是时间效率为O(n^2)。即从第1个元素，开始依次和后面每一个元素进行大小比较，若大于，则逆序对个数加1。

具体代码:

void reverse_num(int a[],int s ,int t) //直接蛮力递归法,T=O(n平方); { if (s == t) { return; } else { reverse_num(a, s+1, t); for (int i=s+1; i <= t; i++) { if (a[s] >a[i]) cout << "<" << a[s] <<","<< a[i] << ">" << " "; } return; } }

---

分治法: 此处可以借用归并排序的思想来解决此题，此时时间复杂度为O（n*logn）。归并排序，具体是先进行对半划分，直到最后左半边数组只有一个元素，右半边数组中也只有一个元素时，此时开始进行回溯合并。那么，计算逆序对个数的关键，就在于此处的回溯合并过程，当左半边元素（PS：回溯过程中，左半边和右半边元素均已是升序排序）中出现大于右半边元素时，那么左半边这个元素及其后面的所有元素均大于这个右半边元素，然后左半边这个元素的下标、左半边序列表的最后一个元素的下标及右半边这个元素的下标传入打印函数用for循环打印.

具体代码

void disp(int a[], int s,int mid,int temp)//输出关于a[j]与子序列a[i...mid]构成的逆序对 { for (int i = s; i <=mid; i++) { cout << "<" << a[i] << "," << temp << ">" << " "; } } void merge(int a[], int low, int mid, int high) //将a[low..mid]和a[mid+1..high]两个相邻的有序子序列归并成一个有序子序列a[low..high] { int i = low, j = mid + 1, k = 0; int* tampa; tampa = (int*)malloc((high - low + 1) * sizeof(int));//临时存放数组 while (i <= mid && j <= high)//扫描1表和2表 { if (a[i] <= a[j]) { tampa[k] = a[i]; i++; k++; } else { tampa[k] = a[j]; disp(a, i, mid, a[j]);//将此时关于a[j]对应的左半子序列中的逆序数打印 j++; k++; } } while (i <= mid)//将1表剩下的放进去 { tampa[k] = a[i]; i++; k++; } while (j <= high)//将2表剩下的放进去 { tampa[k] = a[j]; j++; k++; } for (k = 0, i = low; i <= high; i++, k++)//将tampa复制回a中 { a[i] = tampa[k]; } free(tampa); } void mergePass(int a[], int length, int n)//一趟二路归并排序 { int i; for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) { merge(a, i, i + length - 1, i + 2 * length - 1); } if (i + length - 1 < n)//若余下两个子表,后者长度小于length { merge(a, i, i + length - 1, n - 1);//归并这两个表 } } void merge_sort(int a[], int n)//二路归并算法 { int length; for (length = 1; length < n; length = 2 * length) { mergePass(a, length, n); } } int main() { int a[] = { 3,1,4,5,2 }; merge_sort(a, 5); return 0; }