基于C的排序算法

 1 void insert_sort(int table[])
 2 {
 3  　　int i,j;
 4  　　for(i=1;i<N+1;i++)
 5  　　{
 6   　　　　table[0]=table[i];
 7   　　　　j=i-1;
 8   　　　　while(table[0]<table[j])
9   　　　　{
10    　　　　　　table[j+1]=table[j];
11    　　　　　　j--;
12   　　　　}
13   　　　　table[j+1]=table[0];
14  　　}
15 }

 1 //希尔排序
 2 void shell_sort(int table[])
 3 {
 4  　　int d=N;
 5  　　do
 6  　　{
 7   　　　　d=d/3+1;
 8   　　　　shellPass(table,d);
 9 
10   　　}while(d>1);
11 }
12 
13 
14 void  shellPass(int table[], int d)
15 
16 {
17  　　int i,j;
18  　　for(i=d+1;i<N+1;i++)
19  　　if(table[i]<table[i-d])
20  　　{
21   　　　　table[0]=table[i];
22   　　　　j=i-d;
23   　　　　do
24   　　　　{
25    　　　　　　table[j+d]=table[j];
26    　　　　　　j=j-d;
27 
28    　　　　}while(j>0&&table[0]<table[j]);
29 
30   　　　　table[j+d]=table[0];
31  　　} 
32 }

 1 //冒泡排序
 2 void bubble_sort()
 3  {
 4 　　 int i,j,N＝10;
 5  　　int IsExchange;  (交换标志)
 6  　　int   table[N+1];
 7  　　for(i=1;i<N;i++)
 8  　　{
 9   　　　　IsExchange=0;
10   　　　　for(j=N-1;j>=i;j--)
11   　　　　　if(table[j+1]<table[j])
12   　　　　　{
13    　　　　　　　table[0]=table[j+1];
14    　　　　　　　table[j+1]=table[j];
15    　　　　　　　table[j]=table[0];
16    　　　　　　　IsExchange=1;
17   　　　　　}
18   　　　　　if(!IsExchange)
19   　　　　　break;
20  　　}
21  　　printf("bubble_sort table:\n\n");
22 }

 1 //双向冒泡排序
 2 void bin_bubble_sort()
 3 {
 4     int i=1,j=N=10,k,t;
 5 
 6  　 int IsExchange;  (交换标志)
 7  　 int   table[N+1]; 
 8     while(i<j)
 9     {
10         IsExchange=0;
11         t=j;
12         for(;j>=i;j--)
13           if(table[j]<table[j-1])
14           {
15               table[0]=table[j];
16               table[j]=table[j-1];
17               table[j-1]=table[0];
18               IsExchange=1;
19           }
20         j=t;
21         i++;
22         k=i;
23         for(;j>i;i++)
24           if(table[i]>table[i+1])
25           {
26               table[0]=table[i+1];
27               table[i+1]=table[i];
28               table[i]=table[0];
29               IsExchange=1;
30           }
31         i=k;
32         j--;
33         if(!IsExchange)
34            break;
35    }
36    printf("The bin_bubble_sort table:\n\n");
37 }

 1 //快速冒泡排序
 2 void quick_sort(int table[],int low,int high)
 3 {
 4    int pivotpos;(划分后的基准记录的位置)
 5 
 6    int low=1,high=N=10;
 7 
 8    int   table[N+1]; 
 9    if(low<high)
10    {
11       pivotpos=partition(table,low,high);
12       quick_sort(table,low,pivotpos-1);
13       quick_sort(table,pivotpos+1,high);
14    }
15 
16    printf("The quick_sort table:\n\n");
17 }
18 
19 int partition(int table[],int i,int j)
20 {
21  
22    table[0]=table[i];
23    while(i<j)
24    {
25        while(i<j && (table[j]>=table[0]))
26            j--;
27        if(i<j)
28            table[i++]=table[j];
29        while(i<j && (table[i]<=table[0]))
30            i++;
31        if(i<j)
32            table[j--]=table[i];
33    }
34    table[i]=table[0];
35    return i;
36 }

 1 
 2 void select_sort()
 3 {
 4  　　int i,j,k,n=10;
 5 
 6      int table[N+1];
 7      for(i=1;i<N+1;i++)
 8      {
 9          k=i;
10          for(j=N;j>i;j--)
11            if(table[j]<table[k])
12               k=j;
13          if(k!=i)
14          {
15              table[0]=table[i];
16              table[i]=table[k];
17              table[k]=table[0];
18          }
19       }
20       printf("the select_sort table:\n");
21 }

 1 typedef int KeyType;     //(key type关键字的类型)
 
 5 #define MAXSIZE 500

 9 typedef struct{
10       KeyType key;     //(key定义关键字)
11 
12 }RedType;

