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

62

｜

第

4

章

例

4-3

：选择排序的

C

语言实现

static int selectMax (void **ar, int left, int right,

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

int maxPos = left;

int i = left;

while (++i <= right) {

if (cmp(ar[i], ar[maxPos])> 0) {

maxPos = i;

}

}

return maxPos;

}

void sortPointers (void **ar, int n,

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

/*

反复选择

ar[0,i]

中的最大值，并交换到合适的位置

*/

int i;

for (i = n-1; i >=1; i--) {

int maxPos = selectMax (ar, 0, i, cmp);

if (maxPos != i) {

void *tmp = ar[i];

ar[i] = ar[maxPos];

ar[maxPos] = tmp;

}

}

}

选择排序

是本章描述的所有排序算法中最慢的，即使在最好情况下（如数组已经有序），

它也需要平方级时间。并且，它只是在不断重复进行着几乎相同的工作，而没有从一次 ...