插入排序

    插入排序：
    每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

   

#include <stdio.h>

typedef int (*CompareFunc)(void *a, void *b);

int Func(int *a, int *b);

void InsertionSort(int *x, int len, CompareFunc f);


int
main(void)
{
    int a[] = {2, 3, 4, 9, 8, 5, 1,6, 0, 7, 8};

    int i, num;
    i = 0;
    num = sizeof(a) / sizeof(int);

    printf("Before Insertion Sort:\n");
    for(i = 0; i < num; i++) {
        printf("%d,", a[i]);
    }
    printf("\n\n");

    InsertionSort(a, num, (CompareFunc)Func);

    printf("After Insertion Sort:\n");
    for(i = 0; i < num; i++) {
        printf("%d,", a[i]);
    }
    printf("\n");

    return 0;
}

int Func(int *a, int *b)
{
    if(*a > *b) {
        return 1;
    } else if(*a == *b) {
        return 0;
    } else {
        return -1;
    }
}


void InsertionSort(int *x, int len, CompareFunc f)
{
    if(len > 1) {
        int i, j, key;

        for(j = 1; j < len; j++) {
            key = *(x+j);
            i = j - 1;

            while((i >= 0) && (f((x+i), &key)) == 1) {
                *(x+i+1) = *(x+i);
                --i;
            }

            *(x+i+1) = key;
        }
    }

    return ;
}

/*
 * Initialization: We start by showing that the loop invariant holds before the
 *         first loop iteration, when j = 2. The subarray a[1...j-1], therefor
 *        consists of just the single element a[1], which is in fact the
 *        original element in a[1], Moreover, this subarray is sorted, which
 *        shows that the loop invariant holds prior to the first iteration of
 *        the loop
 * Maintenance: Next we tackle the second property: showing that each iteration maintains
 *    the loop invariant. Informally, the body of the outer for loop works by moving
 *    a[j-1],a[j-2],a[j-3],and so on by one position to the right until the proper
 *     positon for a[j] is found, at which point the value of a[j] is inserted.
 *    A more formal treatment of second property would require us to stat and show a
 *    loop invariant for the "inner" while loop. At this point, however, we prefer not
 *     to get bogged down in such formalism, and so we reply on our informal analysis
 *    to show that the second property holds for the outer loop.
 * Termination: Finally, we examine what happens when loop terminates. For insertion sort,
 *    the outer for loop ends when j exceeds n, when j = n + 1. Substituting n+1 for j
 *    in the wording fo loop invariant, we have that the subarray a[1..n], consisits
 *     of the elements of the elements original in a[1...n], but in sorted order. But
 *    the subarray a[1...n] is the entire array. Hence, the entire array is sorted,
 *    which means that the algorithm is correct.
 */

注：平均时间复杂度为O（n2），稳定。