16 typedef struct{
17     RedType list[MAXSIZE+1];
18     int length;
19 }SqList;

23 void heapsort()    
24 
25 {
26         int i,j;
27 
28         SqList *table;
29         for (i =MAXSIZE/2; i >= 1; i--)          //(大根堆 heap）
30                 adjust(table, i, MAXSIZE);
31         for (i =MAXSIZE; i > 0; i--)
32         {
33                 table->list[0]=table->list[1];  
34 
35                 table->list[1]=table->list[i]; 
36 
37                 table->list[i]=table->list[0];
38 
39                 adjust(table, 1, i-1);
40         }       
41 }
42 int adjust(SqList *table, int k, int m)
43 {
44         int i=k,j;
45         RedType temp;
46         SqList *t;
47         t=(SqList *)malloc(sizeof(SqList));
48         t->list[k]=table->list[k];          
49         temp.key=table->list[k].key;
50         j=2*i;
51         while (j <= m)
52         {
53                 if ((j < m) && (table->list[j].key < table->list[j+1].key))  
54 
55                 {
56                      j++;
57                 }
58                 if (temp.key < table->list[j].key)  
59 
60                 {
61                      table->list[i] = table->list[j];  
62 
63                      i = j;  
64                      j=2*i;
65                 }
66                     
67                 else
68                  break;
69         }     
70         table->list[i] = t->list[i];
71 
72 }

 1 typedef int KeyType;     //(key type关键字的类型)

 5 #define MAXSIZE 500

 9 typedef struct{
10       KeyType key;     //(key定义关键字)
11 
12 }RedType;
13 

16 typedef struct{
17     RedType list[MAXSIZE+1];
18     int length;
19 }SqList;

 1 void MergeSort(SqList *table)     
 3 {
 4  　　int len,i;
 5  　　for(len=1;len<MAXSIZE+1;len*=2)
 6  　　{
 7           for(i=1;i+2*len-1<MAXSIZE;i=i+2*len)
 8           Merge(table,i,i+len-1,i+2*len-1);
 9           if(i+len-1<MAXSIZE)
10           Merge(table,i,i+len-1,MAXSIZE);
11      }
12 }
13 int Merge(SqList *table,int low,int m,int high)（二路归并、分治法二路归并排序共同调用）
14 {
15     SqList *table1;
16     int i=low,j=m+1,p=0;
17     table1=(SqList *)malloc(sizeof(SqList));
18  
19     while(i<=m&&j<=high)
20     {
21           table1->list[p++] = (
22 
23                (table->list[i].key<=table->list[j].key)?table->list[i++]:table->list[j++] ); 
24 
25     }
26     while(i<=m)
27     {
28           table1->list[p++]=table->list[i++]; 
29 
30     }
31     while(j<=high)
32     {
33           table1->list[p++]=table->list[j++]; 
34 
35     }
36     for(p=0,i=low;i<=high;p++,i++)
37     {
38           table->list[i]=table1->list[p]; 
39 
40     }
41     return 0;
42 }
43 
44  
45 
46 （分治法二路归并排序）
47 void MergeSortDC(SqList *table,int low,int high)  
48 
49 {
50     int mid;
51     if(low<high)
52     {
53         mid=(low+high)/2;
54         MergeSortDC(table,low,mid);
55         MergeSortDC(table,mid+1,high);
56         Merge(table,low,mid,high);
57     }
58 }