几种排序算法实现分析

合并排序

void merge(int a[],int left,int mid,int right,int b[])    {      int i = left;        int j = mid +1;        int k = left;        while(i<=mid&&j<=right)        {            if(a[i]<a[j])                b[k++]=a[i++];            else                b[k++]=a[j++];        }        if(i>mid)            {                while(j<=right)                    b[k++]=a[j++];            }            else            {                while(i<=mid)                    b[k++]=a[i++];            }    }    void copy(int a[],int b[],int left,int right)    {        for(int i=left;i<=right;i++)            a[i]=b[i];    }    void mergeSort(int a[],int left,int right,int len)    {        if(left<right)        {            int mid = (left+right)/2;            mergeSort(a,left,mid,len);            mergeSort(a,mid+1,right,len);            int * b = new int[len];            //将排序后的结果存入b            merge(a,left,mid,right,b);            copy(a,b,left,right);            //将b中的结果转到a;            delete[] b;        }    }

快速排序

void swap(int &a,int &b)   {       int buf = a;       a = b;       b = buf;   }      int partion(int a[],int low,int high)   {       int i = low;       int j = high+1;       int x = a[low];       while(true)       {           while(i<high&&a[++i]<x);           while(j>low&&a[--j]>x);           if(i>=j)               break;           swap(a[i],a[j]);       }       swap(a[j],a[low]);       return j;   }   void quickSort(int a[],int low,int high)   {       if(low<high)       {           int q = partion(a,low,high);           quickSort(a,low,q-1);           quickSort(a,q+1,high);       }   }

void swap(int &a,int &b)   {       int buf = a;       a = b;       b = buf;   }   void insertSort(int a[],int len)   {       for(int i = 1;i<len;i++)       {           for(int j = i;j>0;j--)           {               if(a[j]<a[j-1])                   swap(a[j],a[j-1]);               else                   break;              }       }   }

#include <math.h>    #include <stdio.h>    #include <vector>    #include <string>    using namespace std;      void swap(int &a,int &b)    {        int buf = a;        a = b;        b = buf;    }    int mi(int cnt)    {      int s =1;        for(int i=1;i<=cnt;i++)        {          s*=2;      }        return s;    }    void hillInsert(int a[],int d,int len)    {      for(int i =d;i<len;i++)        {          for(int j=i;j>0;j=j-d)            {              if(a[j]<a[j-d])                {                  swap(a[j],a[j-d]);              }              else                  break;          }      }  }    /*    *d是增量序列    *hillCnt是增量序列的长度    */    void hillSort(int a[],int d[],int hillCnt,int len)    {      for(int i=0;i<hillCnt;i++)        {          hillInsert(a,d[i],len);      }  }    void main()  {        int a[] = {76,22,33,12,67,45};        int len = sizeof(a)/sizeof(int);        int hillCnt =log(len+1.0)/log(2.0);        int *d = new int[hillCnt];        for(int i=0;i<hillCnt;i++)      {            d[i] = mi(hillCnt-i)-1;      }        hillSort(a,d,hillCnt,len);        for(int i=0;i<len;i++)      {          cout<<a[i]<<endl;      }  }

void swap(int &a,int &b)  {      int buf = a;        a = b;        b = buf;    }    void bubbleSort(int a[],int len)  {      for(int i=1;i<len;i++)      {          for(int j=0;j<len-i;j++)          {                if(a[j]>a[j+1])                  swap(a[j],a[j+1]);          }      }  }

#include "Queue.h"    #include "QueueItem.h"    #include <math.h>    #include <stdio.h>    #include <vector>    #include <string>    using namespace std;    void swap(int &a,int &b)    {        int x = a;        a = b;        b = x;    }    void heapAdjust(int a[],int len,int s)    {      for(int i=2*s+1;i<len;i=2*i+1)        {            if(i+1<len&&a[i]>a[i+1])i++;            if(a[i]>a[s])                break;            swap(a[s],a[i]);            s = i;            }    }    void heapSort(int a[],int len)    {        for(int i=len/2-1;i>=0;i--)        {          heapAdjust(a,len,i);      }        for(int i=0;i<len;i++)        {          cout<<a[i]<<endl;      }        for(int i=len;i>=1;i--)        {          cout<<a[0]<<"  "<<a[i-1]<<endl;            swap(a[i-1],a[0]);            heapAdjust(a,i-1,0);        }    }    void main()    {        int a[] = {76,22,33,12,67,45,24};        int len = sizeof(a)/sizeof(int);        heapSort(a,len);        for(int i=0;i<len;i++)        {          cout<<a[i]<<endl;      }  }

#include "stdafx.h"  #include "Queue.h"  #include "QueueItem.h"  #include <math.h>  #include <stdio.h>  #include <vector>  #include <string>  using namespace std;  #define MAX_NUM_OF_KEY 8  #define RADIX 10  #define MAX_SPACE 10000    struct SLCell  {      int value[MAX_NUM_OF_KEY];      int next;  };  struct SLList  {      SLCell r[MAX_SPACE];      int keynum;//一个数包含的位数，最大为8为      int recnum;//排序数的个数，最大为10000  };  //将每位相同的组合在一起形成单独的链表  void distribute(SLList &r,int index,int f[],int e[])  {      int len = r.recnum;      for(int i=0;i<RADIX;i++)          f[i]=0;//对f进行初始化      for(int p=r.r[0].next;p;p=r.r[p].next)      {          int j = r.r[p].value[index];          if(!f[j])              f[j]=p;          else              r.r[e[j]].next = p;          e[j]=p;      }    }  //将链表整合在一起  void collect(SLList &r,int index,int f[],int e[])//f中存的每一个队列的首，e是每一个尾  {      int j;      for(j=0;!f[j];j++);      r.r[0].next=f[j];      int t = e[j];      while(j<RADIX)      {          for(j=j+1;j<RADIX-1&&!f[j];j=j+1);          if(j<RADIX&&f[j])          {              r.r[t].next=f[j];              t=e[j];          }      }      r.r[t].next = 0;    }  void radixSort(SLList &r,int f[],int e[])  {      for(int i=0;i<r.keynum;++i)      {          distribute(r,i,f,e);          collect(r,i,f,e);      }  }    void main()  {      SLList list;            list.r[0].next = 1;      list.r[1].value[0]=3;      list.r[1].value[1]=0;      list.r[1].value[2]=2;      list.r[1].next = 2;      list.r[2].value[0]=3;      list.r[2].value[1]=3;      list.r[2].value[2]=9;      list.r[2].next = 3;      list.r[3].value[0]=8;      list.r[3].value[1]=8;      list.r[3].value[2]=0;      list.r[3].next = 4;      list.r[4].value[0]=4;      list.r[4].value[1]=1;      list.r[4].value[2]=7;      list.r[4].next = 0;      list.keynum = 3;      list.recnum = 5;      int *f = new int[RADIX];      int *e = new int[RADIX];        for(int p=list.r[0].next;p;p=list.r[p].next)      {          for(int i =list.keynum-1;i>=0;i--)          {              cout<<list.r[p].value[i];          }          cout<<endl;      }      cout<<"------------------"<<endl;        radixSort(list,f,e);      for(int p=list.r[0].next;p;p=list.r[p].next)      {          for(int i =list.keynum-1;i>=0;i--)          {              cout<<list.r[p].value[i];          }          cout<<endl;      }      cout<<"------------------"<<endl;      delete[] f;      delete[] e;  }