sort.c

自己写的数据结构中排序程序

#include<stdio.h>
#include<math.h>

#define LSIZE 30

typedef struct tagLIST
{
	int elem[LSIZE];
	int count;
}LIST;

void initl(LIST *pl);
int insertl(LIST *pl, int idx, int num);
void printl(LIST *pl);
void printlse(LIST *pl, int is, int ie);


typedef void (*FUNCSORT)(LIST *pl);
typedef struct tagSORT_METHOD
{
   FUNCSORT pfsort;
   char stitle[20];
}SORT_METHOD;


void insertionsort(LIST *pl);
void bubblesort(LIST *pl);
void shellsort(LIST *pl);
void rshellsort(LIST *pl);
void shellpass(LIST *pl, int i);
void mergesort(LIST *pl);
void rmergepass(LIST *pl, int idxs, int idxe);
void quicksort(LIST *pl);
void quickpass(LIST *pl, int left, int right);
void selectionsort(LIST *pl);
void heapsort(LIST *pl);
void adjustheap(LIST *pl, int is, int ie);

int main(void)
{
   SORT_METHOD smarr[9]=
   {
      { insertionsort, "insertion sort" },
      { bubblesort, "bubble sort" },
      { shellsort, "shell sort" },
      { rshellsort, "rshell sort" },
      { mergesort, "merge sort" },
      { quicksort, "quick sort" },
      { selectionsort, "selection sort" },
      { heapsort, "heap sort" },
      { NULL, ""}
   };

	int na[9]={82, 16, 9, 95, 27, 75, 42, 69, 34}, i, j;
   LIST lst;

   for(i=0;smarr[i].pfsort!=NULL;i++)
   {
      initl(&lst);
	   for(j=0;j<9;j++)
		   insertl(&lst, j, na[j]);

      printf("---- ");
      printf("%s", smarr[i].stitle);
      printf(" ----\n");

      printl(&lst);
	   smarr[i].pfsort(&lst);
	   printl(&lst);

      printf("Press ENTER to continue ...");
	   getchar();
   }

   return 0;
}

void initl(LIST *pl)
{
	pl->count=0;
}

int insertl(LIST *pl, int idx, int num)
{
	int i;
	if(pl->count==LSIZE)
		return 1;
	if(idx>pl->count)
		idx=pl->count;
	for(i=pl->count-1;i>=idx;i--)
		pl->elem[i+1]=pl->elem[i];
	pl->elem[idx]=num;
	pl->count++;
	return 0;
}

void printl(LIST *pl)
{
	int i;
	for(i=0;i<pl->count;i++)
		printf("%5d", pl->elem[i]);
	printf("\n");
}

void printlse(LIST *pl, int is, int ie)
{
	int i;
	for(i=0;i<is;i++)
		printf("%5s", "");
	for(i=is;i<=ie;i++)
		printf("%5d", pl->elem[i]);
	for(i=ie+1;i<pl->count;i++)
		printf("%5s", "");
	printf("\n");
}

void insertionsort(LIST *pl)
{
	int i, j, temp;

	for(i=1;i<pl->count;i++)
	{
		j=i;
		temp=pl->elem[i];
		while(j>0 && temp<pl->elem[j-1])
		{
			pl->elem[j]=pl->elem[j-1];
			j--;
		}
		pl->elem[j]=temp;

		printl(pl);
	}
}

void bubblesort(LIST *pl)
{
	int i, j, temp, leindex;

	i=pl->count-1;
	while(i>0)
	{	leindex=0;
		for(j=0;j<i;j++)
			if(pl->elem[j]>pl->elem[j+1])
			{
				temp=pl->elem[j];
				pl->elem[j]=pl->elem[j+1];
				pl->elem[j+1]=temp;

				leindex=j;
			}
		i=leindex;

		printf("last exchance index: %d\n", leindex);
		printl(pl);
	}
}

void shellsort(LIST *pl)
{
	int i, j, k, h, temp;

	i=(int)floor(log((double)(pl->count))/log(2.0));
	while(i>=1)
	{
      h=(int)pow(2.0, (double)i)-1;
		for(j=h;j<pl->count;j++)
		{
			temp=pl->elem[j];
			k=j-h;
			while(k>=0)
			{
				if(pl->elem[k]<=temp)
					break;
				pl->elem[k+h]=pl->elem[k];
				k=k-h;
			}
			pl->elem[k+h]=temp;
		}
		i--;

		printf("increment: %d\n", h);
		printl(pl);
	}
}

