数据结构 c 排序大全(快速,分治,外部,bit,桶,堆,二叉树,希尔等)

  大半天的劳动成果,涵盖了大部分的排序程序,

 

1.快速排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20

void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
       
int partition(int A[], int start, int end)
{
   int x = A[end];
   int i = start-1;
   int j = start;
   for( ; j<end; j++)
    {
      if(A[j]<x)
       {
        i++;
        swap(A+i, A+j);
       }
    }
    swap(A+i+1, A+end);
    return i+1;
}

void quicksort(int A[],int start, int end)
{
 if(start<end)
   {
     int q = partition( A, start, end);
     quicksort( A, start, q-1);
     quicksort( A, q+1, end);
   }
}
  
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%30 + 1;
  
  printf("the original array is:\n");
  print_array(A);
    
  quicksort(A, 0, MAX_NUM-1);
  printf("after quick sort the array is:\n");
  print_array(A);
    
  system("PAUSE");    
  return 0;
}


2.分治合并排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20
#define MAX_VALUES 9999

void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}
 
void merge(int A[],int start,int mid, int end)
{
  int i;
  int j;
  int k;
  
  int L[mid - start + 2];
  int R[end - mid + 1];
  for(i=0;i<=mid-start;i++)
    L[i] = A[i+start];
  L[i] = MAX_VALUES;
  
  for(i=0;i<=end-mid-1;i++)
    R[i] = A[i+mid+1];
  R[i] = MAX_VALUES;
  
  i = 0;
  j = 0;
  for(k=start;k<=end;k++)
   {
     if(L[i]<=R[j])
      {
       A[k] = L[i];
       i++;
      }
     else
      {
       A[k] = R[j];
       j++;
      }
   }
}

void mergesort(int A[],int start, int end)
{
 if(start<end)
  {
   int mid = (start + end)/2;
   mergesort( A, start, mid);
   mergesort( A, mid+1, end);
   merge(A, start, mid, end);
  }
}
  
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%30 + 1;
  
  printf("the original array is:\n");
  print_array(A);
    
  mergesort(A, 0, MAX_NUM-1);
  printf("after merge sort the array is:\n");
  print_array(A);
    
  system("PAUSE");    
  return 0;
}


3.外部排序

#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 20

void print_array(FILE* fp)
{
  int num;
  int i ;
  
  for(i=0;i<MAX_NUM;i++)
   {
    fscanf( fp, "%d\n", &num);
    
    if((i+1)%5 == 0)
      printf("%d\n", num);
    else
      printf("%d\t", num);
   }
}

void externalsort(FILE* fp, int M)
{
  int i = 0;
  int flag = 0;
  int A[2];
  
  FILE* fp_tmp1 = fopen("tmp1.txt","wb+");
  FILE* fp_tmp2 = fopen("tmp2.txt","wb+");
  
  for(i=1;i<=M;i++)
   {
     if(fscanf( fp, "%d\n", &A[0])!=EOF)
      {
       fprintf( fp_tmp1,"%d\n", A[0]);
      }
    }
     
  for(i=M+1;i<=MAX_NUM;i++)
   {
     if(fscanf( fp, "%d\n", &A[0])!=EOF)
      {
       fprintf( fp_tmp2,"%d\n", A[0]);
      }
    }
   rewind(fp_tmp1);
   rewind(fp_tmp2);
  
   fscanf( fp_tmp1, "%d\n", &A[0]);
   fscanf( fp_tmp2, "%d\n", &A[1]);
   rewind(fp);
   for(i=1;i<MAX_NUM+1;i++)
    {
      if(A[0]<=A[1])
       {
        fprintf(fp, "%d\n", A[0]);
        if(fscanf( fp_tmp1, "%d\n", &A[0]) == EOF)
          {
            flag = 1;
            break;
          }
       }
      else
       {
        fprintf(fp, "%d\n", A[1]);
        if(fscanf( fp_tmp2, "%d\n", &A[1]) == EOF)
          {
            flag = 2;
            break;
          }
       }
    }
   while(i++<MAX_NUM+1)
    {
       if(flag == 1)
        {
          fprintf(fp, "%d\n", A[1]);
          while(fscanf( fp_tmp2, "%d\n", &A[1]) != EOF)
            fprintf(fp, "%d\n", A[1]);
        }
       else
        {
          fprintf(fp, "%d\n", A[0]);
          while(fscanf( fp_tmp1, "%d\n", &A[0]) != EOF)
            fprintf(fp, "%d\n", A[0]);
        }
    }
   remove("tmp1.txt");
   remove("tmp2.txt");
}


