算法技术手册（原书第2 版）

排序算法

｜

59

排序算法

4.2.2 使用环境

插入排序

适用于待排序元素数量较少或者初始数据已经“几乎有序”的情况。至于一个

数组是否“足够小”得能够使用插入排序，这要根据具体的机器和编程语言而定。事实上，

待比较元素的类型也有可能非常重要。

图 4-3：插入排序在小数据集上的执行过程

4.2.3 解决方案

当数据信息以基于指针的形式存储时，我们可以通过传入比较函数

cmp

来对元素进行比

较，例

4-1

中的

C

程序实现了对数组

ar

进行排序。

例

4-1

：基于指针的插入排序

void sortPointers (void **ar, int n,

int(*cmp)(const void *,const void *)) {

int j;

for (j = 1; j < n; j++) {

　　

int i = j-1;

　　

void *value = ar[j];

　　

while (i >= 0 && cmp(ar[i], value) > 0) {

ar[i+1] = ar[i];