資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學使用歸併排序計算陣列中逆序對的 C/C++ 程式？
對給定陣列進行排序時發生的逆序對的數量稱為逆序對數。逆序對問題是一個經典問題，可以使用歸併排序演算法解決。在這個問題中，我們將計算陣列中每個元素左側比它大的元素的數量，並將計數新增到輸出中。此邏輯在歸併排序的合併函式中完成。
為了更好地理解主題，讓我們舉個例子。讓我們考慮兩個參與合併過程的子陣列 -
Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5解釋
陣列的逆序對數
給定一個數組，找出它的逆序對數。如果 (i < j) 且 (A[i] > A[j])，則對 (i, j) 稱為陣列 A 的逆序對。我們需要計算陣列 arr 中所有這樣的對。
例如，
陣列中有 5 個逆序對
(9,6), (9,4), (9,5), (6,4), (6,5)
1. 比較元素的值。
2. 如果較低索引處的數值較高，則遞增計數器。
3. 顯示結果。
示例
#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
int k = low, i = low, j = mid + 1;
int inversionCount = 0;
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
aux[k++] = arr[i++];
} else {
aux[k++] = arr[j++];
inversionCount += (mid - i + 1); // NOTE
}
}
while (i <= mid)
aux[k++] = arr[i++];
for (int i = low; i <= high; i++)
arr[i] = aux[i];
return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
if (high == low) // if run size == 1
return 0;
int mid = (low + ((high - low) >> 1));
int inversionCount = 0;
inversionCount += MergeSort(arr, aux, low, mid);
inversionCount += MergeSort(arr, aux, mid + 1, high);
inversionCount += Merge(arr, aux, low, mid, high);
return inversionCount;
}
int main() {
int arr[] = { 1, 9, 6, 4, 5 };
int N = 5;
int aux[N];
for (int i = 0; i < N; i++)
aux[i] = arr[i];
printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
return 0;
}
更新於: 2019年8月19日
234 次檢視
廣告