int main(int argc, char *argv[])
{
  int i;
  int num;
  FILE* fp = NULL;
  
  srand((unsigned int)time(NULL));
  
  fp = fopen("original.txt","wb+");
  for(i=1;i<=10;i++)
   {
    num = 2*i-1;
    fprintf( fp, "%d\n", num);
   }
  for(i=1;i<=10;i++)
   {
    num = 2*i;
    fprintf( fp, "%d\n", num);
   }
   
  rewind(fp);
  printf("the original array is:\n");
  print_array(fp);
  
  rewind(fp);
  externalsort(fp, MAX_NUM/2);
  
  printf("after external sort the array is:\n");
  rewind(fp);
  print_array(fp);
    
  system("PAUSE");    
  return 0;
}


4.bit排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20
#define WIDTH 3
#define MASK 0x07
#define BIT_NUM 3
 
void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}
     
int get_rand(int NUM[], int start, int end)
{
  int num;
  num = rand()%(end-start+1)+start;
  swap(NUM+start, NUM+num);
  return NUM[start];
}

void bit_set(int BIT[],int num)
{
   BIT[num>>WIDTH] |= (1<<(num&MASK));
}

int bit_test(int BIT[],int num)
{
   int tmp = BIT[num>>WIDTH];
   
   if((tmp&= (1<<(num&MASK)))!=0)
     return 1;
   else
     return 0;
}
 
void bitsort(int A[], int N)
{
  int i = 0;
  int j =0;
  int BIT[BIT_NUM];
  printf("BIT_NUM is %d\n",BIT_NUM);
  for(i=0;i<N;i++)
     bit_set(BIT, A[i]);
 
  for(i=1;i<=MAX_NUM;i++)
   {
      if(bit_test(BIT, i))
       {
        A[j] = i;
        j++;
       }
   }
}
  
int main(int argc, char *argv[])
{
  int i;
  int NUM[MAX_NUM];
  int A[MAX_NUM];
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    NUM[i] = i + 1;
    
  for(i=0;i<MAX_NUM;i++)
    A[i] = get_rand(NUM, i,MAX_NUM-1);
  
  
  printf("the original array is: \n");
  print_array(A);
  
  bitsort(A, MAX_NUM);
  printf("after bit sort the array is:\n");
  print_array(A);
    
  system("PAUSE");    
  return 0;
}


5.桶排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20
#define MAX_VAULE 40

void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void bucketsort(int A[], int value)
{
   int B[value];
   int i;
   int j;
   int count = 0;
  
   for(i=0;i<value;i++)
     B[i] = 0;
   
   for(i=0;i<MAX_NUM;i++)
     B[A[i]]++;
    
   for(i=1; i<value; i++)
   {
    while(B[i]--)
     {
       A[count] = i;
       count++;
     }
   }
      
}
  
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%MAX_VAULE + 1;
  
  printf("the original array is:\n");
  print_array(A);
    
  bucketsort(A, MAX_VAULE+1);
  printf("after bucket sort the array is:\n");
  print_array(A);
    
  system("PAUSE");    
  return 0;
}


 

6.堆排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20

typedef struct heap
{
  int size;
  int* num;
}HEAP;

