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

60

｜

第

4

章

i--;

}

　　

ar[i+1] = value;

}

}

当

A

以基于值的形式存储时，数组会被放入具有固定元素大小为

s

字节的

n

行中。对值

进行排序，不仅需要一个比较函数，还需要能够将值从一个位置复制到另外一个位置。

例

4-2

展示了针对这种情况的

C

程序样例，它使用

memmove

函数将底层的字节高效地移

动到

A

中一段连续的条目中。

例

4-2

：基于值的插入排序

void sortValues (void *base, int n, int s,

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

int j;

void *saved = malloc (s);

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

int i=j-1;

void *value = base + j*s;

while(i>=0 && cmp (base + i *s,value) > 0){ i--; }

/*

如果已经在正确位置上，就不需要进行移动

；否则，保存待插入的值，

*

并将中间段的值作为一个大块进行移动

*

接着将该值插入正确的位置

*/

if (++i == j) continue;

memmove (saved, value, s);

memmove (base+(i+1)*s, base+i*s, ...