归并排序&求逆序对数

归并排序：

基本原理：与插入排序使用的“增量”方法不同，归并排序使用另外一种策略：分治法

分治策略基本思想：将原问题划分成n个规模较小而结构与原问题相似的小问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤；

分解(Divide)：将原问题分解成这一系列子问题。

解决(Conquer)：递归地解各子问题。若子问题足够小，则直接求解。

合并(Combine)：将子问题的结果合并成原问题的解。

合并排序算法完全依照了上述模式，直观地操作如下：

分解：将n个元素分成各含n/2个元素的子序列；

解决：用合并排序法对两个子序列递归地排序；

合并：合并两个已排序的子序列以得到排序结果；

时间复杂度：O(nlgn)

代码实现：

#include<stdio.h>

#define N 10 
int A[N] ;
void Merge(/*A*/int p,int q,int r) ;
void MergeSort(/*A*/int p,int r) ;

int main(void)
{
int i,n ;

freopen("in.txt","r",stdin) ;

while(scanf("%d",&n) != EOF)
{
for(i = 0 ; i < n ; i++)
{
scanf("%d",&A[i]) ;
}

printf("You have input the List:\n") ;

for(i = 0 ; i < n ; i++)
{
printf("%-3d",A[i]) ;
}

printf("\n") ;

MergeSort(/*A*/0,n-1) ; //not n but n-1

printf("After Sort:\n") ;
for(i = 0 ; i < n ; ++i)
{
printf("%-3d",A[i]) ;
}
printf("\n\n") ;
}
return 0 ;
}


void MergeSort(/*A*/int p,int r) 
{
int q = 0 ;

if(p < r)
{
q = p + (r-p)/2 ; //notice
MergeSort(/*A*/p,q) ;
MergeSort(/*A*/q+1,r) ;
Merge(/*A*/p,q,r) ;
}
}

void Merge(/*A*/p,q,r) 
{
int L[N], R[N] ;
int i,j,k ;
int nLeft,nRight ;

nLeft = q + 1 - p ; //notice
nRight = r - q ; //notice

for(i = 0 ; i < nLeft ; ++i )
{
L[i] = A[p+i] ;
}

for(j = 0 ; j < nRight ; ++j)
{
R[j] = A[q+j+1] ;  //notice
}

i = 0 ;
j = 0 ;

for(k = p ; k < r && i<nLeft && j<nRight ; k++ )
{
if(L[i] <= R[j])
{
A[k] = L[i] ; 
i++ ;
}
else
{
A[k] = R[j] ; 
j++ ;
}
}

if(i >= nLeft)
{
for(; k <= r ; ++k,++j) 
{
A[k] = R[j] ;
}
}
else
{
for(; k <= r ; ++k,++i)
{
A[k] = L[i] ;
}
}
}

以上结论摘自《算法导论》

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

算法导论思考题：2-4逆序对

d）给出一个算法，它能用O(nlgn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。(提示：修改合并排序)

答：其实就是合并两个子序列时，出现右边元素小于左边元素的情况，亦即R[j]<L[i]时，出现逆序对。此时L[i+1...n1]里的元素均比R[j]大，而R[j]又在它们的后面。所以，此时的逆序对数：n1-i。后面的元素以此类推。

代码实现：

#include<stdio.h>

#define N 10 
int A[N] ;
int nTotalInversion = 0 ;
void Merge(/*A*/int p,int q,int r) ;
void MergeSort(/*A*/int p,int r) ;

int main(void)
{
int i,n ;

freopen("in.txt","r",stdin) ;

while(scanf("%d",&n) != EOF)
{
nTotalInversion = 0 ;
for(i = 0 ; i < n ; i++)
{
scanf("%d",&A[i]) ;
}

printf("You have input the List:\n") ;

for(i = 0 ; i < n ; i++)
{
printf("%-3d",A[i]) ;
}

printf("\n") ;

MergeSort(/*A*/0,n-1) ; //not n but n-1

printf("The Inversions are %d.\n\n",nTotalInversion) ;
}
return 0 ;
}


void MergeSort(/*A*/int p,int r) 
{
int q = 0 ;

if(p < r)
{
q = p + (r-p)/2 ; //notice
MergeSort(/*A*/p,q) ;
MergeSort(/*A*/q+1,r) ;
Merge(/*A*/p,q,r) ;
}
}

void Merge(/*A*/p,q,r) 
{
int L[N], R[N] ;
int i,j,k ;
int nLeft,nRight ;

nLeft = q + 1 - p ; //notice
nRight = r - q ; //notice

for(i = 0 ; i < nLeft ; ++i )
{
L[i] = A[p+i] ;
}

for(j = 0 ; j < nRight ; ++j)
{
R[j] = A[q+j+1] ;  //notice
}

i = 0 ;
j = 0 ;

for(k = p ; k < r && i<nLeft && j<nRight ; k++ )
{
if(L[i] <= R[j])
{
A[k] = L[i] ; 
i++ ;
}
else
{
nTotalInversion += nLeft - i ;  //here
A[k] = R[j] ; 
j++ ;
}
}

if(i >= nLeft)
{
for(; k <= r ; ++k,++j) 
{
A[k] = R[j] ;
}
}
else
{
for(; k <= r ; ++k,++i)
{
A[k] = L[i] ;
}
}
}

练习题6.5-8

大概思路：先利用每个链表的头元素来建立一个最大堆或者最大堆，然后再做类似堆排序的操作。但是这里要注意的是用到了额外空间数组B来储存排序后的元素。而且在交换树根和堆的最后一个元素之后，还要检查链表是否为空，从而更新heap-size[A]的值。时间复杂度：O(nlgk)

伪代码实现：

 

K-Road-MegerSort(A,k,n)
{
BuildMinHeap(A,k) ; //use the K List's first data to build the heap
i <- n ;
j <- 0 ;

nHeapSize <- k ;

while i > 0
do B[j] <- A[1]->data ;
   j <- j + 1 ; 

   if A[1]->next = NULL  //if the one List is empty. 
    then  exchange  A[1] <-> A[nHeapSize] ;   
  nHeapSize <- nHeapSize - 1 ;
  MinHeapify(A,1) ;
   else 
then  MinHeapify(A,1) ; 
   i <- i - 1 ;  
}

秒客网

归并排序&求逆序对数

相关文章