六种排序算法

我的代码很烂，刚做的作业

 

#include
#include
#include
#include
#include
#include
#define MAX1 10
#define MAX2 1000
#define MAX3 10000
#define MAX4 100000
#define MAX_DOUBLE 10000000000000000.000000
#define INIT_SIZE MAX4

//A subprogram of quickSort
int partition(double a[],int p,int r)
{
 double x=a[r];
 int i=p-1;
 int j;
 double tmp;
 for(j=p;j<=r-1;j++)
 {
  if(a[j]<=x)
  {
   i=i+1;
   tmp=a[i];
   a[i]=a[j];
   a[j]=tmp;
  }
 }
 tmp=a[i+1];
 a[i+1]=a[r];
 a[r]=tmp;
 return i+1;
}

//quickSort                              //right
void quickSort(double a[],int p,int r)
{
 int q;
 if(p {
  q=partition(a,p,r);
  quickSort(a,p,q-1);
  quickSort(a,q+1,r);
 }
}

//insertSort                            //right
void insertSort(double a[],int n)
{
 int j;
 double key;
 int i;
 for(j=1;j {
  key=a[j];
  i=j-1;
  while(i>0&&a[i]>key)
  {
   a[i+1]=a[i];
   i--;
  }
  a[i+1]=key;
 }
}

//mergeSort subprogram
void Merge(double a[],int p,int q,int r)
{
 int n1=q-p+1;
 int n2=r-q;
 int i;
 int j;
 int k;
 double *L=(double *)malloc(n1*sizeof(double));        //int *a=(int*)malloc(N*sizeof(int));
 double *R=(double *)malloc(n2*sizeof(double));
 for(i=0;i  L[i]=a[p+i];
 for(j=0;j  R[j]=a[q+j+1];
 L[n1]=MAX_DOUBLE;
 R[n2]=MAX_DOUBLE;
 i=0;
 j=0;
 for(k=p;k<=r;k++)
 {
  if(L[i]<=R[j])
  {
   a[k]=L[i];
   i++;
  }
  else
  {
   a[k]=R[j];
   j++;
  }
 }
}

//mergeSort                             //right
void mergeSort(double a[],int p,int r)
{
 int q;
 if(p {
  q=(p+r)/2;
  mergeSort(a,p,q);
  mergeSort(a,q+1,r);
  Merge(a,p,q,r);
 }
}

//bubbleSort                             //right
void bubbleSort(double a[],int n)
{
 int i;
 int j;
 double tmp;
 for(i=0;i {
  for(j=n-1;j>=i;j--)
  {
   if(a[j]   {
    tmp=a[j-1];
    a[j-1]=a[j];
    a[j]=tmp;
   }
  }
 }
}

typedef struct Node
{
 double data;
 struct Node* next;
 struct Node* pre;
}SLNode;

void ListInitiate(SLNode **head)
{
 if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)
  exit(1);
 (*head)->next=NULL;
 (*head)->pre=head;
}

void ListInsert(SLNode *head,double x)
{
 SLNode *p;
 p=head;
 while(p->next!=NULL)
 {
  p=p->next;
 }
 p->next=(SLNode *)malloc(sizeof(SLNode));
 p->next->data=x;
 p->next->next=NULL;
 p->next->pre=p;
}

void insertsort(SLNode *head)
{
 SLNode *p=head->next,*pre,*q;
 head->next=NULL;
 while(p!=NULL)
 {
  if(head->next==NULL)
  {
   head->next=p;
   p=p->next;
   head->next->next=NULL;
  }
  else
  {
   pre=head;
   q=head->next;
   while(q!=NULL&&q->datadata)
   {
    pre=q;
    q=q->next;
   }
   q=p->next;
   p->next=pre->next;
   pre->next=p;
   p=q;
  }
 }
}

//bucketSort
void bucketSort(double a[],int n)
{
 int i;
 SLNode *p;
 SLNode *head0,*head1,*head2,*head3,*head4,*head5,*head6,*head7,*head8,*head9;
 ListInitiate(&head0);
 ListInitiate(&head1);
 ListInitiate(&head2);
 ListInitiate(&head3);
 ListInitiate(&head4);
 ListInitiate(&head5);
 ListInitiate(&head6);
 ListInitiate(&head7);
 ListInitiate(&head8);
 ListInitiate(&head9);
 for(i=0;i {
  if(a[i]<0.100000)
  {
   ListInsert(head0,a[i]);
  }
  else if(a[i]>=0.100000&&a[i]<0.200000)
  {
   ListInsert(head1,a[i]);
  }
  else if(a[i]>=0.200000&&a[i]<0.300000)
  {
   ListInsert(head2,a[i]);
  }
  else if(a[i]>=0.300000&&a[i]<0.400000)
  {
   ListInsert(head3,a[i]);
  }
  else if(a[i]>=0.400000&&a[i]<0.500000)
  {
   ListInsert(head4,a[i]);
  }
  else if(a[i]>=0.500000&&a[i]<0.600000)
  {
   ListInsert(head5,a[i]);
  }
  else if(a[i]>=0.600000&&a[i]<0.700000)
  {
   ListInsert(head6,a[i]);
  }
  else if(a[i]>=0.700000&&a[i]<0.800000)
  {
   ListInsert(head7,a[i]);
  }
  else if(a[i]>=0.800000&&a[i]<0.900000)
  {
   ListInsert(head8,a[i]);
  }
  else if(a[i]>=0.900000)
  {
   ListInsert(head9,a[i]);
  }
 }
 insertsort(head0);
 insertsort(head1);
 insertsort(head2);
 insertsort(head3);
 insertsort(head4);
 insertsort(head5);
 insertsort(head6);
 insertsort(head7);
 insertsort(head8);
 insertsort(head9);
// for(i=0;i// {
//  a[i]=1.000000;
// }
 if(head0->next!=NULL)
 {
  p=head0->next;
  i=0;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head1->next!=NULL)
 {
  p=head1->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head2->next!=NULL) 
 {
  p=head2->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head3->next!=NULL)
 {
  p=head3->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head4->next!=NULL)
 {
  p=head4->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head5->next!=NULL)
 {
  p=head5->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head6->next!=NULL)
 {
  p=head6->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++; 
 }
 if(head7->next!=NULL)
 {
  p=head7->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head8->next!=NULL)
 {
  p=head8->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
 if(head9->next!=NULL)
 {
  p=head9->next;
  while(p->next!=NULL)
  {
   a[i]=p->data;
   p=p->next;
   i++;
  }
  a[i]=p->data;
  i++;
 }
}

//shellSort                                 //right
void shellSort(double a[],int n)
{
 int i;
 int j;
 int k=4;
 double tmp;
 while(k>=1)
 {
  for(i=k+1;i  {
   tmp=a[i];
   j=i;
   while(j>k&&a[j-k]>tmp)
   {
    a[j]=a[j-k];
    j=j-k;
   }
   a[j]=tmp;
  }
  k/=2;
 }
}

void main()
{
 double a[MAX2];
 int i;
 int j;
 double time1,time2;
// for(j=0;j<5;j++)
// {
 for(i=0;i {
  a[i]=rand()/32767.000000;
 }

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();
 quickSort(a,0,MAX2-1);   //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("quickSort's running time is %f ms\n",time2-time1);
 printf("\n");
 
 for(i=0;i {
  a[i]=rand()/32767.000000;
 }
// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();
 insertSort(a,MAX2);   //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("insertSort's running time is %f ms\n",time2-time1);
 printf("\n");

 for(i=0;i {
  a[i]=rand()/32767.000000;
 }
// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();
 mergeSort(a,0,MAX2-1);   //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("mergeSort's running time is %f ms\n",time2-time1);
 printf("\n");
 

 for(i=0;i {
  a[i]=rand()/32767.000000;
 }
// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();
 bubbleSort(a,MAX2);      //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("bubbleSort's running time is %f ms\n",time2-time1);
 printf("\n");

 for(i=0;i {
  a[i]=rand()/32767.000000;
 }
// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();          
 bucketSort(a,MAX2);        //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("bucketSort's running time is %f ms\n",time2-time1);
 printf("\n");
 

 for(i=0;i {
  a[i]=rand()/32767.000000;
 }
// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("\n");

 time1=clock();
 shellSort(a,MAX2);       //right
 time2=clock();

// for(i=0;i// {
//  printf("%f\t",a[i]);
// }
 printf("shellSort's running time is %f ms\n",time2-time1);
}