C++求逆序對的辦法

C++求逆序對的辦法。本站提示廣大學習愛好者：（C++求逆序對的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++求逆序對的辦法正文

本文實例講述了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++算法設計的進修有所贊助。