sort.h

我的一个课程设计

typedef struct
{
KeyType key;
}DataTypeSort;
 //////////////直接插入排序算法////////////	
void InsertSort(DataTypeSort a[],int n) 
{
int i,j;
DataTypeSort temp;
for (i=0;i<n-1;i++)
{
temp=a[i+1];
j=i;
while(i>-1&&temp.key<a[j].key)
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}

}

////////////////////////希尔排序/////////////////////////
void ShellSort(DataTypeSort a[],int n)
{
DataTypeSort temp;
int i,k,j,span;

span=n;

for (span=n;span>0;)
{
span=span/2;
for(k=0;k<span;k++)
{
for(i=k;i<n-span;i=i+span)
{
temp=a[i+span];
j=i;
while(j>-1&&temp.key<=a[j].key)
{
a[j+span]=a[j];
j=j-span;
}
a[j+span]=temp;
}
}
}
}

//////////////////////直接选择排序///////////////////////

void SelectSort(DataTypeSort a[],int n)
{
int i,j,small;
DataTypeSort temp;
for(i=0;i<n-1;i++)
{
small=i;
for(j=i+1;j<n;j++)
if(a[j].key<a[small].key)small=j;
if(small!=i)
{

temp=a[i];
a[i]=a[small];
a[small]=temp;

}

}

}

////////////////////堆排序///////////////////////////////
////////////建立堆/////////////
void CreateHeap(DataTypeSort a[],int n,int h)
{
int i,j,sign;
DataTypeSort temp;

i=h;
j=i*2+1;
temp=a[i];
sign=0;

while(j<n&&sign!=1)
{
if(j<n-1&&a[j].key<a[j+1].key)j++;;
if (temp.key>a[j].key)
sign=1;
else
{
a[i]=a[j];
i=j;
j=2*i+1;
}

}
a[i]=temp;
}

void InitHeap(DataTypeSort a[],int n)

{
int i;
for(i=(n-1)/2;i>=0;i--)
CreateHeap(a,n,i);
}

void HeapSort(DataTypeSort a[],int n)

{
int i;
DataTypeSort temp;
InitHeap(a,n);

for(i=n-1;i>0;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
CreateHeap(a,i,0);
}

}

/////////////交换排序(冒泡法)/////////////////////////

void BubbleSort(DataTypeSort a[],int n)
{
int i,j,flag=1;
DataTypeSort temp;
for (i=1;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if (a[j].key>a[j+1].key)
{
flag=1;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

////////////////快速排序////////////////////////////
void QuickSort(DataTypeSort a[],int low,int high)
{
int i=low,j=high;
DataTypeSort temp=a[low];
while(i<j)
{
while(i<j&&temp.key<=a[j].key)j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j&&a[i].key<temp.key)i++;
if (i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
if(low<i)QuickSort(a,low,i-1);
if(j<high)QuickSort(a,j+1,high);

}


/////////////////归并排序////////////////////////

void Merge(DataTypeSort a[],int n,DataTypeSort swap[],int k)
{
int m=0,u1,l2,i,j,u2;
int l1=0;

while(l1+k<=n-1)
{
l2=l1+k;
u1=l2-1;
u2=(l2+k-1<=n-1)?l2+k-1:n-1;

for (i=l1,j=l2;i<=u1&&j<=u2;m++)
{
if(a[i].key<=a[j].key)
{
swap[m]=a[i];
i++;
}
else
{
swap[m]=a[j];
j++;
}
}
while (i<=u1)
{
swap[m]=a[i];
m++;
i++;

}
while(j<=u2)
{
swap[m]=a[j];
m++;
j++;
}
l1=u2+1;

}
for (i=l1;i<n;i++,m++)swap[m]=a[i];

}


void MergeSort(DataTypeSort a[],int n)
{
int i,k=1;
DataTypeSort *swap;

swap=(DataTypeSort *)malloc(sizeof(DataTypeSort)* n);

while(k<n)
{
Merge(a,n,swap,k);
for (i=0;i<n;i++)
a[i]=swap[i];
k=2*k;

}
free(swap);
}



/////////////////选择算法函数////////////////////////////

int  SelectSort(int n,DataTypeSort b[],int count)
{


switch(n)
{
////////////////////直接插入排序算法//////////////////////
case 1:

printf("选择了<<直接插入排序>>算法:\n");
InsertSort(b,count); 

break;


////////////////////////希尔排序/////////////////////////
case 2:
printf("选择了<<希尔排序>>算法:\n");
ShellSort(b,count);
break;
//////////////////////直接选择排序///////////////////////

case 3:
printf("选择了<<直接选择排序>>算法:\n");
SelectSort(b,count);
break;
////////////////////堆排序///////////////////////////////
case 4:
printf("选择了<<堆排序>>算法:\n");
HeapSort(b,count);
break;
/////////////交换排序(冒泡法)/////////////////////////
case 5:
 printf("选择了<<交换排序(冒泡法)>>算法:\n");
 BubbleSort(b,count);
break;
////////////////快速排序////////////////////////////
case 6:
printf("选择了<<快速排序>>算法:\n");
QuickSort(b,0,count-1);
break;
/////////////////归并排序////////////////////////
case 7:
printf("选择了<<归并排序>>算法:\n");
MergeSort(b,count);
break;
///////////////基数排序///////////////////////
default:
printf("                  超出选择范围!\n\n\n");
return 0;
	break;
}
return 1;
}






void PrintselectSort()
{
printf("\n");
printf("请选排序的算法:	\n1.直接插入排序\n2.希尔排序\n3.直接选择排序\n4.堆排序\n5.交换排序(冒泡法)\n");
printf("6.快速排序\n7.归并排序\n");
printf("(输入以上排序的算法的序号)选择:  ");
}

void RNum(int *nummin,int *nummax)
{
int min,max;
for (int j=0;j==0;)
{
printf("请输入取数范围最少值:    ");
scanf("%d",&min);
printf("请输入取数范围最大值:    ");
scanf("%d",&max);
if(min>max)
{
printf("输入错误!\n");
continue;

}
j++;
}
*nummin=min;
*nummax=max+1;
}



void CRNum(int *count)
{
int c;
printf("请输入要排的数的个数:   ");
scanf("%d",&c);
*count=c;
}