function.h

外排序 对于海量数据进行快速排序 然后利用败者树进行归并的算法的一个模板

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include "stack.h"
typedef int KeyType;

void swap(int & x,int & y)
{
	int m=x;
	x=y;
	y=m;
}
void insertsort(int c[],int low,int high){
	int u,v,w;
	
    int d[200];
		d[1]=c[low];
	for (u=2;u<=high-low+1;u++)
	{
		d[0]=c[low+u-1];
		for(v=u;d[0]<d[v-1];v--) d[v]=d[v-1];
		d[v]=d[0];
	}
	for (w=1;w<=high-low+1;w++){c[low+w-1]=d[w];}
}

int quicksort(int b[],int low,int high)
{
	int mid=(low+high)/2;
	if(low+11>=high) {insertsort(b,low,high);return 0;}
	else
	{
		int k,j;
		
		if(b[low]>b[mid]) swap(b[low],b[mid]);
		if(b[low]>b[high]) swap(b[low],b[high]);
		if(b[mid]>b[high]) swap(b[high],b[mid]);
        int temp=b[mid];
		swap(b[mid],b[high-1]);
		for (k=low,j=high-1;;)
		{


			while(b[++k]<temp);

			while(b[--j]>temp);

			if(k<j)

				swap(b[k],b[j]);
			else
				break;

		}
		swap(b[k],b[high-1]);

		return k;

	}

}
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MINKEY -1
#define MAXKEY 100
 

typedef int Status; 
 

typedef int Boolean;