用合并排序算法解决逆序数问题

     这段时间本人开始学习《算法导论》这本书，并且将书中的某点问题的解决写入自己的博客中，当成对自己的勉励,如果自己写的文章中有什么错误之处，请高手指正。

     分治法(divide-and-conquer)。为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。通常采用分治策略：1、分解：将原问题划分成一系列子问题；2、解决：递归地解各子问题。若子问题足够小，则直接求解；3、合并：将子问题的结果合并成原问题的解。

     逆序对问题：设A[1..n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j],则(i,j)就称为A中的一个逆序对。比如数组<2,3,8,6,1>有5个逆序对<2,1>,<3,1>,<8,1>,<6,1>,<8,6>。给出一个算法，它能用O(nlogn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。方法是修改合并排序算法解决这个问题,算法的时间复杂度是O(nlogn)。(《算法导论》（第二版）P24，思考题2-4：逆序对)

// sort.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <limits.h> //ÇóÄæÐòÊý int number = 0; void merge(int *A,int p,int q,int r); void mergeSort(int *A,int p,int r); void merge(int *A,int p,int q,int r){ int n1=q-p+1; int n2=r-q; int *L = (int*)malloc(sizeof(int)*(n1+2)); int *R = (int*)malloc(sizeof(int)*(n2+2)); int i,j,k; for(i=1;i<=n1;i++) L[i]=A[p+i-1]; for(j=1;j<=n2;j++) R[j]=A[q+j]; L[n1+1]=INT_MAX; R[n2+1]=INT_MAX; //printf("%d /n",INT_MAX); i=1,j=1; for(k=p;k<=r;k++) if(L[i]<=R[j]) A[k]=L[i++]; else{ A[k]=R[j++]; //关键在此处，当L[i]>R[j](i<j),因为L[1,n1]是有序的，所以 L[i+1]...L[n1]都大于R[j]，所以逆序对的数目等于n1-i+1. number += n1-i+1; } } void mergeSort(int *A,int p,int r){ int q; if(p<r){ q=(p+r)/2; mergeSort(A,p,q); mergeSort(A,q+1,r); merge(A,p,q,r); } } void insertion_sort(int *array,int length){ int i=0; int j=0; for(j=1;j<length-1;j++){ int key=array[j]; for(i=j-1;i>0 && array[i]>key;i--) array[i+1]=array[i]; array[i+1] = key; } } int main(int argc, char* argv[]) { int a[5]= {2,3,8,6,1}; mergeSort(a,0,4); for(int i=0;i<=4;i++) printf("%d ",a[i]); printf("number: %d ",number); system("pause"); return 0; }

最后

以上就是合适金针菇为你收集整理的用合并排序算法解决逆序数问题的全部内容，希望文章能够帮你解决用合并排序算法解决逆序数问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。