sort.h

可能是能找到的处理速度最快

#include<stdio.h>
#include<conio.h>
#include<io.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include"heap.h"
#include "gsort.h"

#define MAX_CHAR	1024*4

#define SUCCESS		0
#define NO_ENOUGH_MEM	1
#define FILE_OPEN_ERROR	2
#define FAIL	3
#define CHAR_TO_WORD(c1,c2)	((c1<<8)|(c2&0xFF))
#define SIZE_OF_AVTREE(len) (sizeof(AV_TREE)+len)
//#define SIZE_OF_AVTREE(len) (4*sizeof(AV_TREE *)+len+1)
//#define SIZE_OF_AVTREE(len) (3*sizeof(AV_TREE *)+sizeof(unsigned char)+len+1)

#define TRUE	1
#define FALSE	0
#define LINKS	1024

struct AV_TREE
{
	AV_TREE *left;
	AV_TREE *right;
	unsigned char count;
	char balance;
	char data[1];
};

struct CCacheNode
{
	AV_TREE *tree;
	unsigned short MidChar;//[2];
	int operator-(CCacheNode &node2)
	{
		return MidChar-node2.MidChar;
	}
	int operator-(unsigned short c)
	{
		return MidChar-c;
	}
	CCacheNode(AV_TREE *t=NULL,unsigned short c=0):tree(t),MidChar(c)
	{}
	CCacheNode(CCacheNode &node2)
	{
		tree=node2.tree;
		MidChar=node2.MidChar;
	}
};

class CCache:public CTree<CCacheNode>
{
public:
	AV_TREE *Add(AV_TREE *t)
	{
		CCacheNode node;
		node.tree=t;
		node.MidChar=*(unsigned short *)&t->data[0];
		CCacheNode *n=CTree<CCacheNode>::FindFirst(node);
		if (n)
			return n->tree;
		else
		{
			n=CTree<CCacheNode>::Add(node);
			if (n)
				return n->tree;
			else
				return NULL;
		}
	}
	CCache():CTree<CCacheNode>(true)
	{}
};


struct TREE_LINK
{
	AV_TREE *tree;
	//unsigned short MidChar;//[2];
	TREE_LINK *next;
};

#define MAX_MID	2048
#define NIL	(AV_TREE *)((char *)NULL-1)

struct COptions
{
	int DelDuplicate;
	int IncreadOrder;
	int NoEmptyLines;
	int ShowDulpicateLines;
	int Column;
	bool UseCache;
	bool SkipRanding;
	COptions()
	{
	// options .........
		IncreadOrder=TRUE;
		DelDuplicate=TRUE;
		NoEmptyLines=FALSE;
		Column=0;
		UseCache=true;
		SkipRanding=true;
		ShowDulpicateLines=FALSE;
	// .........
	}
};

class TXT_FILE:public COptions
{
protected:
	TREE_LINK *TreeHead,*TreeTial,*TreeMid;
	AV_TREE **RandArray;
	unsigned long ArraySize;
	unsigned long ArrayCount;
	unsigned long AccessMax;
	AV_TREE *MaxPointer;
	AV_TREE *Root;
	CCache Cache;
	unsigned long temp;
//	MY_HEAP *heap;
	inline AV_TREE *SAdd(AV_TREE *, AV_TREE *);
	inline AV_TREE *SAdd(char *);
	inline int RandAdd(char *);
	int Save(AV_TREE *, FILE *);
	AV_TREE *CreateNewNode(char *str)
	{
		AV_TREE *p=(AV_TREE *)new char[SIZE_OF_AVTREE(strlen(str))];
		if (p==NULL)
			return NULL;
		p->count=1;
		strcpy(p->data,str);
		p->left=NULL;
		p->right=NULL;
		p->balance=0;
		return p;
	}
public:
	int LoadFromFile( char *);
	int SaveToFile(char *);
	int Sort(void);
	AV_TREE *Add(char *);
	void Delete(AV_TREE *);
	COptions &operator=(COptions &option);
	TXT_FILE(void);
	~TXT_FILE(void);
};

class CMyTimer
{
	clock_t start;
	clock_t stop;
public:
	CMyTimer()
	{
		start=clock();
	}
	~CMyTimer()
	{
		stop=clock();
		printf("Time used:%9.3fs",(double)(stop-start)/CLOCKS_PER_SEC);
	}
};