常用排序算法集合

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define NUM    100
#define LEN    100

void initArray(int *A, int len);
void printArray(int *A, int len);
void mySwap(int *a, int *b);
void bubbleSort(int *A, int len);
void insertSort(int *A, int len);
void selectSort(int *A, int len);
void quickSort(int *A, int begin, int end);
void mergeSort(int *A, int begin, int end);
void heapSort(int *A, int len);
void shellSort(int *A, int len);

int
main(void)
{
    int a[LEN] = {0};

    initArray(a, LEN);
    printArray(a, LEN);

    bubbleSort(a, LEN);
    printArray(a, LEN);

    insertSort(a, LEN);
    printArray(a, LEN);

    selectSort(a, LEN);
    printArray(a, LEN);

    printf("\nQuick sort:");
    quickSort(a, 0, LEN-1);
    printArray(a, LEN);

    printf("\nMerge sort:");
    mergeSort(a, 0, LEN-1);
    printArray(a, LEN);

    heapSort(a, LEN);
    printArray(a, LEN);

    shellSort(a, LEN);
    printArray(a, LEN);

    return 0;
}

void
initArray(int *A, int len)
{
    printf("\nInit array:");
    int i;
    srand((unsigned int )time(0));
    for ( i = 0; i < len; i++)
        *(A+i) = rand() % NUM ;
}

void
printArray(int *A, int len)
{
    int i;
    printf("\nBegin:\n");

    for (i = 0; i < len; i++) {
        printf("%5d, ", *(A+i));
        if ((i+1)%20 == 0)
            printf("\n");
    }

    printf("\nEnd:\n");
}

void
mySwap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void
bubbleSort(int *A, int len)
{
    printf("\nBubble sort:");

    if (len <= 1)
        return ;

    int i, j;
    for (i = 0; i < len; i++) {
        for (j = len-1; j > i; j--)
            if (*(A+j) < *(A+j-1))
                mySwap(A+j, A+j-1);
    }
}

void
insertSort(int *A, int len)
{
    printf("\nInsert sort:");

    if (len <= 1)
        return ;

    int i, j;
    for (j = 1; j < len; j++) {
        int tmp = *(A+j);
        i = j - 1;
        while (i >= 0 && *(A+i) >= tmp) {
            *(A+i+1) = *(A+i);
            --i;
        }
        *(A+i+1) = tmp;
    }
}

void
selectSort(int *A, int len)
{
    printf("\nSelect sort:");

    if (len <= 1)
        return ;

    int i, j, min;
    for (i = 0; i < len-1; i++) {
        min = i;
        for (j = i+1; j < len; j++) {
            if (*(A+j) < *(A+i))
                min = j;
        }
        if (min != i)
            mySwap(A+i, A+min);
    }
}

static int
paration(int *A, int begin, int end)
{
    int base;
    int i;

    base = *(A+begin);
    i = begin + 1;
    while (i <= end) {
        if (*(A+i) <= base) {
            *(A+i-1) = *(A+i);
            ++i;
        } else {
            mySwap(A+i, A+end);
            --end;
        }
    }
    *(A+i-1) = base;

    return (i-1);
}

void
quickSort(int *A, int begin, int end)
{
    int mid;
    if (begin < end) {
        mid = paration(A, begin, end);
        quickSort(A, begin, mid-1);
        quickSort(A, mid+1, end);
    }
}

static void
merge(int *A, int begin, int mid, int end)
{
    int n1, n2;
    n1 = mid - begin + 1 + 1;
    n2 = end - mid + 1;
    int L[n1], R[n2];
    int i, j, k;

    for (i = 0; i < n1-1; i++)
        L[i] = *(A+begin+i);
    for (j = 0; j < n2-1; j++)
        R[j] = *(A+mid+1+j);

    L[i] = INT_MAX;
    R[j] = INT_MAX;
    i = 0;
    j = 0;

    for (k = begin; k <= end; k++) {
        if (L[i] <= R[j]) {
            *(A+k) = L[i];
            ++i;
        } else {
            *(A+k) = R[j];
            ++j;
        }
    }
}

void
mergeSort(int *A, int begin, int end)
{
    int mid;
    if (begin < end) {
        mid = (begin + end)/2;
        mergeSort(A, begin, mid);
        mergeSort(A, mid+1, end);
        merge(A, begin, mid, end);
    }
}

static void
maxHeapVerify(int *A, int i, int len)
{
    int lf = 2*i;
    int rt = 2*i+1;
    int lg;

    if (lf < len && *(A+lf) > *(A+i))
        lg = lf;
    else
        lg = i;

    if (rt < len && *(A+rt) > *(A+lg))
        lg = rt;

    if (lg != i) {
        mySwap(A+lg, A+i);
        maxHeapVerify(A, lg, len);
    }
}

static void
buildMaxHeap(int *A, int len)
{
    int i;
    for (i = len-1; i >= 0; i--)
        maxHeapVerify(A, i, len);
}

void
heapSort(int *A, int len)
{
    printf("\nHeap sort:");

    if (len <= 1)
        return ;

    int i;
    buildMaxHeap(A, len);
    for (i = len-1; i > 0; i--) {
        mySwap(A+i, A);
        --len;
        maxHeapVerify(A, 0, len);
    }
}

static void
shellPass(int *A, int step, int len)
{
    int i, j, k;
    int tmp;

    for (i = 0; i < step; i++) {
        for (j = (i+1)*step; j < len; j+= step) {
            tmp = *(A+j);
            k = j - step;
            while (k >= i && *(A+k) > tmp) {
                *(A+k+step) = *(A+k);
                k -= step;
            }
            *(A+k+step) = tmp;
        }
    }
}

void
shellSort(int *A, int len)
{
    printf("\nShell sort:");

    if (len <= 1)
        return ;

    int step = len;
    do {
        step = step / 3 + 1;
        shellPass(A, step, len);
    } while (step > 1);
}