qsort.c

linux下Qsort的C语 言的实现

#include "qsort.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void swap(void *p1, void *p2, int size)
{
     void * tmp=malloc(size);
     memmove(tmp,p1,size);
     memmove(p1,p2,size);
     memmove(p2,tmp,size);
     free(tmp);
}

void sort_3elem(void *base, int left, int right, int size, int(*cmp)(const void *, const void *))
{
     int center=(left+right)/2;
     void * lp=base+left*size;
     void * cp=base+center*size;
     void * rp=base+right*size;
     if(cmp(lp,cp)>0) swap(lp,cp,size);
     if(cmp(lp,rp)>0) swap(lp,rp,size);
     if(cmp(cp,rp)>0) swap(cp,rp,size);
}

void quicksort(void *base, int left, int right, int size, int(*cmp)(const void *, const void *))
{
     int center=(left+right)/2;
     void * lp=base+left*size;
     void * cp=base+center*size;
     void * rp=base+right*size;
     void * pivot;
     void * ip=lp+size;
     void * jp=rp-2*size;


     if(left>=right) return;

     if(left+1==right)
      {
         if(cmp(lp,rp)>0) swap(lp,rp,size);
         return;
      }

     sort_3elem(base,left,right,size,cmp);

     if(left+2==right) return;

     swap(cp,rp-size,size);
     pivot=malloc(size);
     memmove(pivot,rp-size,size);
     while(1)
     {
         while(ip<=jp&&cmp(ip,pivot)<=0) ip+=size;
         while(ip<=jp&&cmp(jp,pivot)>0) jp-=size;
         if(ip<jp) swap(ip,jp,size);
         else break;
     }
    swap(ip,rp-size,size);

    quicksort(base,left,(ip-base)/size-1,size,cmp);
    quicksort(base,(ip-base)/size+1,right,size,cmp);

    free(pivot);
}

void q_sort(void *base, int nmemb, int size, int(*cmp)(const void *, const void *))
{
    quicksort(base,0,nmemb-1,size,cmp);
}