#include<stdio.h>
#include"stdlib.h"
#define MAXSIZE 100 /线性表中最大元素个数/
typedef int KeyType; /关键字类型/
typedef struct
{ KeyType Key; /关键字域/
}LineList;
void bubble(LineList a[],int n) //冒泡排序
{
int i,j,temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i].Key>a[j].Key)
{
temp=a[i].Key;
a[i].Key=a[j].Key;
a[j].Key=temp;
}

}
void choise(LineList a[],int n)//选择排序
{
int i,j,k,temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(a[k].Key>a[j].Key) k=j;
if(i!=k)
{
temp=a[i].Key;
a[i].Key=a[k].Key;
a[k].Key=temp;
}
}
}
void quick(LineList a[],int i,int j)//快速排序
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[(i+j)/2].Key;
do
{
while(a[m].Key&&m<j) m++;
while(a[n].Key>k&&n>i) n–;
if(m<=n)
{
temp=a[m].Key;
a[m].Key=a[n].Key;
a[n].Key=temp;
m++;
n–;
}
}while(m<=n);
if(m<j) quick(a,m,j);
if(n>i) quick(a,i,n);
}
void insert(LineList a[],int n) //插入排序
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i].Key;
j=i-1;
while(j>=0&&temp<a[j].Key)
{
a[j+1].Key=a[j].Key;
j–;
}
a[j+1].Key=temp;
}
}
void shell(LineList a[],int n)//希尔排序
{
int i,j,k,x;
k=n/2;
while(k>=1)
{
for(i=k;i<n;i++)
{
x=a[i].Key;
j=i-k;
while(j>=0&&x<a[j].Key)
{
a[j+k].Key=a[j].Key;
j-=k;
}
a[j+k].Key=x;
}
k/=2;
}
}
void Merge(LineList a[],LineList b[],int left,int mid,int right)
{
int i,j,k;
i = left;
j = mid+1;
k = left;
while ( i <= mid && j <= right )
{
if ( a[i].Key <= a[j].Key )
{
b[k++].Key = a[i++].Key;
}
else
{
b[k++].Key = a[j++].Key;
}
}
while ( i <= mid )
{
b[k++].Key = a[i++].Key;
}
while ( j <= right )
{
b[k++].Key = a[j++].Key;
}
}
void MergeSort(int left,int right,LineList a[],LineList b[])
{
int i,mid;
if ( left < right )
{
mid = ( left + right ) / 2 ;
MergeSort(left , mid,a,b);
MergeSort(mid+1 , right,a,b);
Merge(a,b,left,mid,right);
for ( i = left ; i <= right ; i++)
{
a[i].Key = b[i].Key;
}
}
}
void Heapify(LineList s[],int x,int n)
{
if ( x2+1 <= n)
{
if ( s[x].Key == s[2x].Key && s[x].Key == s[2x+1].Key ) return ;
if ( s[2x].Key > s[x].Key && s[2x].Key > s[2x+1].Key )
{
s[2x].Key ^= s[x].Key ^= s[2x].Key ^= s[x].Key ;
Heapify(s,2x,n);
}
else if ( s[2x+1].Key > s[x].Key && s[2x+1].Key > s[2x].Key )
{
s[2x+1].Key^= s[x].Key ^= s[2x+1].Key ^= s[x].Key ;
Heapify(s,2x+1,n);
}
else if ( s[2x+1].Key == s[2x].Key && s[2x].Key > s[x].Key)
{
s[2x].Key ^= s[x].Key ^= s[2x].Key ^= s[x].Key;
Heapify(s,2x,n);
}
}
else if ( x2 == n )
{
if ( s[2x].Key > s[x].Key )
{
s[2x].Key ^= s[x].Key ^= s[2x].Key ^= s[x].Key ;
Heapify(s,2x,n);
}
}
}
void HeapSort(LineList s[],int n)
{
int i,k;
for ( i = n/2 ; i >= 1 ; i–)
{
Heapify(s,i,n);
}
for ( k = n ; k > 1 ; k–)
{
s[k].Key ^= s[1].Key ^= s[k].Key ^= s[1].Key;
Heapify(s,1,k-1);
}
}
void print(LineList a[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n");
}

void MenuSort()
{ /显示菜单子函数/
printf("\n 排序子系统");
printf("\n==================================================");
printf("\n| 1——更新排序数据 |");
printf("\n| 2——直接插入排序 |");
printf("\n| 3——希尔排序 |");
printf("\n| 4——冒泡排序 |");
printf("\n| 5——快速排序 |");
printf("\n| 6——直接选择排序 |");
printf("\n| 7——堆排序 |");
printf("\n| 8——归并排序 |");
printf("\n| 0——返回 |");
printf("\n==================================================");
printf("\n请输入菜单号（0-8）