排序学习

看了几个程序，有冒泡排序、归并排序、插入排序等。
冒泡排序，是时间常数最大的，每次循环将最大的元素放到最后，
插入排序，每次取出后一个元素，和前面的元素比较，大的放在后面。
归并排序，

#include<stdio.h>
#include<stdlib.h>
#define len 5

int a[len]={11,5,2,4,7};

void insert()
{
    int tmp;
    int i,j,m;
    for( i=0;i<len-1;i++)
    {
        for( j=0;j<=i;j++)
        {
            tmp=a[j+1];


            if(a[j]>a[j+1])
            {


                a[j+1]=a[j];

                a[j]=tmp;

            }
        }
        // for(m=0;m<len;m++)
        // printf("buble iiiiiii a[%d]=%d\n",m,a[m]);
        printf("%d,%d,%d,%d,%d\n",a[0],a[1],a[2],a[3],a[4]);


    }



}


void buble()
{
    int tmp;
    int i,j,m;
    for ( i=0;i<len;i++)
    {
        for( j=0;j<len-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }


            //printf("buble i= %d a[%d]=%d\n",i,j,a[j]);
        }

        for(m=0;m<len;m++)
            printf("buble bbbbb a[%d]=%d\n",m,a[m]);


    }


}


int main(void)
{
    // int a[len]={10,5,2,4,7}
    int i;
    for(i=0;i<len;i++)
        printf("buble x a[%d]=%d\n",i,a[i]);

    insert();
    //buble();

    for(i=0;i<len;i++)
        printf("buble xxx a[%d]=%d\n",i,a[i]);
    // buble( a[len],len);

}

插入排序图例：

归并排序：

将大的序列转换成小的

#include<stdio.h>
#define LEN 9
int a[LEN]={5,2,4,7,1,3,2,8,6};

void merge(int start ,int mid,int end)
{
   int n1=mid-start + 1;
   int n2=end-mid;
   int left[n1],right[n2];
   int i,j,k;

   for(i=0;i<n1;i++)
       left[i]=a[start+i];

   for(j=0;j<n2;j++)
       right[j]=a[mid+1+j];
   i=0;
   j=0;
   k=start;
   for(;i<n1&&j<n2;)
    {
      if(left[i]<right[j])
         a[k++]=left[i++];

      else
         a[k++]=right[j++];

    }
   while(i<n1)
         a[k++]=left[i++];

   while(j<n2)
         a[k++]=right[j++];


}
void sort(int start,int end)
{
  int mid;
  if(start<end)
  {
    mid=(start+end)/2;
    printf("sort (%d~%d,%d~%d) %d %d %d %d %d %d %d %d %d\n",start,mid,mid+1,end,a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
    sort(start,mid);
    sort(mid+1,end);
    merge(start,mid,end);

    printf("merge (%d~%d,%d~%d) %d %d %d %d %d %d %d %d %d\n",start,mid,mid+1,end,a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
  }


}
int main(void)

{
  sort(0,LEN-1);



}

output

sort (0~4,5~8) 5 2 4 7 1 3 2 8 6
sort (0~2,3~4) 5 2 4 7 1 3 2 8 6
sort (0~1,2~2) 5 2 4 7 1 3 2 8 6
sort (0~0,1~1) 5 2 4 7 1 3 2 8 6
merge (0~0,1~1) 2 5 4 7 1 3 2 8 6
merge (0~1,2~2) 2 4 5 7 1 3 2 8 6
sort (3~3,4~4) 2 4 5 7 1 3 2 8 6
merge (3~3,4~4) 2 4 5 1 7 3 2 8 6
merge (0~2,3~4) 1 2 4 5 7 3 2 8 6
sort (5~6,7~8) 1 2 4 5 7 3 2 8 6
sort (5~5,6~6) 1 2 4 5 7 3 2 8 6
merge (5~5,6~6) 1 2 4 5 7 2 3 8 6
sort (7~7,8~8) 1 2 4 5 7 2 3 8 6
merge (7~7,8~8) 1 2 4 5 7 2 3 6 8
merge (5~6,7~8) 1 2 4 5 7 2 3 6 8
merge (0~4,5~8) 1 2 2 3 4 5 6 7 8