C++求逆序对的方法

Xandy ·

更新时间:2024-09-21

· 637 次阅读

本文实例讲述了C++求逆序对的方法，分享给大家供大家参考之用。具体实现方法如下：


#include <iostream>
#include <vector>
using namespace std;
int array[] = {3, 9, 7, 4, 5, 2};
const int size = sizeof array / sizeof *array;
int temp[size];
//int numbers[size];
int reversePair(int *numbers, int start, int last, int &index, int &count)
{
 if(start == last)
 return 0;
 int mid = (last - start) / 2 + start;
 reversePair(numbers, start, mid, index, count);
 reversePair(numbers, mid + 1, last, index, count);
 for(int i = start; i <= last; i++)
 temp[i] = numbers[i];
 int index1 = start, index2 = mid + 1;
 index = start;
 while(index1 <= mid && index2 <= last) {
 if(temp[index1] > temp[index2]) {
  numbers[index] = temp[index2];
  count += mid - index1 + 1;
  index++;
  index2++;
 } else if(temp[index1] == temp[index2]) {
  numbers[index] = temp[index1];
  index++;
  index1++;
  index2++;
 } else if(temp[index1] < temp[index2]) {
  numbers[index] = temp[index1];
  index++;
  index1++;
 }
 }
 if(index1 <= mid) {
 while(index1 <= mid) {
  numbers[index] = temp[index1];
  index++;
  index1++;
 }
 } else {
 while(index2 <= last) {
  numbers[index] = temp[index2];
  index++;
  index2++;
 }
 }
 return count;
}
void main()
{
 int count = 0;
 int index = 0;
 reversePair(array, 0, size - 1, index, count);
 cout << "count = " << count << endl;
}

希望本文所述对大家C++算法设计的学习有所帮助。

您可能感兴趣的文章:C++实现string存取二进制数据的方法C++常用字符串分割方法实例汇总C++设计模式之工厂方法模式C++线程池的简单实现方法提高C++程序运行效率的10个简单方法C++实现八皇后问题的方法C++循环链表之约瑟夫环的实现方法C++实现二叉树非递归遍历方法实例总结C++链表倒序实现方法C++深度优先搜索的实现方法C++实现第K顺序统计量的求解方法C++实现二叉树遍历序列的求解方法C++实现raw_input的方法

c+ 逆序对方法 C++

1024 个赞