#include <cstdio>
#define MAXSIZE 20
using namespace std;
typedef struct
{ int r[MAXSIZE+1];
int length;
}List;
/* 初始化 */
void Initial(List &L,int num[],int n)
{ for(int i=0;i<n;i++)
L.r[i]=num[i];
L.length=n-1;
}
/* 输出结果 */
void Print(List L)
{ for(int i=1;i<=L.length;i++)
printf("%d ",L.r[i]);
printf("/n");
}
/* 直接插入排序 */
void InsertSort(List &L)
{
int i;
int j;
for(i=2;i<=L.length;i++)
{
if(L.r[i]<L.r[i-1])
{
L.r[0]=L.r[i]; //设置哨兵，防止下标越界
for(j=i-1; (L.r[j]>L.r[0]); j--) //寻找插入位置
{
L.r[j+1]=L.r[j]; //记录后移
}
L.r[j+1]=L.r[0];
}
}
}/* 直接插入排序 */
/* 希尔排序 */
void ShellInsert(List &L,int dk)
{
for(int i=dk+1;i<=L.length;i++)
{
int j;
if(L.r[i]<L.r[i-dk])
{ L.r[0]=L.r[i];
for( j=i-dk;(j>0) && (L.r[0]<L.r[j]);j-=dk)
{
L.r[j+dk]=L.r[j];
}
L.r[j+dk]=L.r[0];
}
}
}
void ShellSort(List &L,int dlta[],int t)
{ for(int k=0;k<t;k++)
ShellInsert(L,dlta[k]);
}/* 希尔排序 */
/* 冒泡排序 */
void BubbleSort(List &L)
{ int t;
bool change=true;
for(int i=L.length;change && i>1;i--)
{ change=false;
for(int j=1;j<i;j++)
if(L.r[j]>L.r[j+1])
{t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;change=true;}
}
}/* 冒泡排序 */
/* 快速排序 */
int Partition(List &L,int low,int high)
{ L.r[0]=L.r[low];
while(low<high)
{ while(low<high && L.r[high]>=L.r[0]) high--;
L.r[low]=L.r[high];
while(low<high && L.r[low]<=L.r[0]) low++;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QuickSort(List &L,int low,int high)
{ if(low<high)
{ int piv;
piv=Partition(L,low,high);
QuickSort(L,low,piv-1);
QuickSort(L,piv+1,high);
}
}/* 快速排序 */
/* 选择排序 */
void SelectSort(List &L)
{ int t;
for(int i=1;i<L.length;i++)
{ int k=i;
for(int j=i+1;j<=L.length;j++)
if(L.r[k]>L.r[j]) k=j;
if(k!=i){t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;}
}
}/* 选择排序 */
/* 堆排序 */
void HeapAdjust(List &L,int s,int m)
{ int rc=L.r[s];
for(int i=2*s;i<=m;i=2*s)
{ if(i+1<=m && L.r[i]<L.r[i+1]) i++;
if(rc>=L.r[i]) break;
L.r[s]=L.r[i];
s=i;
}
L.r[s]=rc;
}
void HeapSort(List &L)
{ int i,t;
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--)
{ t=L.r[1];L.r[1]=L.r[i];L.r[i]=t;
HeapAdjust(L,1,i-1);
}
}/* 堆排序 */
/* 归并排序 */
void Merge(List L,List &T,int l,int m,int h)
{ int i=l,j=m+1,k=l;
while(i<=m && j<=h)
if(L.r[i]<=L.r[j]) T.r[k++]=L.r[i++];
else T.r[k++]=L.r[j++];
while(i<=m) T.r[k++]=L.r[i++]; //原来if改为while
while(j<=h) T.r[k++]=L.r[j++]; //原来if改为while
}
void MergeSort(List L,List &T,int s,int t)
{ if(s==t) T.r[s]=L.r[s];
else
{ int m=(s+t)/2;
List S;
MergeSort(L,S,s,m);
MergeSort(L,S,m+1,t);
Merge(S,T,s,m,t);
}
}/* 归并排序 */
/* 主函数 */
void main()
{
List L;
int num[9]={0,49,38,65,97,76,13,27,49};
int dlta[3]={5,3,1};
Initial(L,num,9);
printf("原来的数据为:");
Print(L);
Initial(L,num,9);
printf("直接插入排序:");
InsertSort(L);
Print(L);
Initial(L,num,9);
printf("希尔排序 :");
ShellSort(L,dlta,3);
Print(L);
Initial(L,num,9);
printf("冒泡排序 :");
BubbleSort(L);
Print(L);
Initial(L,num,9);
printf("快速排序 :");
QuickSort(L,1,L.length);
Print(L);
Initial(L,num,9);
printf("选择排序 :");
SelectSort(L);
Print(L);
Initial(L,num,9);
printf("堆排序 :");
HeapSort(L);
Print(L);
Initial(L,num,9);
printf("归并排序 :");
MergeSort(L,L,1,L.length);
Print(L);
}