首页 > 编程语言 > 详细

求数组的逆序对

时间:2018-05-22 20:12:01      阅读:41      评论:0      收藏:0      [点我收藏+]

标签:include   数组   code   ret   ostream   OS   left   pre   for   

#include<iostream>
#include<vector>
using namespace std;

void merge(vector<int>&input, int left, int right, int mid, vector<int>&temp,int &count){
    int i = left;
    int j = mid+1;
    int t = 0;//t=left也可以,因为最终都是要赋值给input[left]
    
    while (i<=mid&&j<=right){
        if (input[i] > input[j]){
            temp[t++] = input[j++];
            count += mid+1-i;//input[i]>input[j]时,左边比input[i]大的均与input[j]构成逆序对,总共mid+1-i
        }
        else{
            temp[t++] = input[i++];
        }
    }
    while (i <= mid){
        temp[t++] = input[i++];
    }
    while (j <= right){
        temp[t++] = input[j++];
    }
    t = 0;//t=left
    while (left <= right){
        input[left++] = temp[t++];
    }
    
}

void mergesort(vector<int>&input, int left, int right, vector<int>&temp,int &count){
    if (left < right){
        int mid = (left + right) / 2;
        mergesort(input, left, mid, temp,count);
        mergesort(input, mid + 1, right, temp,count);
        merge(input, left, right, mid, temp,count);
    }
}
int main(){
    vector<int>a = { 7,2,5,4};
    vector<int>b(a.size(), 0);
    
    int count = 0;
    mergesort(a, 0, a.size() - 1, b,count);
    for (int i = 0; i < a.size(); i++){
        cout << a[i] << endl;
    }
    
    cout << count << endl;
    system("pause");
    return 0;
}

 

求数组的逆序对

标签:include   数组   code   ret   ostream   OS   left   pre   for   

原文:https://www.cnblogs.com/inception6-lxc/p/9073740.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号