总述：排序是指将元素集合按规定的顺序排列。通常有两种排序方法：升序排列和降序排列。例如，如整数集{6，8，9，5}进行升序排列，结果为{5，6，8，9}，对其进行降序排列结果为{9，8，6，5}。虽然排序的显著目的是排列数据以显示它，但它往往可以用来解决其他的问题，特别是作为某些成型算法的一部分。

总的来说，排序算法分为两大类：比较排序 和 线性时间排序。

某些算法只使用数据本身的存储空间来处理和输出数据（这些称为就地排序或内部排序），

而有一些则需要额外的空间来处理和输出数据（虽然可能最终结果还是会拷贝到原始内存空间中）（这些称之为外部排序）。

插入排序是最简单的排序算法。正式表述为：插入排序每次从无序数据集中取出一个元素，扫描已排好序的数据集，并将它插入有序集合的合适位置上（像我们打扑克牌摸牌时的操作）。虽然乍一看插入排序需要独立为有序和无序的元素预留足够的存储空间，但实际上它是不需要额外的存储空间的。

插入排序是一种较为简单的算法，但它在处理大型数据集时并不高效。因为在决定将元素插入哪个位置之前，需要将被插入元素和有序数据集中的其他元素进行比较，这会随着的数据集的增大而增加额外的开销。插入排序的优点是当将元素插入一个有序数据集中时，只需对有序数据集最多进行一次遍历，而不需要完整的运行算法，这个特性使得插入排序在增量排序中非常高效。

issort

int issort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2));

返回值：如果排序成功返回0，否则返回-1。

描述：利用插入排序将数组data中的元素进行排序。data中的元素个数由size决定。而每个元素的大小由esize决定。

函数指针compare会指向一个用户定义的函数来比较元素的大小。在递增排序中，如果key1>key2，函数返回1；如果key1=key2，函数返回0；如果key1<key2，函数返回-1。在背叛排序中，返回值相反。当issort返回时，data包含已排好序的元素。

复杂度：O(n²)，n为要排序的元素的个数。

 从根本上讲，插入排序就是每次从未排序的数据集中取出一个元素，插入已经排好序的数据集中。在下面的实现中，两个数据集都存放在data中，data是一块连续的存储区域。

最初，data包含size个无序元素，随着issort的运行，data逐渐被有序数据集所取代，直到issort返回，此时data已经是一个有序数据集。虽然插入排序使用的是连续的存储空间，但它仍能用链表来实现，并且效率也不差。

插入排序使用一个嵌套循环，外部循环使用标号j来控制元素，使元素从无序数据集中插入有序数据集中。由于待插入的元素总是在有序数据集的右边，因此也可以认为j是data中分隔有序元素集和无序元素集的界线。对于每个处理位置j的元素，都会使用变量i来在有序数据集中向后查找元素将要放置的位置。当向后查找数据时，每个处于位置i的元素都要向右移动一位，以保证留出足够的空间来插入新元素。一旦j到达无序数据集的尾部，data就是一个有序数据集了。

插入排序的时间复杂度关键在于它的嵌套循环部分。外部循环运行时间T(n)=n-1，乘以一段固定的时间，其中n为要排序元素的个数。考虑内部循环运行在最坏的情况，假设在插入元素之前必须从右到左遍历完所有的元素。这样的话，内部循环对于第一个元素迭代一次，对于第二个元素迭代两次，以此类推。直到外部循环终止。嵌套循环的运行时间表示为1到n-1数据的和，即运行时间T(n)=n(n+1)/2 - n，乘以一段固定时间（这是由1到n的求和公式推导出的）。为O表示法可以简化为O（n²）。当在递增排序中使用插入排序时，其时间复杂度为O（n）。插入排序不需要额外的空间，因此它只使用无序数据集本身的空间即可。

示例：插入排序的实现

/*issort.c*/
#include <stdlib.h>
#include <string.h>

#include "sort.h"

/*issort 插入排序*/
int issort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2))
{
    char *a = data;
    void *key;
    int  i,j;

    /*为key元素分配一块空间*/
    if((key =(char *)malloc(esize)) == NULL)
        return -1;

    /*将元素循环插入到已排序的数据集中*/
    for(j=1; j < size; j++)
    {
        /*取无序数据集中的第j个元素，复制到key中*/
        memcpy(key, &a[j*esize], esize);
        /*设i为j紧邻的前一个元素*/
        i = j - 1;

        /*从i开始循环查找可以插入key的正确位置*/
        /*key和第i个元素对比，如果小于第i个元素就复制i元素到i+1的位置;i递减循环对比*/
        while(i >= 0 && compare(&a[i*esize],key)>0)
        {
            memcpy(&a[(i+1)*esize],&a[i*esize],esize);
            i--;
        }
        /*将key元素的值（也就是要插入的值）复制到while循环后i+1的位置，也就是要插入的位置*/
        memcpy(&a[(i+1)*esize],key,esize);
    }
    /*释放key的空间*/
    free(key);

    return 0;
}

快速排序是一种分治算法。

广泛地认为它是解决一般问题的最佳算法。同插入排序一样，快速排序也属于比较排序的一种，而且不需要额外的存储空间。在处理中到大型数据集时，快速排序是一个比较好的选择。