归并排序 逆序对的实现
程序员文章站
2024-03-16 11:59:34
...
归并排序 逆序对的实现
#include<iostream>
using namespace std;
long long mergeSort(int a[], int n);
long long _mergeSort(int a[], int l, int r);
long long merge(int a[], int l, int mid, int r);
void test_mergeSort();
void test_mergeSort2();
void test_mergeSort3();
int main(){
test_mergeSort();
test_mergeSort2();
test_mergeSort3();
return 0;
}
//////////////////////////////////////////////////////////////////////////
// 归并排序
// 计算逆序数对的结果以long long返回
// 对于一个大小为N的数组, 其最大的逆序数对个数为 N*(N-1)/2, 非常容易产生整型溢出
// 逆序对个数最多不超过:(n-1)+(n-2)+(n-3)+...+2+1=n*(n-1)/2;
long long mergeSort(int a[], int n){
return _mergeSort(a, 0, n - 1);
}
long long _mergeSort(int a[], int l, int r){
if (l >= r) return 0;
int mid = l + (r - l) / 2;
long long result_l = _mergeSort(a, l, mid);//a[l...mid]范围内的逆序对
long long result_r = _mergeSort(a, mid + 1, r);//a[mid+1...r]范围内的逆序对
return result_l + result_r + merge(a, l, mid, r);
}
long long merge(int a[], int l, int mid, int r){
int *aux = new int[r - l + 1];//辅助数组
for (int i = l; i <= r; ++i)
aux[i - l] = a[i];
long long result = 0;//逆序对个数
int i = l, j = mid + 1;//左右块的起始索引分别为i,j
for (int k = l; k <= r; ++k){
if (i > mid){ a[k] = aux[j - l]; j++; }//左块索引超出索引范围
else if (j > r){ a[k] = aux[i - l]; i++; }//右块索引超出索引范围
else if (aux[i - l] <= aux[j - l]){ a[k] = aux[i - l]; i++; }//左半部分 <= 右半部分
else { a[k] = aux[j - l]; j++;//左半部分 > 右半部分
result += (long long)(mid - i + 1);//右半部分元素小,故j所指的右半部分的当前元素a[j] < 左半部分当前元素a[i]以及左半部分i之后的所有剩余元素,那么当前逆序对个数就是 mid-i+1; [l...i...mid; mid+1...j...r]
}
}
delete[] aux;//删掉new的辅助数组aux
return result;
}
//////////////////////////////////////////////////////////////////////////三个测试用例
void test_mergeSort(){
int a[] = { 4, 36, 12, 3, 16, 5, 7, 0, 12, 4, 16 };
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
cout << "逆序对个数为:" << mergeSort(a, n) << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
}
void test_mergeSort2(){
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
cout << "逆序对个数为:" << mergeSort(a, n) << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
}
void test_mergeSort3(){
int a[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
cout << "逆序对个数为:" << mergeSort(a, n) << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << "\t";
cout << endl;
}
上一篇: NNI样例实践-以mnist-pytorch为样例
下一篇: 回溯法之n皇后问题
推荐阅读