数据结构-排序

#include "stdio.h"
#include "stdlib.h"
int show_array(int a[],int n)
{
    int i;
    for(i=0;i         printf("%2d ",a[i]);
    printf("n");
}
int insert_sort(int a[],int n)
{
    int i,j,temp;
    for(i=1;i     {
        temp=a[i];j=i;
        while(j>0&&a[j-1]>temp)
           {
               a[j]=a[j-1];j--;
           }
        if(j!=i)
            a[j]=temp;
    }
    return 1;
}

int binary_insert_sort(int a[],int n)
{
    int i,j,temp;
    int low,high,mid;
    for(i=1;i     {   temp=a[i];
        low=0;high=i-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(a[mid]                 low=mid+1;
            else
                high=mid-1;
        }
        for(j=i;j>high+1 ;j--)
            a[j]=a[j-1];
        a[high+1]=temp;
    }
    return 1;
}
int bubble_sort(int a[],int n)
{
    int i,j,temp,flag;
    for(i=0;i     {   flag=1;
        for(j=0;j         {
            if(a[j]>a[j+1])
            {
                temp=a[j];a[j]=a[j+1];a[j+1]=temp;flag=0;
            }
        }
        if(flag==1)
            break;
    }
    return 1;
}
int select_sort(int a[],int n)
{
    int i,j,temp,k;
    for(i=0;i     {    k=i;
        for(j=i+1;j            if(a[j]                  k=j;
        if(k!=i)
        {
            temp=a[i];a[i]=a[k];a[k]=temp;
        }
    }
    return 1;
}
int shell_sort(int a[],int n)
{
   int i,j,temp,d;
   d=n/2;
   while(d>0)
   {
        for(i=d;i         {
           temp=a[i];j=i;
           while(j>0&&a[j-d]>temp)
             {
               a[j]=a[j-d];j=j-d;
              }
           if(j!=i)
              a[j]=temp;
        }
       d=d/2;
   }

    return 1;
}
int one_pass_quicksort(int a[],int low,int high)
{
     int temp;
     temp=a[low];
     while(low      {
         while(lowtemp)
            high--;
         if(low             a[low]=a[high];
         while(low             low++;
         if(low             a[high]=a[low];
     }
     a[high]=temp;
     return high;
}
int quick_sort(int a[],int low,int high)
{
    int k;
    if(low     {
        k=one_pass_quicksort(a,low,high);
        quick_sort(a,low,k-1);
        quick_sort(a,k+1,high);
    }
}

int heap_adjust(int a[],int s,int m)
{
    int i,j,temp;
    temp=a[s];i=2*s+1;
    while(i<=m)
    {
        if(i+1<=m&&a[i+1]>a[i])
            i=i+1;
        if(a[i]             break;
        else
        {
            a[s]=a[i];
            s=i;
            i=2*i+1;
        }
    }
    a[s]=temp;

}
int heap_sort(int a[],int n)
{    //big  from 0
    int i,temp;
    for(i=n/2;i>=0;i--)
        heap_adjust(a,i,n-1);
    for(i=n-1;i>0;i--)
    {   temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        heap_adjust(a,0,i-1);
    }
}
int merge_one_pass(int a[],int low,int mid,int high)
{
    int *b,i,j,k;
    b=(int *)malloc((high-low+1)*sizeof(int));
    i=low;j=mid+1;k=0;
    while(i<=mid&&j<=high)
    {
        if(a[i]         {
            b[k]=a[i];k++;i++;
        }
        else
        {
            b[k]=a[j];k++;j++;
        }
    }
    while(i<=mid)
    {
         b[k]=a[i];k++;i++;
    }
    while(j<=high)
    {
        b[k]=a[j];k++;j++;
    }
    for(k=0;k<(high-low+1);k++)
    {
        a[low+k]=b[k];
    }
   free(b);
}
int merge_sort(int a[],int low,int high)
{
    int mid;
    if(low     {
        mid=(low+high)/2;
        merge_sort(a,low,mid);
        merge_sort(a,mid+1,high);
        merge_one_pass(a,low,mid,high);
    }
}
int main()

{  int a[10]={6,3,9,1,2,8,4,10,7,5};
   int n=10;
   show_array(a,n);
   merge_sort(a,0,n-1);
   show_array(a,n);

}