首页 > 后端开发 > C++ > 正文

使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数

PHPz
发布: 2023-08-25 19:33:28
转载
1065 人浏览过

使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数

数组的反转表示;需要进行多少次更改才能将数组转换为其排序形式。当数组已经排序时,需要 0 次反转,而在其他情况下,如果数组反转,反转次数将达到最大。

为了解决这个问题,我们将遵循归并排序方法降低时间复杂度,采用分治算法。

输入

A sequence of numbers. (1, 5, 6, 4, 20).
登录后复制

输出

将数字升序排列所需的反转次数。

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)

输入 - 两个数组,谁已经合并,左,右和中间索引。

输出-按排序顺序合并的数组。

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)

输入 - 给定数组和临时数组,数组的左右索引。

输出 - 排序后的逆序对数量。

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(int arr[], 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;
}
int mergeSort(int arr[], 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;
}
int arrInversion(int arr[], int n) {
   int temp[n];
   return mergeSort(arr, temp, 0, n - 1);
}
int main() {
   int arr[] = {1, 5, 6, 4, 20};
   int n = 5;
   cout << "Number of inversions are "<< arrInversion(arr, n);
}
登录后复制

输出

Number of inversions are 2
登录后复制

以上是使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板