小编Dav*_* R.的帖子

我正在C中实现QuickSort.

这是我的交换程序:

void swap(int *x, int *y)
{
    *x += (*y);
    *y = (*x) - (*y);
    *x = (*x) - (*y);
}

这是我的分区程序:

int partition(int a[], int sx, int dx)
{
    int indice_pivot = (rand()%(dx-sx+1))+sx;
    int i = sx-1, j;

    swap(&a[indice_pivot],&a[dx]);


    for(j=sx;j<dx;j++)
    {
        if(a[j] <= a[dx])
        {
            i++;
            swap(&a[j],&a[i]);
        }
    }

    i++;
    swap(&a[i],&a[dx]);

    return i;
}

问题是,当交换两个变量时,它们神奇地(？)变为0.我做了一些调试,一切似乎在交换过程中工作正常.但是数组在某些分区的末尾包含零(并非所有分区).奇怪的是,如果我用替换交换过程

void swap(int *x, int *y)
{
    int temp = *y;
    *y = *x;
    *x = temp;
}

一切正常.为什么？

我有一个带有一些整数字段的结构,比如

struct s {
    int a;
    int b;
    int c;
    int max;
};
struct s mystruct = {0, 0, 0, 0}; // Global var

然后,我有N个线程,有时不得不做这样的事情++还是--在前三场,有时还得看他们,然后更新的max领域.我必须在这里使用互斥吗？如果是,是仅在阅读/更新时才需要max或总是需要？为什么？如果我只是增加或减少前三个字段,那么一个线程在另一个之前运行是否重要？

我有一个 n 个整数的数组，它只能假设log n 个可能的值（和任何值）。例如，在 中S = [349,12,12,283,349,283,283,12]，只有 3 个不同的数字(log 8 = 3)。

我必须在短时间内对这个数组进行排序O(nlogn)。我应该使用哪种算法？也许基数排序和计数排序？它的分析呢？