algorithm.c

关于计算机几种常见排序算法

/*关于计算机几种常见排序算法，在学习数据结构的时候曾自己动手写C语言的程序，

现发布出来与大家交流。虽然简单，但希望与大家在编程以及计算机算法方面能

够与大家交流，达到抛砖引玉的效果，恳切大家提出意见、建议。*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<alloc.h>
#define MAXSIZE 20
typedef int type;
void output(const int *sortlist);
void insertsort(const int*);
void binary_insertsort(const int*);
void binary_sort(const int*);
void two_insertsort(const int*);
void shell_insertsort(const int*);
void bubblesort(const int*);
void bubbleshort(const int*);
void quick_sort(const int*);
void quicksort(const int*);
void heapsort(const int*);
void mergesort(const int*);
void radixsort(const int*);
void simplesort(const int*);
int main()
 {
  int serial[MAXSIZE]={0},sortlist[MAXSIZE];
  int i;
  randomize();
  for(i=1;i<MAXSIZE;i++)
   {
    serial[i]=random(1000);
    printf("%4d",serial[i]);
  }printf("\n");
  /*insertlist*/
  printf("The insert sort list:\n");
  insertsort(serial);
  /*binary insertion sort*/
  printf("The binary insertion sort:\n");
  binary_insertsort(serial);
  /*bianry insertion sort*/
  printf("The binary insertion sort(inprove):\n");
  binary_sort(serial);
     /*2-insert sort:*/
  printf("The 2 direction insert sort:\n");
  two_insertsort(serial);
     /*shell's insert sort*/
     printf("The shell's insert sort:\n");
  shell_insertsort(serial);
     /*bubble sort*/
     printf("The bubble sort:\n");
  bubblesort(serial);
  /*bubble sort(improve)*/
  printf("The bubble sort(simple sort):\n");
  simplesort(serial);
  /*quick sort*/
  printf("The quick sort:\n");
  quick_sort(serial);
     /*quick sort with a pivot*/
  printf("The quick sort (improve):\n");
  quicksort(serial);
     /*heap sort*/
  printf("The heap sort:\n");
  heapsort(serial);
  /*merge sort*/
  printf("The merge sort:\n");
  mergesort(serial);
  /*radix sort*/
  printf("The radix sort:\n");
  radixsort(serial);
     /*simple sort*/

  printf("Press any key to exit...");
  getch();
  return 0;
}
void output(const int *array)
 {
  int i;
  for(i=1;i<MAXSIZE;i++)
   printf("%4d",*(array+i));
  printf("\n");
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void insertsort(const int *sortlist)
 {
  int i,j;
  int list[MAXSIZE];
  for(i=0;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=1;i<MAXSIZE;i++)
   {
    *list=list[i];
    for(j=i;j>0&&list[0]<list[j-1];j--)
     list[j]=list[j-1];
    list[j]=*list;
  }
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void binary_insertsort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE];
  for(i=0;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=2;i<MAXSIZE;i++)
   {
    int k,high,low;
    *list=list[i];
    low=1;
    high=i-1;
    while(low<=high)
     {
      if(*list<list[high])
       high--;
      if(*list>=list[low])
       low++;
    }
    for(k=i;k>low;k--)
     {
      list[k]=list[k-1];
    }
    list[low]=*list;                /*insert point:low*/
  }
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void binary_sort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=1;i<MAXSIZE;i++)
   {
    int k,high=i-1,low=1;
    *list=list[i];
    while(high>=low)
     {
      int k=(high+low)/2;         /*When low=high is necessary*/
      if(*list<=list[k])
       high=k-1;
      else
       low=k+1;
    }
    for(k=i;k>low;k--)
      list[k]=list[k-1];
    list[low]=*list;
  }
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void two_insertsort(const int *sortlist)
 {
  int i,first=MAXSIZE,final=1,central;
  int list[MAXSIZE+1]={0};                  /*increase a node*/
  central=list[MAXSIZE]=list[1]=sortlist[1];
  for(i=2;i<MAXSIZE;i++)
   {
    *list=sortlist[i];
    if(sortlist[i]<central)
     {
      int k=first;
      while(*list>list[k])
       {
     list[k-1]=list[k++];
      }
      list[k-1]=*list;
      first--;
   }
   else
     {
      int k=final;
      while(*list<list[k])
       {
        list[k+1]=list[k--];
      }
      list[k+1]=*list;
      final++;
    }
  }
  /*output(list);*/
  for(i=first;i<first+MAXSIZE;i++)
   {
    int k=i%MAXSIZE;
    if(k==0)continue;
    printf("%4d",list[k]);
  }
  printf("\n");
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void shell(int *list,int step)
 {
  int i;
  for(i=step+1;i<MAXSIZE;i++)
   {
    int k;
    if(list[i]<list[i-step])
     {
         *list=list[i];
               for(k=i-step;k>0&&*list<list[k];k-=step)
        list[k+step]=list[k];
         list[k+step]=*list;
    }
  }
}
void shell_insertsort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE],step[4]={1,3,5,7};
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=3;i>=0;i--)
   shell(list,step[i]);
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void bubblesort(const int *sortlist)
 {
  int i,j;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
     for(i=1;i<MAXSIZE-1;i++)
   for(j=i+1;j<MAXSIZE;j++)
    if(list[i]>list[j])
     {
         int temp;
         temp=list[i];
         list[i]=list[j];
         list[j]=temp;
    }
     output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@2*/
void simplesort(const int *sortlist)
 {
  int i,movflag=1;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  while(movflag)
   {
    movflag=0;
    for(i=1;i<MAXSIZE-1;i++)
     if(list[i]>list[i+1])
      {
       int temp=list[i];
           list[i]=list[i+1];
        list[i+1]=temp;
        movflag=1;
     }
  }
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void swap(int *elem1,int *elem2)
 {
  int temp=*elem1;
      *elem1=*elem2;
      *elem2=temp;
}
void quick(int *list,int lg,int rg)
 {
  int i=lg,j=rg;                   /*low(left) merge and high(right) merge*/
  while(i<j)
   {
    while(i<j&&list[i]<=list[j])
     i++;
    swap(&list[i],&list[j]);
    while(i<j&&list[j]>=list[i])
     j--;
    swap(&list[i],&list[j]);
  }
  if(rg>lg)
   {
    quick(list,lg,i-1);
    quick(list,i+1,rg);
  }
}
void quick_sort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  quick(list,1,MAXSIZE-1);
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@2*/
void quickpart(int *list,int lowmerge,int highmerge)
 {
  int pivot=list[lowmerge];
  int i=lowmerge,j=highmerge;
  while(i<j)
   {
    while(i<j&&list[j]>=pivot)
     j--;
    list[i]=list[j];
    while(i<j&&list[i]<=pivot)
     i++;
    list[j]=list[i];
  }
  list[i]=pivot;
  if(lowmerge<highmerge)
   {
    quickpart(list,lowmerge,i-1);
    quickpart(list,i+1,highmerge);
  }
}
void quicksort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  quickpart(list,1,MAXSIZE-1);
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void selectsort(const int* sortlist)
 {
  int i,j;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=1;i<MAXSIZE-1;i++)
   {
    int k=i,temp;
    for(j=i+1;j<MAXSIZE;j++)
     if(list[k]>list[j])
      k=j;
    temp=list[k];
    list[k]=list[i];
    list[i]=temp;
  }
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@2*/
void heappart(int *list,int point,int n)
 {
  int i=point,j=2*point;
  *list=list[point];
  while(j<n)
   {
    if(list[j]<list[j+1])
     j++;
    if(*list<list[j])
     {
            list[i]=list[j];
         i=j;j=2*i;
    }
    else
     break;
  }
  list[i]=*list;
}
void heapsort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE]={0};
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  for(i=(MAXSIZE-1)/2;i>0;i--)
   {
    heappart(list,i,MAXSIZE-1);
  }
  for(i=MAXSIZE-1;i>0;i--)
   {
    swap(&list[1],&list[i]);
    heappart(list,1,i-1);
  }
  if(list[1]>list[2])
   swap(&list[1],&list[2]);               /*list[1] and list[2] no chance to compare*/
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void mergepart(int *list,int low,int high)
 {
     if(low<high)
   {
    int i,j,k,stop;
    int temp[MAXSIZE]={0};
    mergepart(list,low,(low+high)/2);
    mergepart(list,(low+high)/2+1,high);
    i=low;j=(high+low)/2+1;k=0;
    while(i<=(high+low)/2&&j<=high)
     {
      if(list[i]>=list[j])
       temp[k++]=list[j++];
      else
       temp[k++]=list[i++];
    }
    stop=k;
    if(j<=high)
      for(i=low,k=0;i<stop+low;i++,k++)
       list[i]=temp[k];
    if(i<=(high+low)/2)
     {
      for(j=low+stop;j<=high;j++,i++)
       list[j]=list[i];
      for(j=low,k=0;j<stop+low;j++)
       list[j]=temp[k++];
    }
  }
}
void mergesort(const int *sortlist)
 {
  int i;
  int list[MAXSIZE];
  for(i=1;i<MAXSIZE;i++)
   list[i]=sortlist[i];
  mergepart(list,1,MAXSIZE-1);
  output(list);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
typedef struct linklist
 {
  type data;
  struct linklist *next;
}*link,linknode;
void radixpart(int list[],int digit)
 {
  int   i,k;
  link  sort[10]={0};
  link  previous,rear;
  link  node;
  for(i=1;i<MAXSIZE;i++)
   {
    int bit=list[i]/digit;
    bit=bit%10;                  /*get a digit of list number*/
    node=(link)malloc(sizeof(linknode));
    node->data=list[i];
    node->next=0;
    rear=previous=sort[bit];
    while(previous)
     {
      rear=previous;
      previous=previous->next;
    }
    if(!rear)
     sort[bit]=node;
    else
     rear->next=node;
  }
  for(i=0,k=1;i<10;i++)
    if(sort[i])
     {
      previous=sort[i];
      while(previous)
       {
        list[k++]=previous->data;
     previous=previous->next;
      }
    }
}
void radixsort(const int *sortlist)
 {
  int i,max;
  int *digit;
  int list[MAXSIZE];
  for(i=1,max=1;i<MAXSIZE;i++)
   {
    list[i]=sortlist[i];
    if(sortlist[i]>sortlist[max])
     max=i;
  }                                      /*The maximum number of the digit serial*/
  for(i=0,max=list[max];i<100;i++)
  {
   if(max==0)
    {
     max=i;
     break;
   }
   else
    max=max/10;
  }
  digit=(int*)malloc(max*sizeof(int));
  for(i=0;i<max;i++)
   {
    digit[i]=exp(i*log(10));
  }
  for(i=0;i<max;i++)
   radixpart(list,digit[i]);
  output(list);
  free(digit);
}