```c++
#include<iostream>
#define MAX 100
using namespace std;
void xier_sort(int d[],int n,int dd[],int t);
void kuaisu_sort(int d[],int min,int max);
void duitiaozheng(int d[ ],int s,int n);
void dui_sort(int d[ ],int n);
int main( )
{
int d[MAX],dd[MAX];
int s,q,t,n,k,m,ch;
/*the number of nodes*/
printf("How many nodes?\n");
scanf("%d",&n);
/*receive n,put it in array d*/
for(s=0;s<n;s++)
{
printf("Input No %d value\n",s+1);
scanf("%d",&d[s]);
}
printf("Please input your choice(1-6):");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("This is straight insertion sort!\n");
s=1;
while(s<n)
{
t=d[s]; /*t is a temporary variable*/
for(q=s-1;q>=0&&t<d[q];q--)
d[q+1]=d[q]; /*the node move right*/
d[q+1]=t; /*if the value of q is -1,it does not exist a number whose value is smaller than t,else,it must exist q+1 numbers whose value is smaller than t at least*/
s++;
}
break;
case 2:
printf("This is shell sort!\n");
/*initiate the array */
s=n;q=0;
while(s>1)
{
dd[q++]=s/2;
s=s/2;
}
/*the last increment is 1*/
xier_sort(d,n,dd,q);
break;
case 3:
printf("This is bubble sort!\n");
m=0;
while(m<n-1)/*if m is equal to n-1,end the cycle*/
{
q=n-1;
for(s=n-1;s>=m+1;s--)
if(d[s]<d[s-1])
{
t=d[s];
d[s]=d[s-1];
d[s-1]=t;
q=s;/*j note the current location where the exchanging happens this time*/
}
m=q;
}
break;
case 4:
printf("This is quick sort!\n");
kuaisu_sort(d,0,n-1);
break;
case 5:
printf("This is simple selection sort!\n");
for(s=0;s<n-1;s++)
{
k=s;
for(q=s+1;q<n;q++)
if(d[k]>d[q]) k=q;
t=d[s];
d[s]=d[k];
d[k]=t;/*exchange the location*/
}
break;
case 6:
printf("This is heap sort!\n");
dui_sort(d,n);
break;
default:
printf("1--------------straight insertion sort!\n");
printf("2--------------shell sort!\n");
printf("3--------------bubble sort!\n");
printf("4--------------simple selection sort!\n");
printf("5--------------quick sort!\n");
printf("6--------------heap sort!\n");
return 0;
}
/*output the nodes' sequence after sorting*/
for(s=0;s<n-1;s++)
printf("%d,",d[s]);
printf("%d",d[s]);
printf("\n");
}
/*shell sort*/
void xier_sort(int d[],int n,int dd[],int t)
{
int s,x,k,h;
int y;
for(s=0;s<t;s++)
{
h=dd[s];/*select increment*/
for(x=h;x<n;x++)/*j point out the location of the number inserted*/
{
y=d[x];
for(k=x-h;k>=0&&y<d[k];k-=h)
d[k+h]=d[k];/*move back*/
d[k+h]=y;
}
}
}
void kuaisu_sort(int d[],int min,int max)
{
int head,tail;
int t;
if(min<max)
{
head=min;
tail=max;
t=d[head];
while(head!=tail)
{
while(head<tail&&d[tail]>=t)
tail--;
if(head<tail)
d[head++]=d[tail];/*exchange the nodes*/
while(head<tail&&d[head]<=t)
head++;
if(head<tail)
d[tail--]=d[head];
}
d[head]=t;
kuaisu_sort(d,min,head-1);
kuaisu_sort(d,tail+1,max);
}
}
void duitiaozheng(d,s,n)
int d[];int s,n;
{
int q;
int t;
t=d[s];
while((q=2*s+1)<n)/*it has left child*/
{
if(q<n-1&&d[q]<d[q+1]) q++;
if(t<d[q])
{
d[(q-1)/2]=d[q];
s=q;
}
else
break;
}
d[(q-1)/2]=t;/*put it in the final location*/
}
void dui_sort(d,n)
int d[];int n;
{
int s;int t;
s=(n-1)/2;
while(s>=0)
{
duitiaozheng(d,s,n);
s--;
}
s=n-1;
while(s>0)
{
t=d[0];/*exchange the nodes*/
d[0]=d[s];
d[s]=t;
duitiaozheng(d,0,s);/*after exchangeing，readjust the heap*/
s--;
}
}
```
