鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

第七章快速排序之“区间模糊排序FUZZY-SORT”(待改进。。。)

来源:互联网 作者:佚名 时间:2015-09-25 05:38
快速 排序 可以看成 区间 大小为1的 模糊 排序 。 #include string.h#include time.h#define BUFFER_SIZE 10typedef struct{int start;int end;}Node; int FuzzyPartition(Node *a,int p,int r){Node tmp;int i=0;int j=0;int k=0;Node x;i=p-1;x.start=a[r]

快速排序可以看成区间大小为1的模糊排序

#include <string.h>
#include <time.h>

#define BUFFER_SIZE 10

typedef struct
{
	int start;
	int end;
}Node; 

int FuzzyPartition(Node *a,int p,int r)
{
	Node tmp;
	int i=0;
	int j=0;
	int k=0;
	Node x;
	
	i=p-1;
	x.start=a[r].start;
	x.end=a[r].end;
	for(j=p;j<r;j++)
	{
		if(a[j].end<x.start)
		{//在所选主元区间左边 
			i++;
			tmp.start=a[i].start;
			tmp.end=a[i].end;
			a[i].start=a[j].start;
			a[i].end=a[j].end;
			a[j].start=tmp.start;
			a[j].end=tmp.end;
		}
		else if(a[j].start>x.end)
		{//在所选主元区间右边 
			;
		}
		else
		{//与所选主元区间有重叠,则将主元区间更新为重叠部分 
			x.start=(a[j].start>=x.start)?a[j].start:x.start;
			x.end=(a[j].end<=x.end)?a[j].end:x.end;
		}
	}
	
	i++;
	tmp.start=a[i].start;
	tmp.end=a[i].end;
	a[i].start=a[j].start;
	a[i].end=a[j].end;
	a[j].start=tmp.start;
	a[j].end=tmp.end;
	
	return i;
}


void FuzzySort(Node *a,int p,int r)
{
	int q=0;
	if(p<r)
	{
		q=FuzzyPartition(a,p,r);
		FuzzySort(a,p,q-1);
		FuzzySort(a,q+1,r);
	}
}

int main()
{
	int i=0;
	int j=0;
	Node a[BUFFER_SIZE]; 
	//随机生成数组 
	srand((unsigned)time(NULL));
	for(j=0;j<BUFFER_SIZE;j++)
	{
		a[j].start=rand()%100;
		a[j].end=rand()%100+100;
	} 
	printf("随机生成的区间:\n");
	for(i=0;i<BUFFER_SIZE;i++)
	{
		printf("%d %d\n",a[i].start,a[i].end);
	} 
	printf("\n");
	
	FuzzySort(a,0,BUFFER_SIZE-1);
	printf("对区间进行模糊排序:\n"); 
	for(i=0;i<BUFFER_SIZE;i++)
	{
		printf("%d %d\n",a[i].start,a[i].end);
	}
	
	system("pause");
	return 0;
} 


上一篇:J2ME概念介绍
下一篇:RMQ问题ST算法
网友评论
<