//Sort.h
#include <stdlib.h>
#include<stdio.h>
#include<time.h>
#define MAXSIZE 2000
typedef struct list{
int data[MAXSIZE];
int length;
};

void Print_List(list a)
{
printf("输出顺序表中%d个排序码:\n",a.length);
for(int i=0;i<a.length;i++)
{
printf("%-5d",a.data[i]);
if((i+1)%10==0)
{
printf("\n");
}
}
printf("\n");
}

//测试主函数
#include"Sort.h"
//#include"Quick_Sort.cpp"

int main()
{
int n;
list a;
srand(time(NULL));
printf("输入待排序的个数:");
scanf("%d",&n);
a.length=n;
for(int i = 0 ;i<n;i++)
{
a.data[i]=rand()%100;
}
Print_List(a);
Quick_Sort(a,0,n);
Print_List(a);
return 0;
}

/*********************************************************/
/* 直接选择排序 */
/*********************************************************/
void Simple_Sort(list &a)
{
int i,j,max,k;
for(i=0;i<a.length;i++)
{
k=i;
max=a.data[i];
for(j=i+1;j<a.length;j++)
{
if(a.data[j]>max)
{
k=j;
max=a.data[j];
}
}
a.data[k]=a.data[i];
a.data[i]=max;
}
}

/**************************************************/
/* 直接插入排序 */
/**************************************************/
void Insert_Sort(list &a)
{
int i,j;
for(i=1;i<a.length;i++) //将第i个数插入到前面中去。
{
int temp=a.data[i];
j=i-1;
while(j>=0&&temp<a.data[j])
{
a.data[j+1]=a.data[j];
j--;
}
a.data[j+1]=temp;
}
}

/********************************************************/
/* 冒泡排序 */
/********************************************************/
void Bubble_Sort(list &a)
{
int i , j;
for(i=0;i<a.length;i++)
{
for(j=0;j<a.length-i-1;j++)
{
if(a.data[j+1]>a.data[j])
{
int temp;
temp=a.data[j];
a.data[j]=a.data[j+1];
a.data[j+1]=temp;
}
}
}
}

/*****************************************************/
/* shell 排序 */
/*****************************************************/
void Shell_Sort(list &a)
{
int i,j;
int d=a.length/2; //分组
while(d>=1)
{
for(i=d;i<a.length;i++) //从第i个元素开始，将所有元素有序插入到相应分组
{
int temp=a.data[i];//保存第i个元素
j=i-d; //向前找插入位置
while(j>=0&&a.data[j]<temp)
{
a.data[j+d]=a.data[j]; //组内移动
j-=d;
}
a.data[j+d]=temp;
}
d/=2; //减小分组数
}
}

/********************************************************/
/* 快速排序 */
/********************************************************/
void Quick_Sort(list &a,int left,int right)
{
int i ,j;
if(left<right)
{
i=left;j=right;
int temp=a.data[i];
while(i!=j)
{
while(i<j&&temp>a.data[j])
{
j--;
}
if(i<j)
{
a.data[i]=a.data[j];
i++;
}
while(i<j&&temp<a.data[i])
{
i++;
}
if(i<j)
{
a.data[j]=a.data[i];
j--;
}
}
a.data[i]=temp;
Quick_Sort(a,left,i-1);
Quick_Sort(a,i+1,right);
}
}

/**************************************************/
/* 二分法插入排序 */
/**************************************************/
void Binsert_Sort(list &a)
{
int i,j;
for(i=1;i<a.length;i++)
{
int temp=a.data[i];
int left=0,right=i-1;
while(left<=right)
{
int mid=(left+right)/2;
if(a.data[mid]>a.data[i])
{
left=mid+1;
}
else
{
right=mid-1;
}
}
for(j=i-1;j>=left;j--)
{
a.data[j+1]=a.data[j];
}
a.data[align=left]=temp;
}
}

//DistributionCounting 分布计数
main()
{
    int a[7]={13,11,12,13,12,12,18};
    int d[8],s[7];
    int i,j;
    for(j=0;j<=7;j++)
        d[j]=0;
    for(i=0;i<7;i++)
        d[a[i]-11]++;
    for(j=1;j<=7;j++)
        d[j]=d[j-1]+d[j];
    for(i=6;i>=0;i--)
    {
        j=a[i]-11;
        s[d[j]-1]=a[i];
        d[j]=d[j]-1;
    }
    for(i=0;i<7;i++)
        printf("%d ",s[i]);
}