四种基本的排序算法练习

今天没事又看了一遍算法书的排序一章，所以就顺便把书上讲的自己写了一下，当做练习。

程序里包括了四种排序算法，分别是：插入排序，希尔排序，归并排序，快速排序。
主函数想用哪一种，就把函数指针指向那个算法。

#include <stdio.h>

void insert_sort(int A[],int left,int right);
void shell_sort(int A[],int left,int right);
void merge_sort(int A[],int left,int right);
void quick_sort(int A[],int left,int right);

void out(int A[],int left,int right)
{
    int i;
    for(i=left;i<=right;i++) {
        printf("%d ",A[i]);
    }
    printf("\n");
}

int main(int argc,char *argv[])
{
    void (*sort)(int *,int,int);

    int A[10] = {2,6,8,12,23,19,15,21,6,13};

//    sort = insert_sort;
//    sort = shell_sort;
//    sort = merge_sort;
    sort = quick_sort;

    sort(A,0,9);

    out(A,0,9);
    return 0;
}

//insert_sort
void insert_sort(int A[],int left,int right)
{
    int i,j;
    int tmp;

    for(i=left+1;i<=right;i++) {

        tmp = A[i];

        for(j=i;j>0&&A[j-1]>tmp;j--) {
            A[j] = A[j-1];
        }
        A[j] = tmp;
    }
}

//shell_sort
void shell_sort(int A[],int left,int right)
{
    int i,j,increment;
    int tmp;
    int n = right - left + 1;

    for(increment=n/2;increment>0;increment/=2) {
        for(i=increment;i<n;i++) {
            tmp = A[i];
            for(j=i;j>=increment;j-=increment) {
                if(tmp<A[j-increment])
                    A[j] = A[j-increment];
                else
                    break;
            }
            A[j] = tmp;
        }
    }
}

//merge_sort
int A_tmp[10];

void merge(int A[],int left,int center,int right)
{
    int i=left,j=center+1,k=left;

    while(i<=center&&j<=right) {
        if(A[i]<A[j]) {
            A_tmp[k++] = A[i++];
        }
        else {
            A_tmp[k++] = A[j++];
        }
    }

    while(i<=center) {
        A_tmp[k++] = A[i++];
    }

    while(j<=right) {
        A_tmp[k++] = A[j++];
    }

    for(i=left;i<=right;i++) {
        A[i] = A_tmp[i];
    }
}

void merge_sort(int A[],int left,int right)
{
    int center;

    if(left<right) {
        center = (left + right)/2;
        merge_sort(A,left,center);
        merge_sort(A,center+1,right);
        merge(A,left,center,right);
    }
}

//quick_sort
#define cutoff    3
void swap(int *a,int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void quick_sort(int A[],int left,int right)
{
    int i,j,pivot,center;

    if(left+cutoff<=right) {
        center = (left+right)/2;
        pivot = A[center];
        swap(&A[center],&A[right]);

        j = left;

        for(i=left;i<=right-1;i++) {
            if(A[i]<=A[right]) {
                swap(&A[i],&A[j++]);
            }
        }
        swap(&A[j],&A[right]);

        quick_sort(A,left,j-1);
        quick_sort(A,j+1,right);
    }
    else
        insert_sort(A,left,right);
}