归并排序及其应用两则

简介:归并排序(merging sort)的时间复杂度为O(nlogn),是一种稳定的排序方法。常用的2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列,递归算法形式简洁,简单易用。

应用1:求逆序对数

设a[1…n]是一个包含n个不同数的数组,对于i<j如有a[i]>a[j],则称(i,j)为一个逆序对。出题方式很多,比如直接求一个序列中逆序对的个数;比如交换原序列中相邻两元素位置使之成为单调不下降序列,求交换次数等等。当然,求逆序对数的方法也很多,但时间复杂度不大于O(nlogn)就只有归并排序和平衡二叉树了吧,显然归并排序实现起来更加简单,代码如下所示。

#include <stdio.h>

#define MAX 50001
int temp[MAX];
int count, n;

void Merge(int *array, int s, int m, int t)
{
	int i=s, j, k;
	for (j=m+1,k=s; s<=m&&j<=t; ++k)
	{
		if (array[s]<=array[j])
			temp[k] = array[s++];
		else
		{
			temp[k] = array[j++];
			count += m-s+1;  //record the inversion pairs
		}
	}
	while (s<=m)
		temp[k++] = array[s++];
	while (j<=t)
		temp[k++] = array[j++];
	while (i<=t)
		array[i] = temp[i++];
}

void MergeSort(int *array, int s, int t)
{
	if (s!=t)
	{
		int m;
		m = (s+t)/2;
		MergeSort(array,s,m);
		MergeSort(array,m+1,t);
		Merge(array,s,m,t);
	}
}

int main()
{
	int i;
	while (1)
	{
		count = 0;
		printf("Input the number(1~50000):");
		scanf("%d", &n);
		if (n==0)
			break;
		int array[n+1];
		for (i=1; i<=n; i++)
			scanf("%d", &array[i]);
		printf("The initial sequence is: ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\n");
		MergeSort(array, 1, n);
		printf("The sorted sequence is:  ");
		for (i=1; i<=n; i++)
			printf("%d  ", array[i]);
		printf("\nThe count of inversions is: %d\n", count);
	}
	return 0;
}

p.s.上述代码如果编译有错误的只需将第50行的int array[n+1];换成int array[MAX];就可以了,支持不定长数组是C99标准新增的特性,我平时使用的GCC是完全支持C99标准的,所以编译没问题,但是VS就不行了,呵呵。

应用2:其实也是求逆序对,只不过比较隐晦的那种

Continue reading

C语言逐行读取文件

C语言可以说是我学习的第一门语言,不过似乎也是忘的最多的一门语言,自从因为项目需要重新拾起C语言,我的噩梦就开始了。

依稀记得大二学习数据结构时编程解决“约瑟夫环”、“迷宫”等问题后的骄傲,认为C简直就是天神一般的语言,如此强大,如此让人着迷。后来学了C++,后来开始搞.net,后来自学了CSS和简要的PHP,当C快被我抛弃的时候,由于种种原因,被分到一个新的项目,重新开始做C编程。

继语法树构造完之后自我放假了好久,这两天开工写了一段文件处理的代码,发现以前学习的C语言知识确实完全还给老师了,小崔,我对不起你啊,下面是遭遇问题小结。

1. 字符型转化为整型

如果不是正好用到,我想我永远不会知道居然还有标准库函数可以将字符串转换为任意类型(整型、长整型、浮点型等),我太无知了,我居然只知道强制类型转换,却从来没想过对于字符串要怎样处理,不过还好有人跟我一样不知道,哼哼。

atof():将字符串转换为双精度浮点型值;
atoi():将字符串转换为整型值;
atol():将字符串转换为长整型值;
strtod():将字符串转换为双精度浮点型值,并报告不能被转换的所有剩余数字;
strtol():将字符串转换为长整值,并报告不能被转换的所有剩余数字;
strtoul():将字符串转换为无符号长整型值,并报告不能被转换的所有剩余数字。

用法非常简单,举例说明如下:
Continue reading

Linux下的Socket编程

上两周的进度终于验收完毕,结果怎样我就不想多说了,总之自己学到了东西,自己做完了要求的任务,自己认为无愧于心就好。

记得一个很崇拜的师兄曾问我后悔了吗,记得豆豆曾告诉我GX并不像我想的那么单纯,直到今天我才真正领悟其中的含义。

明白只要离开了大学就算是进入了社会,不管是读研也好、工作也好,都已经不能再率性而为了。

委屈和眼泪再也不能成为逃脱的理由,我又一次选择了鸵鸟的策略,把头深深的埋进土里,看不见的就是不存在的。

好了,发了一通无用的牢骚,现在开始进入主题,关于linux下socket编程方法我就不多说了,书籍和网上的资料很多,这里只是小结下自己编程中遇到的问题,以防再犯。

1.推荐两本很有用的书

由于我前两周主要是做的linux下的socket编程和进程管理,都是以前没有涉及过的东西,从图书馆借阅了好多资料,在能够找到的资源中,有两本是值得推荐的。

一本是《实战linux socket编程》,很适合初学者,讲的十分全面而且容易理解,再配上网上流传的一篇《BSD Socket简易入门手册》,基本就可以上手写代码了。另外一本是《linux系统编程》,也是比较通俗的入门的书,讲的非常好,而且这本书可以直接看原版《Linux System Programming》,也不需要太强的英语基础。 Continue reading

自己做的美女找茬外挂

想起大四下学期无聊的日子,常常在寝室疯狂玩“美女找茬”游戏,当时水平比较弱,自己玩每次都输,然后就号召起全体舍友,经常8只眼睛一起菜屏幕后面的对手,视力已经提升到1.0。

每次感觉自己不道德时候就说“人家那边还不知道几个人呢”,游戏嘛,旨在玩乐,虽然我们有点小作弊,但是我们很开心啊。

要说最不开心的,估计就属泡面同学了,因为她心爱的笔记本每次都会被我们点的面目全非,然后就嚷嚷着让我们帮她擦显示器,虽然这话实际不起什么所用,反正我是从来没擦过, Continue reading

C#实现窗体截图(代码+效果)

最近在做一个QQ找茬游戏的外挂,第一步便是窗体截图,因为以前从来没有涉及过图像处理方面的知识,感觉还是有点小难的。理论上讲做这个东西用C++会比较简单,但由于我一看到MFC就眼晕,所以还是选择了熟悉的C#语言。

C#写截图要用到传说中的.net没有提供的叫做BitBlt的函数,而BitBlt函数要求有被截窗体的设备驱动器句柄,需要用GetDC(hwnd)函数获得,当然之后还要用ReleaseDC(hdc)释放。但是要得到窗体的设备驱动器句柄又要求有被截窗体的窗体句柄,需要调用FindWindow()函数,有了窗体句柄再用GetClientRect()同时可以得到窗体的大小。看到这么多API,给我的第一感觉是头大。

然后我想到最简单的方法是用google搜到代码,直接考上去就得了,搜了半天却发现网上鲜有C#窗体截图的东西,铺天盖地都是屏幕截图。 Continue reading