最新消息:

C语言 插入排序

编程 5577浏览

插入排序虽然不是最有效的排序方法,但它简单,并且不需要额外的存储空间。其最佳应用场景是对一个小的数据集合进行递增排序。

插入排序的描述

插入排序是最简单的排序算法。它的工作方式就像我们手动梳理一堆已作废的支票。此时我们手上有一堆未排序的支票,另外还留一块空地放置已排好序的支票。每一次,从未排序的支票中拿出一张,并根据其序号将它放入有序支票之间的正确位置。正式的表述为,插入排序每次从无序数据集中取出一个元素,扫描已排好序的数据集,并将它插入有序集合合适的位置上。虽然乍一看,插入排序需要独立为有序和无序的元素集合预留足够的存储空间,但实际上它是不需要额外的存储空间的。

插入排序是一种较为简单的算法,但是它在处理大型数据集时并不高效。因为很明显,在决定将元素插入哪个位置之前,需要将被插入元素和有序数据集中的其他元素进行比较,这会随着数据集的增大而增加额外的开销。然而插入排序的优点是,当将元素插入一个有序数据集中时,只需要对有序数据集最多进行一次遍历,而不需要完整地运行算法。这个特性使得插入排序在增量排序中非常高效。这种情况可能会发生,例如:在某酒店预订系统中。假设系统按姓名列出了所有顾客的名单,同时当有新顾客入住时系统会实时更新。在这种情况下使用插入排序,系统只需要扫视一遍数据,并将新顾客姓名插入列表中,就完成重新排序。

插入排序的接口定义

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语言 插入排序 就分享到这里,非常感谢你的来访。如果你喜欢本站,请不要忘记收藏本站,以便下次继续访问;也可以 关注站长微博 随时获取最新动态。你的支持就是我最大的动力!

转载请注明:爱维科斯 » C语言 插入排序

支付宝打赏支付宝打赏 微信打赏微信打赏

如果文章对你有帮助,欢迎点击上方按钮打赏作者