`
chriszeng87
  • 浏览: 713966 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

归并排序求逆序对的代码(C语言)

阅读更多

#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;
}
 
分享到:
评论
2 楼 chriszeng87 2011-05-02  
忘了free掉malloc的内存了
    free(left);
    free(right);
    left = NULL;
    right = NULL;
1 楼 chriszeng87 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;

相关推荐

    归并求逆序对 C语言实现

    利用归并排序求逆序对,有分治和递归,不过没有主函数

    统计数组中逆序对

    统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计

    c语言实现的各种排序算法效率分析与比较及源代码

    各种排序算法效率分析比较及源...起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆排序。 通过输入不同的数据量和数据大小正序,逆序和乱序情况比较各种排序算法的效率。 其中树形选择排序算法有点错误。

    用C语言实现常用排序算法

    利用随机函数产生30000个随机整数,利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序,并且 (1) 统计每一种排序上机所花费的时间。 (2) 统计在完全正序,完全逆序情况下记录的比较...

    单链表的创建,排序,归并,插入删除定位和获得元素,计算元素个数,打印链表

    单链表的创建,排序,归并,插入删除定位和获得元素,计算元素个数,打印链表

    智能归并排序

    文中详细介绍并分析了归并排序算法的优缺点,针对归并算法的强制把数据划分两份进行了改进,提出按照数据本身具有的规律进行智能归并排序划分的方法。该方法将局部有序的记录块作为一组,避免对已经有序的数据划分再...

    c语言经典案例

    实例024 归并排序 29 实例025 二分查找 31 实例026 分块查找 32 实例027 哈希查找 34 实例028 斐波那契数列 37 实例029 哥德巴赫猜想 38 实例030 尼科彻斯定理 39 第4章 常用数据类型 41 实例031 数值型常量的使用 ...

    C程序范例宝典(基础代码详解)

    实例133 归并排序 198 4.3 查找算法 199 实例134 顺序查找 199 实例135 二分查找 201 实例136 分块查找 202 实例137 哈希查找 203 4.4 定理与猜想 206 实例138 斐波那契数列 206 实例139 角谷猜想...

    POJ 2299_AC

    在这里要用到__int64,也就是long long int

    传智播客扫地僧视频讲义源码

    本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...

    《数据结构 1800题》

    排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1(2分) ...

Global site tag (gtag.js) - Google Analytics