void rshellsort(LIST *pl)
{
	shellpass(pl, 1);
}

void shellpass(LIST *pl, int i)
{
	int j, k, h, temp;
	h=(int)pow(2.0, i)-1;
	if(h>pl->count) return;

	shellpass(pl, i+1);

	for(j=h;j<pl->count;j++)
	{	temp=pl->elem[j];
		k=j-h;
		while(k>=0)
		{
			if(pl->elem[k]<=temp)
				break;
			pl->elem[k+h]=pl->elem[k];
			k=k-h;
		}
		pl->elem[k+h]=temp;
	}
	i--;

	printf("increment: %d\n", h);
	printl(pl);
}

void mergesort(LIST *pl)
{
	rmergepass(pl, 0, pl->count-1);
}

void rmergepass(LIST *pl, int idxs, int idxe)
{
	int idxm, left, right, temp, i;

	if(idxs==idxe)
		return;

	idxm=(idxs+idxe)/2;
	rmergepass(pl, idxs, idxm);
	rmergepass(pl, idxm+1, idxe);

 	printl(pl);

	left=idxs;
	right=idxm+1;

	while(!(left==right || right==idxe+1))
	{
		if(pl->elem[left]>pl->elem[right])
		{
			temp=pl->elem[right];
			for(i=right-1;i>=left;i--)
				pl->elem[i+1]=pl->elem[i];
			pl->elem[left]=temp;
			right++;
		}
		left++;
	}
}

void quicksort(LIST *pl)
{
	quickpass(pl, 0, pl->count-1);
}

void quickpass(LIST *pl, int left, int right)
{
	int scanup, scandown, temp;

	if(left>=right) return;

	temp=pl->elem[left];
	scanup=left;
	scandown=right;
	while(scanup<scandown)
	{
		while(temp<pl->elem[scandown] && scanup<scandown)
			scandown--;
      if(scanup<scandown)
   	   pl->elem[scanup++]=pl->elem[scandown];
		while(temp>pl->elem[scanup] && scanup<scandown)
			scanup++;
      if(scanup<scandown)
   	   pl->elem[scandown--]=pl->elem[scanup];
	}
	pl->elem[scanup]=temp;

	printl(pl);

	quickpass(pl, left, scanup-1);
	quickpass(pl, scandown+1, right);
}

void selectionsort(LIST *pl)
{
	int i, j, min, idxofmin, temp;

	for(i=0;i<pl->count-1;i++)
	{
		min=pl->elem[i];
		idxofmin=i;
		for(j=i+1;j<pl->count;j++)
			if(min>pl->elem[j])
			{
				min=pl->elem[j];
				idxofmin=j;
			}
		temp=pl->elem[i];
		pl->elem[i]=pl->elem[idxofmin];
		pl->elem[idxofmin]=temp;

		printl(pl);
	}
}

void heapsort(LIST *pl)
{
   int i, temp;

   for(i=pl->count/2-1;i>=0;i--)
   {
      adjustheap(pl, i, pl->count-1);
   }

   for(i=pl->count-1;i>0;i--)
   {
      temp = pl->elem[i];
      pl->elem[i] = pl->elem[0];
      pl->elem[0] = temp;

      adjustheap(pl, 0, i-1);
      printl(pl);
   }
}

void adjustheap(LIST *pl, int is, int ie)
{
   int lchild, rchild, idxofmax, idxcur, temp;

   idxcur = is;
   idxofmax = -1;

   while(idxcur != idxofmax)
   {
      lchild = idxcur*2+1;
      rchild = idxcur*2+2;

      idxofmax = idxcur;
      if(lchild<=ie && pl->elem[idxofmax]<pl->elem[lchild])
      {
         idxofmax = lchild;
      }
      if(rchild<=ie && pl->elem[idxofmax]<pl->elem[rchild])
      {
         idxofmax = rchild;
      }
      if(idxofmax != idxcur)
      {
         temp = pl->elem[idxcur];
         pl->elem[idxcur] = pl->elem[idxofmax];
         pl->elem[idxofmax] = temp;
         idxcur = idxofmax;
         idxofmax = -1;
      }
   }
}