弄清楚三元运算符级联的功能？

Question

我正在尝试实现 Merge Sort 的简单（且易于理解）版本，经过一些研究 I found the following C version:

#include <stdio.h>
#include <stdlib.h>

void merge (int *a, int n, int m) 
{
    //...
    int i, j, k;

    // allocate memory on the heap for the temp array
    int *x = malloc(n * sizeof (int));

    // what is happening here (sorting)
    for (i = 0, j = m, k = 0; k < n; k++) 
    {
        x[k] = j == n      ? a[i++]
             : i == m      ? a[j++]
             : a[j] < a[i] ? a[j++]
             :               a[i++];
    }

    // deep copy of temp elements to initial array
    for (i = 0; i < n; i++) 
    {
        a[i] = x[i];
    }

    // free temp array
    free(x);
}

//---------------------------------------------------------------------
void merge_sort (int *a, int n) 
{
    // base case (subarray with 2 elements)
    if (n < 2)
    {
        return;
    }

    // find index of middle element
    int m = n / 2;

    // divide into two
    merge_sort(a, m);
    merge_sort(a + m, n - m);

    // sort and merge
    merge(a, n, m);
}

//=====================================================================
int main ()
{
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    int n = sizeof a / sizeof a[0];
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    }

    merge_sort(a, n);

    for (i = 0; i < n; i++)
    {
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    }

    return 0;
}

有人可以帮我描述和评论（可能将其分解为 if 语句）函数 merge 中 for 循环中的长级联三元运算符吗？

_{除非另有说明，否则内容根据 GNU 自由文档许可证 1.2 提供。}

Answer 1

你没听懂的与归并排序无关：

    x[k] = j == n      ? a[i++]
         : i == m      ? a[j++]
         : a[j] < a[i] ? a[j++]
         :               a[i++];

刚刚由更喜欢 sexy/funny 查看代码而不是就绪性的人编写。但真正的代码有行。这could/should表示为：

if(j == n)
{
    x[k] = a[i++];
}
else if(i == m)
{
    x[k] = a[j++];
}
else if(a[j] < a[i])
{
    x[k] = a[j++];
}
else
{
    x[k] = a[i++];
}

如果您需要了解合并排序的工作原理，请参阅 Merge Sort on wikipedia:

我修改了一些代码以进行老式调试，并使用了 GIF 的数字以便您可以关注，但首先是输出：

Pass 1. n:2, m:1
inserting 5
inserting 6

Pass 2. n:2, m:1
inserting 1
inserting 3

Pass 3. n:4, m:2
inserting 1
inserting 3
inserting 5
inserting 6

Pass 4. n:2, m:1
inserting 7
inserting 8

Pass 5. n:2, m:1
inserting 2
inserting 4

Pass 6. n:4, m:2
inserting 2
inserting 4
inserting 7
inserting 8

Pass 7. n:8, m:4
inserting 1
inserting 2
inserting 3
inserting 4
inserting 5
inserting 6
inserting 7
inserting 8

现在，代码：

#include <stdio.h>
#include <stdlib.h>

static int pass = 0;
void merge (int *a, int n, int m) {
    int i, j, k;
    int *x = malloc(n * sizeof (int));

    printf("\nPass %d. n:%d, m:%d\n", ++pass, n, m);

    for (i = 0, j = m, k = 0; k < n; k++) {
        if(j == n)
        {
            printf("inserting %d\n", a[i]);
            x[k] = a[i++];
        }
        else if(i == m)
        {
            printf("inserting %d\n", a[j]);
            x[k] = a[j++];
        }
        else if(a[j] < a[i])
        {
            printf("inserting %d\n", a[j]);
            x[k] = a[j++];
        }
        else
        {
            printf("inserting %d\n", a[i]);
            x[k] = a[i++];
        }
    }
    for (i = 0; i < n; i++) {
        a[i] = x[i];
    }
    free(x);
}

void merge_sort (int *a, int n) {
    if (n < 2)
        return;
    int m = n / 2;
    merge_sort(a, m);
    merge_sort(a + m, n - m);
    merge(a, n, m);
}

int main () {
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof a / sizeof a[0];
    int i;
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    merge_sort(a, n);
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    return 0;
}

弄清楚三元运算符级联的功能？

Figuring out the function of cascade of ternary operators?

c

algorithm

sorting

ternary-operator