資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++ 語言
C# 語言
MongoDB 資料庫
MySQL 資料庫
Javascript 語言
PHP 語言
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究計算陣列中的逆序對
陣列的逆序對錶示：將陣列轉換為已排序形式需要進行多少次轉換。當陣列已排序時，需要進行 0 次轉換，而在另一種情況下，轉換次數將達到最大值，如果將陣列倒置。
為了解決此問題，我們將採用歸併排序方法來降低時間複雜度，並將其設為分治演算法。
輸入和輸出
Input: A sequence of numbers. (1, 5, 6, 4, 20). Output: The number of inversions required to arrange the numbers into ascending order. Here the number of inversions are 2. First inversion: (1, 5, 4, 6, 20) Second inversion: (1, 4, 5, 6, 20)
演算法
merge(array, tempArray, left, mid, right)
輸入：兩個陣列，已合併，以及 left、right 和 mid 索引。
輸出：已按排序順序合併的陣列。
Begin i := left, j := mid, k := right count := 0 while i <= mid -1 and j <= right, do if array[i] <= array[j], then tempArray[k] := array[i] increase i and k by 1 else tempArray[k] := array[j] increase j and k by 1 count := count + (mid - i) done while left part of the array has some extra element, do tempArray[k] := array[i] increase i and k by 1 done while right part of the array has some extra element, do tempArray[k] := array[j] increase j and k by 1 done return count End
mergeSort(array, tempArray, left, right)
輸入：給定一個數組和一個臨時陣列，以及陣列的 left 和 right 索引。
輸出 − 排序後的逆序對數。
Begin count := 0 if right > left, then mid := (right + left)/2 count := mergeSort(array, tempArray, left, mid) count := count + mergeSort(array, tempArray, mid+1, right) count := count + merge(array, tempArray, left, mid+1, right) return count End
示例
#include <iostream>
using namespace std;
int merge(intarr[], int temp[], int left, int mid, int right) {
int i, j, k;
int count = 0;
i = left; //i to locate first array location
j = mid; //i to locate second array location
k = left; //i to locate merged array location
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) { //when left item is less than right item
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
count += (mid - i); //find how many convertion is performed
}
}
while (i <= mid - 1) //if first list has remaining item, add them in the list
temp[k++] = arr[i++];
while (j <= right) //if second list has remaining item, add them in the list
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i]; //store temp Array to main array
return count;
}
intmergeSort(intarr[], int temp[], int left, int right) {
int mid, count = 0;
if (right > left) {
mid = (right + left)/2; //find mid index of the array
count = mergeSort(arr, temp, left, mid); //merge sort left sub array
count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
}
return count;
}
intarrInversion(intarr[], int n) {
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main() {
intarr[] = {1, 5, 6, 4, 20};
int n = 5;
cout<< "Number of inversions are "<<arrInversion(arr, n);
}輸出
Number of inversions are 2
更新時間： 16-6 月-2020
429 次瀏覽
廣告