排序一栏（总结帖）

 1 /*归并排序递归版
 2   Coder @ Gxjun
 3   2014/3/30/16:42
 4 */
 5 #include<stdio.h>
 6 #include<string.h>
 7 #include<stdlib.h>
 8 void merge(int A[],int lowc ,int high,int tol_len)
 9 {
10     int *cc;
11     cc=(int *)malloc(sizeof(int)*(1+tol_len));  // <==> int cc[tol_len];
12     int i,j,k=0;
13     i=lowc ;
14     j=high;
15     while(i<high&&j<tol_len)
16     {
17         if(A[i]>A[j])  //以升序即从小到大的顺序排列
18         {
19             cc[k++]=A[j];
20             j++;
21         }
22         else
23         {
24             cc[k++]=A[i];
25             i++;
26         }
27     }
28     //有可能不是一起放完，因此还需要对剩余的元素放到cc中
29     for( ; i<high ; i++)
30         cc[k++]=A[i];
31     for( ; j<tol_len ; j++)
32         cc[k++]=A[j];
33     //然后将排好序的这个新子段，放回去
34      k=0;
35     for(i=lowc ;i<tol_len ;i++)
36         A[i]=cc[k++];
37         free(cc);
38 }
39 void merge_sort(int A[],int st,int en)
40 {
41     if(st<en-1) //两者至少相隔一个元素
42     {
43       int mid=st+(en-st)/2;
44       merge_sort(A,st,mid);
45       merge_sort(A,mid,en);
46       merge(A,st,mid,en);
47     }
48 }
49 int array[12];
50 int main()
51 {
52     int n,i;
53     while(scanf("%d",&n)!=EOF)
54     {
55         for(i=0;i<n;i++)
56             scanf("%d",array+i);
57       merge_sort(array,0,n);
58      for(i=0;i<n;i++)
59        printf("%3d",array[i]);
60        putchar(10);
61     }
62 
63   return 0;
64 }

 1 /*归并排序非递归版
 2   Coder @ Gxjun
 3   2014/3/30/16:22
 4 */
 5 #include<stdio.h>
 6 #include<string.h>
 7 #include<stdlib.h>
 8 void merge(int A[],int lowc ,int high,int tol_len)
 9 {
10     int *cc;
11     cc=(int *)malloc(sizeof(int)*(1+tol_len));  // <==> int cc[tol_len];
12     int i,j,k=0;
13     i=lowc ;
14     j=high;
15     while(i<high&&j<tol_len)
16     {
17         if(A[i]>A[j])  //以升序即从小到大的顺序排列
18         {
19             cc[k++]=A[j];
20             j++;
21         }
22         else
23         {
24             cc[k++]=A[i];
25             i++;
26         }
27     }
28     //有可能不是一起放完，因此还需要对剩余的元素放到cc中
29     for( ; i<high ; i++)
30         cc[k++]=A[i];
31     for( ; j<tol_len ; j++)
32         cc[k++]=A[j];
33     //然后将排好序的这个新子段，放回去
34      k=0;
35     for(i=lowc ;i<tol_len ;i++)
36         A[i]=cc[k++];
37 
38         free(cc);
39 }
40 void merge_sort(int A[],int st,int en)
41 {
42     int i,s,t;
43     t=1;
44     while(t<=en-st)
45     {
46       s=t;  //每一个子段的长度
47       t=2*t; //合并的长度
48       i=st;
49       while(i+t<=en-st)
50       {
51         merge(A,i,i+s,i+t);
52         i+=t;
53       }
54     }
55     if(s<en-st)
56     merge(A,st,s+st,en);
57 }
58 int array[12];
59 int main()
60 {
61     int n,i;
62     while(scanf("%d",&n)!=EOF)
63     {
64         for(i=0;i<n;i++)
65             scanf("%d",array+i);
66       merge_sort(array,0,n);
67      for(i=0;i<n;i++)
68        printf("%3d",array[i]);
69        putchar(10);
70     }
71 
72   return 0;
73 }

 1 /*
 2 Quck_sort();
 3 Coder @Gxjun
 4 2014/3/30
 5 */
 6 #include<stdio.h>
 7 #include<string.h>
 8 #include<stdlib.h>
 9 #include<time.h>
10 void swap(int *a ,int *b)
11 {
12     if(*a!=*b)
13     {
14       *a^=*b;
15       *b^=*a;
16       *a^=*b;
17     }
18 }
19 int divepart(int A[], int left,int right)
20 {
21 
22     /*srand(time(NULL));
23     int key=A[left+rand()%(right-left)];*/
24     int key=A[left];
25     while(left<right)
26     {
27         //还是以升序为列，即从小到大
28         while(key<A[right])
29             right--;
30        // swap(&A[left],&A[right]);
31         while(key>A[left])
32             left++;
33         swap(&A[right],&A[left]);
34     }
35     return left;
36 }
37 void K_sort(int A[],int lowc,int high )
38 {
39    if(lowc<high)
40     {
41         int mid=divepart(A,lowc,high);
42         K_sort(A,lowc,mid);
43         K_sort(A,mid+1,high);
44     }
45 }
46 int array[12];
47 int main()
48 {
49     int n,i;
50     while(scanf("%d",&n)!=EOF)
51     {
52      for(i=0;i<n;i++)
53         scanf("%d",array+i);
54        K_sort(array,0,n-1);
55      for(i=0;i<n;i++)
56        printf("%3d",array[i]);
57        putchar(10);
58     }
59     return 0;
60 }