常见的排序算法

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

#define N 15

typedef void (*fp_sort)(int a[], int n);

// 直接插入排序
void insert_sort(int a[], int n)
{
    int i;

    for (i = 1; i < n; i++) {
        if (a[i] < a[i-1]) {
            int j = i - 1;
            int x = a[i];
            while (x < a[j] && (j >= 0)) {
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;
        }
    }
}

// 希尔排序
void shell_sort(int a[], int n)
{
    int dk = n/2;
    int i, j;
    while (dk >= 1) {

        for (i = 0; i < dk; i++) {
            for (j = i + dk; j < n; j = j + dk) {
                int k = j;
                int x = a[k];
                while ((k >= dk) && (x < a[k-dk])) {
                    a[k] = a[k-dk];
                    k = k - dk;
                }
                a[k] = x;
            }
        }

        dk = dk/2;
    }
}

// 简单选择排序
void select_sort(int a[], int n)
{
    int min, key;
    int i, j;

    for (i = 0; i < n; i++) {
        min = a[i];

        for (j = i+1; j < n; j++)
            if (min > a[j]) {
                min = a[j];
                key = j;
            }

        // a[key] = min
        a[key] = a[i];
        a[i] = min;
    }

}

// 冒泡排序
void bubble_sort(int a[], int n)
{
    int i, j, tmp;
    for (i = n-1; i > 0; i--) {
        for (j = 0; j < i; j++) {
            if (a[j] > a[j+1]) {
                tmp = a[j+1];
                a[j+1] = a[j];
                a[j] = tmp;
            }

        }
    }
}

// 快速排序
int split(int a[], int low, int high)
{
    int i = low, j = high;
    int key = a[i];

    while (i != j) {
        while (a[j] > key) {
            j--;
            if (i == j)
                goto out;
        }
        a[i] = a[j];
        a[j] = key;
        i++;
        if (i == j)
            goto out;
        while (a[i] < key) {
            i++;
            if (i == j)
                goto out;
        }
        a[j] = a[i];
        a[i] = key;
        j--;
    }

out:
    return i;
}

void quick_rec(int a[], int low, int high)
{
    if (low < high) {
        int key = split(a, low, high);
        quick_rec(a, low, key-1);
        quick_rec(a, key+1, high);
    }
}

void quick_sort(int a[], int n)
{
    quick_rec(a, 0, n-1);
}


int main()
{
    int i;
    int a[N];
    fp_sort fun_p;        //

    // 产生 1 ~ 100 的随机数
    srand(time(0));
    for (i = 0; i < N; i++)
        a[i] = rand()%100;

    for (i = 0; i < N; i++)
        printf("%d ", a[i]);

    fun_p = bubble_sort;
    printf("\nbubble_sort:\t");
    (*fun_p)(a, N);
    for (i = 0; i < N; i++)
        printf("%d ", a[i]);

    return 0;
}