void print_array(HEAP* H)
{
  int i = 1;
  for(i=1;i<=MAX_NUM;i++)
  {
   if(i%5 == 0)
     printf("%d\n",H->num[i]);
   else
     printf("%d\t",H->num[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int get_rand(int NUM[], int start, int end)
{
  int num;
  num = rand()%(end-start+1)+start;
  swap(NUM+start, NUM+num);
  return NUM[start];
}

void init_heap(HEAP** H)
{
  *H = (HEAP*)malloc(sizeof(HEAP));
  (*H)->size = 0;
  (*H)->num = (int*)malloc(sizeof(int)*(MAX_NUM+1));
  (*H)->num[0] = 0;
}

void insert_heap(HEAP* H, int num)
{
   int i;
   for(i=++(H->size); H->num[i/2]>num; i/=2)
     H->num[i] = H->num[i/2];
   H->num[i] = num;
}

int delete_min(HEAP* H)
{
  int i;
  int min = H->num[1];
  int size = H->size;
  int last_num = H->num[(H->size)--];
  int child;
  
  for( i=1; i*2<=H->size; i=child)
   {
     child = 2*i;
     if(H->num[child]>H->num[child+1])
      child++;
     
     if(last_num > H->num[child])
       H->num[i] = H->num[child];
     else
       break;
   }
   
   H->num[i] = last_num;
   H->num[size] = min;
   return min;
}

void heapsort(HEAP* H,int N)
{
  int i;
  for(i=1;i<N+1;i++)
    insert_heap(H, H->num[i]);
  
  for(i=1;i<N+1;i++)
    delete_min(H);
          
}

int main(int argc, char *argv[])
{
  int i;
  int NUM[MAX_NUM];
  
  HEAP* H = NULL;
  init_heap(&H);
  
  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
    NUM[i] = i + 1;
    
  for(i=0;i<MAX_NUM;i++)
   {
    H->num[i+1] = get_rand(NUM, i,MAX_NUM-1);
   }
  
  printf("the original array is: \n");
  print_array(H);
  
  heapsort(H, MAX_NUM);

  printf("after heap sort the array is:\n");
  print_array(H);
    
  system("PAUSE");    
  return 0;
}


 

7.二叉树排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20

typedef struct tree
{
  int num;
  struct tree* lchild;
  struct tree* rchild;
}TREE;

int count = 0;
void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void add_tree(TREE** T, int num)
{
  if(*T == NULL)
   {
     *T = (TREE*)malloc(sizeof(TREE));
     (*T)->num = num;
     (*T)->lchild = NULL;
     (*T)->rchild = NULL;
     }
   else if((*T)->num > num)
     add_tree(&((*T)->lchild), num);
   else
     add_tree(&((*T)->rchild), num);
}

void midwalk(TREE* T,int A[])
{
  if(T!=NULL)
   {
     midwalk(T->lchild,A);
     A[count++] = T->num;
     midwalk(T->rchild,A);
   }
}

void treesort(int A[], int N)
{
  int i;
  TREE* T = NULL;
  
  for(i=0;i<N;i++)
    add_tree(&T, A[i]);
  
  midwalk( T, A);
}
   
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  srand((unsigned int)time(NULL));
  
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%100+1;
  
  printf("the original array is:\n");
  print_array(A);
    
  treesort(A, MAX_NUM);
  
  printf("after tree sort the array is:\n");
  print_array(A);
  
  system("PAUSE");    
  return 0;
}


8.希尔排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20


void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void shellsort(int A[], int N)
{
  int i;
  int increment = N/2;
  for(; increment>0; increment/=2)
    for(i=0;i<N-increment;i++)
     {
       if(A[i]>A[i+increment])
         swap(A+i,A+i+increment);
     }
}
   
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  srand((unsigned int)time(NULL));
  
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%100+1;
  
  printf("the original array is:\n");
  print_array(A);
    
  shellsort(A,MAX_NUM);
  
  printf("after tree sort the array is:\n");
  print_array(A);
  
  system("PAUSE");    
  return 0;
}


 

9.插入排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20


void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void insertsort(int A[], int N)
{
  int i;
  int j;
  int tmp;
  
  for(i=1; i<N; i++)
   {
    int tmp = A[i];
    for(j=i; j>0&&A[j-1]>tmp; j--)
     A[j] = A[j-1];
    
    A[j] = tmp;
   }
}
   
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  srand((unsigned int)time(NULL));
  
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%100+1;
  
  printf("the original array is:\n");
  print_array(A);
    
  insertsort( A, MAX_NUM);
  
  printf("after insert sort the array is:\n");
  print_array(A);
  
  system("PAUSE");    
  return 0;
}


 

10.冒泡排序

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 20


void print_array(int A[])
{
  int i = 0;
  for(i=0;i<MAX_NUM;i++)
  {
   if((i+1)%5 == 0)
     printf("%d\n",A[i]);
   else
     printf("%d\t",A[i]);
  }
}

void swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void bubblesort(int A[], int N)
{
  int i;
  int j;
  for(i=0; i<N-1; i++)
    for(j=0;j<N-i-1;j++)
     {
       if(A[j]>A[j+1])
         swap(A+j,A+j+1);
     }
}
   
int main(int argc, char *argv[])
{
  int i;
  int A[MAX_NUM];
  srand((unsigned int)time(NULL));
  
  for(i=0;i<MAX_NUM;i++)
    A[i] = rand()%100+1;
  
  printf("the original array is:\n");
  print_array(A);
    
  bubblesort(A,MAX_NUM);
  
  printf("after tree sort the array is:\n");
  print_array(A);
  
  system("PAUSE");    
  return 0;
}


 

写的累死俺了,终于又完成一件大工程,一直有想写个排序全集的,今天终于....