排序算法

最近找工作，又把基础的东西温习了一遍，其中最基本的就是几种排序算法。

 

均以从小到大顺序排序

/*冒泡排序*/

#define swap(x,y) {int t;t=*x;*x=*y;*y=t;}
void bubbleSort(int *,int);
void bubbleSort(int *s,int n){
    int i,j;
    for(i=0;i<n-1;i++)
        for(j=n-1;j>i;j--)
            if(s[j]<s[j-1])
                swap(&s[j],&s[j-1])
}

/*选择排序*/

#define swap(x,y) {int t;t=*x;*x=*y;*y=t;}
void selectSort(int *,int);
void selectSort(int *s,int n){
    int i,j,m;
    for(i=0;i<n-1;i++){
        for(j=i+1,m=i;j<n;j++)
            if(s[j]<s[m]) m=j;
        if(i!=m) swap(&s[i],&s[m]);
    }
}

/*插入排序*/

void insertSort(int*,int);
void insertSort(int *s,int n){
    int i,j;
    int m;
    for(i=1;i<n;i++){
        m=s[i];
        for(j=i;j>0 && s[j-1]>m;j--) s[j]=s[j-1];
        s[j]=m;
    }
}

/*希尔排序(可以选用别的希尔序列)*/

void shellSort(int *,int);
void shellSort(int *s,int n){
    int incr,i,j;
    int m;
    for(incr=n/2;incr>0;incr/=2){
        for(i=incr;i<n;i++){
            m=s[i];
            for(j=i;j>=incr && s[j-incr]>m;j-=incr) s[j]=s[j-incr];
            s[j]=m;
        }
    }
}

/*快速排序(选用首,中位,尾三数的中间数为分割数)*/

#define cutoff 3
#define swap(x,y) {int t;t=*x;*x=*y;*y=t;}

extern void insertSort(int *,int);
static int median3(int *,int,int);
static void qsort(int *,int,int);
void quickSort(int *,int);

void quickSort(int *s,int n){
    qsort(s,0,n-1);
}

static int median3(int *s,int left,int right){
    int center=(left+right)/2;
    if(s[left]>s[center]) swap(&s[left],&s[center]);
    if(s[left]>s[right]) swap(&s[left],&s[right]);
    if(s[center]>s[right]) swap(&s[center],&s[right]);
    swap(&s[center],&s[right-1]);
    return s[right-1];
}

static void qsort(int *s,int left,int right){
    int pivot,i,j;
    if(left+cutoff<=right){
        pivot=median3(s,left,right);
        i=left;
        j=right-1;
        for(;;){
            while(s[++i]<pivot);
            while(s[--j]>pivot);
            if(i<j) swap(&s[i],&s[j])
            else break;
        }
        swap(&s[i],&s[right-1]);
        qsort(s,left,i-1);
        qsort(s,i+1,right);
    }else{
        insertSort(s+left,right-left+1);
    }
}


/*归并排序(递归)*/

#include <stdlib.h>
static void msort(int *,int *,int ,int );
static void merge(int *,int *,int ,int ,int );
void mergeSort(int *,int );

void mergeSort(int *s,int n){
    int *d;
    d=(int *)malloc(sizeof(int)*n);
    msort(s,d,0,n-1);
    free(d);
}

static void msort(int *s,int *d,int i,int j){
    if(i<j){
        int m=(i+j)/2;
        msort(s,d,i,m);
        msort(s,d,m+1,j);
        merge(s,d,i,m,j);
        for(;i<=j;i++) s[i]=d[i];
    }else if(i==j) d[i]=s[i];
}

static void merge(int *s,int *d,int i,int m,int j){
    int t,k;
    for(t=m+1,k=i;i<=m && t<=j;k++){
        if(s[i]<s[t]) d[k]=s[i++];
        else d[k]=s[t++];
    }
    while(i<=m) d[k++]=s[i++];
    while(t<=j) d[k++]=s[t++];
}



/*归并排序(改进,非递归)*/

#include <stdlib.h>
void mergeSort(int *,int);
static void msort(int *,int*,int,int);
static void merge(int *,int *,int,int,int);

void mergeSort(int *s,int n){
    int incr,*d;
    d=(int *)malloc(sizeof(int)*n);
    incr=1;
    while(incr<n){
        msort(s,d,incr,n);
        incr<<=1;;
        msort(d,s,incr,n);
        incr<<=1;
    }
}

static void msort(int *s,int *d,int incr,int n){
    int i;
    for(i=0;i<=n-2*incr;i+=2*incr)
        merge(s,d,i,i+incr-1,i+2*incr-1);
    if(i+incr<n) merge(s,d,i,i+incr-1,n-1);
    else for(;i<n;i++) d[i]=s[i];
}

static void merge(int *s,int *d,int i,int m,int j){
    int t,k;
    for(t=m+1,k=i;i<=m && t<=j;k++)
        if(s[i]<s[t]) d[k]=s[i++];
        else d[k]=s[t++];
    while(i<=j) d[k++]=s[i++];
    while(t<=j) d[k++]=s[t++];
}

/*堆排序*/

#define swap(x,y) {int t;t=*x;*x=*y;*y=t;}
static void percDown(int *,int,int);
void heapSort(int *,int);

static void percDown(int *s,int i,int j){
    int top,child;
    top=s[i];
    for(;i*2<=j;i=child){
        child=i*2;
        if(child!=j && s[child+1]>s[child])
            child++;
        if(s[child]>top)
            s[i]=s[child];
        else break;
    }
    s[i]=top;
}

void heapSort(int *s,int n){
    int i;
    for(i=n/2;i>=0;i--)  /*构建大顶堆*/
        percDown(s,i,n-1);
    for(i=n-1;i>0;i--){
        swap(&s[0],&s[i]);  /*替换堆顶*/
        percDown(s,0,i-1);  /*调整堆*/
    }
}