插入排序虽然不是最有效的排序方法，但它简单，并且不需要额外的存储空间。其最佳应用场景是对一个小的数据集合进行递增排序。
插入排序的描述
插入排序是最简单的排序算法。它的工作方式就像我们手动梳理一堆已作废的支票。此时我们手上有一堆未排序的支票，另外还留一块空地放置已排好序的支票。每一次，从未排序的支票中拿出一张，并根据其序号将它放入有序支票之间的正确位置。正式的表述为，插入排序每次从无序数据集中取出一个元素，扫描已排好序的数据集，并将它插入有序集合合适的位置上。虽然乍一看，插入排序需要独立为有序和无序的元素集合预留足够的存储空间，但实际上它是不需要额外的存储空间的。
插入排序是一种较为简单的算法，但是它在处理大型数据集时并不高效。因为很明显，在决定将元素插入哪个位置之前，需要将被插入元素和有序数据集中的其他元素进行比较，这会随着数据集的增大而增加额外的开销。然而插入排序的优点是，当将元素插入一个有序数据集中时，只需要对有序数据集最多进行一次遍历，而不需要完整地运行算法。这个特性使得插入排序在增量排序中非常高效。这种情况可能会发生，例如：在某酒店预订系统中。假设系统按姓名列出了所有顾客的名单，同时当有新顾客入住时系统会实时更新。在这种情况下使用插入排序，系统只需要扫视一遍数据，并将新顾客姓名插入列表中，就完成重新排序。
插入排序的接口定义
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 包含已排序的元素。
插入排序的实现与分析
插入排序从根本上来说，就是每次从未排序的数据集中取出一个元素，插入已排好序的数据集中。在以下所展示的实现中，两个数据集都存放在 data 中，data 是一块连接的存储区域。最初，data 包含 size 个无序元素。随着 issort 的运行，data 逐渐被有序数据集所取代，直到 issort 返回（此时，data 已经是一个有序数据集）。虽然实现插入排序用到连续的存储空间，但它也能用链表来实现（并不是所有的排序都可以使用链表来实现），并且效率不差。
#include <stdlib.h>
#include <string.h>
#include "sort.h"
int issort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2)) {
char *a = data;
void *key;
int i,j;
if ((key = (char *)malloc(esize)) == NULL) return -1;
for (j = 1; j < size; j++) {
memcpy(key, &a[j*esize], esize);
i = j - 1;
while (i >= 0 && compare(&a[i * esize], key) > 0) {
memcpy(&a[(i+1)*esize], &a[i*esize], esize);
i--;
}
memcpy(&a[(i+1)*esize], key, esize);
}
free(key);
return 0;
} 好了，C语言 插入排序 就分享到这里，非常感谢你的来访。如果你喜欢本站，请不要忘记收藏本站，以便下次继续访问；也可以 关注站长微博 随时获取最新动态。你的支持就是我最大的动力！
支付宝打赏 
微信打赏 如果文章对你有帮助，欢迎点击上方按钮打赏作者