1.1 算法

  • 「算法 algorithm」 是一组完成特定任务的有穷指令序列。所有算法都必须满足:

    • 输入:有零个或者多个由外部提供的输入量。
    • 输出:至少产生一个输出量。
    • 确定性:每条指令都有明确的语义,无歧义性。
    • 有限性:算法的任何一条执行路线都能在有限步之内结束。
    • 有效性:每一条指令都必须足够简单、在原则上,只用笔和纸就可以处理这一指令。
  • 「选择排序」 函数 sort(list, n) 能够将 n(n1)n(n \geq 1) 个整数正确地排序。排序后的结果存放在 list[0], ..., list[n-1] 中,且满足 list[0] \leq list[1] \leq \cdots \leq list[n-1]

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void sort(int list[], int n)
{
    int i, j, min, temp;
    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i+1; j < n; j++)
            if (list[j] < list[min])
                min = j;
        SWAP(list[i], list[min], temp);
    }
}
  • 「折半查找」(迭代实现) 假定有 nn 个不同的整数 n1n \geq 1,且它们已经排序并存放在数组 list 中。判定某个整数 searchnum 是否在数组 list 中,如果在,返回下标 i。如果不再数组 list 中,就返回 -1。 初始化时,left = 0right = n-1。令 middle = (left + right) / 2list 中间位置。
#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1)

int binsearch(int list[], int searchnum, int left, int right)
{
    int middle;
    while (left <= right) {
        middle = (left + right) / 2;
        switch (COMPARE(list[middle], searchnum)) {
        case -1: left = middle + 1; break;
        case 0: return middle;
        case 1: right = middle - 1;
        }
    }
    return -1;
}

results matching ""

    No results matching ""