浏览 3537 次
锁定老帖子 主题:归并排序求逆序对的代码(C语言)
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-05-01
#include <stdio.h> #include <stdlib.h> #define MAX 32767 int merge(int *array, int p,int q,int r) { //归并array[p...q] 与 array[q+1...r] int tempSum=0; int n1 = q-p+1; int n2 = r-q; int* left = NULL; int* right = NULL; int i,j,k; left = ( int *)malloc(sizeof(int) * (n1+1)); right = ( int *)malloc(sizeof(int) * (n2+1)); for(i=0; i<n1; i++) left[i] = array[p+i]; for(j=0; j<n2; j++) right[j] = array[q+1+j]; left[n1] = MAX; //哨兵,避免检查每一部分是否为空 right[n2] = MAX; i=0; j=0; for(k=p; k<=r; k++) { if( left[i] <= right[j]) { array[k] = left[i]; i++; } else { array[k] = right[j]; j++; tempSum += n1 - i; printf("tempSum = %d\n", tempSum); } } return tempSum; } int mergeSort(int *array, int start, int end ) { int sum=0; if(start < end) { int mid = (start + end) /2; sum += mergeSort(array, start, mid); sum += mergeSort(array, mid+1, end); sum += merge(array,start,mid,end); } return sum; } int main(int argc, char** argv) { int array[5] = {9,1,0,5,4}; int inversePairNum; int i; inversePairNum = mergeSort(array,0,4); for( i=0; i<5; i++) printf("%d ", array[i]); printf("\nInverse pair num = %d\n", inversePairNum); return 0; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2011-05-01
for(k=p; k<=r; k++) {
if( left[i] <= right[j]) { array[k] = left[i]; i++; } else { array[k] = right[j]; j++; tempSum += n1 - i; printf("tempSum = %d\n", tempSum); } } 这部分是重点,思想是在合并left[0...n1] 和 right[0...n2]时,如果left[i] > right[j] ,则left 数组中第i个元素及后面的元素都将跟 right[j]构成逆序对,所以 tempSum += n1-i; |
|
返回顶楼 | |
发表时间:2011-05-02
忘了free掉malloc的内存了
free(left); free(right); left = NULL; right = NULL; |
|
返回顶楼 | |