常用的六种排序

蜡笔编程

常用的六种排序
[mw_shl_code=applescript,true]#include<stdio.h>
#include<malloc.h>
void Swap(int a[],int i,int j)
{
    int temp=a;
    a=a[j];
    a[j]=temp;
}

//冒泡排序
void BubbleSorting(int a[],int len)
{
   for(int i=0;i<len;i++)
   {
       for(int j=i+1;j<len;j++)
       {
           if(a>a[j])
           {
              Swap(a,i,j);
           }
       }
   }
}

//选择排序
void SelectSorting(int a[],int len)
{
     for(int i=0;i<len;i++)
     {
         int k=i;
         int temp=a[k];
         for(int j=i+1;j<len;j++)
         {
             if(a[j]<temp)
             {
                temp=a[j];
                k=j;
             }
         }
         Swap(a,i,k);
     }
}

//插入排序
void InsertSorting(int a[],int len)
{
    for(int i=1;i<len;i++)
    {
        int k=i;
        int temp=a[k];
        for(int j=i-1;(j>=0)&&(a[j]>temp);j--)
        {
            a[j+1]=a[j];
            k=j;
        }
        a[k]=temp;
    }
}

//希尔排序
void ShellSorting(int a[],int len)
{
     int gap=len;
     do
     {
        gap/=2;
        for(int i=gap;i<len;i++)
        {
           int k=i;
           int temp=a[k];
           for(int j=i-gap;(j>=0)&&(a[j]>temp);j-=gap)
           {
                a[j+gap]=a[j];
                k=j;
           }
           a[k]=temp;
        }
     }while(gap>0);
}

//快速排序
int Pos(int a[],int low,int high)
{
     int i=low;
     int j=high;
     int k=a[low];
     while(i<j)
     {
          while(a[j]>k) j--;
          Swap(a,i,j);
          while(a<k) i++;
          Swap(a,i,j);
     }
     return i;
}

void QSorting(int a[],int low,int high)
{  
       if(low<high)
       {
         int pos=Pos(a,low,high);
         QSorting(a,low,pos);
         QSorting(a,pos+1,high);
       }
}

void QuickSorting(int a[], int len)
{
    QSorting(a, 0, len-1);
}

//归并排序
void MergerSorting(int a[],int des[],int low,int mid,int high)
{
     int i=low;
     int j=mid+1;
     int k=low;
     while((i<=mid)&&(j<=high))
     {
           if(a<a[j]) des[k++]=a[i++];
           else des[k++]=a[j++];
     }
     while(i<=mid) des[k++]=a[i++];
     while(j<=high) des[k++]=a[j++];
}

void MSorting(int a[],int des[],int low,int high,int max)
{
    if(low==high)
    {
         des[low]=a[low];
    }
    else
    {
      int mid=(low+high)/2;
      int* space=(int*)malloc(sizeof(int)*max);
      if(space!=NULL)
      {
          MSorting(a,space,low,mid,max);
          MSorting(a,space,mid+1,high,max);
          MergerSorting(space,des,low,mid,high);
          free(space);
      }
    }
}

void MerSorting(int a[],int len)
{
    MSorting(a,a,0,len-1,len);
}

void ShowSorting(int a[], int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d ", a);
    }
    printf("\n");
}

int main()
{
    int a[]={1,5,21,20,31,2,15,100};
    int len=sizeof(a)/sizeof(*a);
    //BubbleSorting(a,len);
    //SelectSorting(a,len);
    //InsertSorting(a,len);
    //ShellSorting(a,len);
    //QuickSorting(a,len);
    MerSorting(a,len);
    ShowSorting(a,len);
    return 0;
}[/mw_shl_code]