c - 跳过值时对数组进行排序

Question

我有这个一维数组：

0, 0, 2, 0, 0, 0, 1, 7, 4, 0

我需要能够使用比冒泡排序更有效的排序算法在 C 中对这个数组进行排序，比如插入排序。我还需要在不创建新数组的情况下就地排序。但是，我需要忽略 0。

一个示例排序数组将是：

0, 0, 1, 0, 0, 0, 2, 4, 7, 0

Answer 1

您运行的算法与为插入排序运行的算法相同，只是在实际移动值时会跳过零。

所以举个例子：

0, 0, 2, 0, 0, 0, 1, 7, 4, 0

假设没有零：2, 1, 7, 4。您读取1，将其与前一个值 (2) 进行比较，然后将 2 移到 所在的位置1：

2, 1*, 7, 4 (copy 1 to register, shift the 2 since it is bigger than 1)
2, 2*, 7, 4 (write the 1 in that place)
1, 2*, 7, 4 (since there are no previous elements we are done)

在该迭代结束时，星号之前的所有内容都会被排序。

现在与零的区别在于您需要跟踪“先前”和“当前”位置（<和>）

0, 0, 2, 0, 0<, 1*> (copy 1 to register, compare to value at `<`)
0, 0, 2, 0<, 0, 1*> (Since it is zero, move the previous head further back)
0, 0, 2<, 0, 0, 1*> (Since it is zero, move the previous head further back)
0, 0, 2<, 0, 0, 2*> (Check if 1 < 2.  Since it is, write the 2 in the current head)
0, 0, 2<>, 0, 0, 2*  (move the current head)
0, 0<, 2>, 0, 0, 2*  (move the previous head back)
0<, 0, 2>, 0, 0, 2*  (move the previous head back)
0<, 0, 1>, 0, 0, 2*  (Since we hit the front, we know that we have to write the `1` in the place marked by the "current" position)

对于没有达到终点的情况，请考虑0, 1, 0, 3, 0, 2, 0. 第六次迭代的步骤是

0, 1, 0, 3, 0, 2*<>, 0
....
0, 1<, 0, 3>, 0, 3*, 0 (do the comparison and see that 1 < 2 but 2 < 3, so we want to write the 2 here and end this iteration)

0, 1<, 0, 2>, 0, 3*, 0 (now we know the elements before the * are sorted, so we can move on)

Answer 2

修改快速排序算法，以便：

• 当您决定一个项目是在枢轴的左侧还是右侧时，它会保持原样，就像 0

• 确保您没有选择 0 作为枢轴值。因此，随机 qsort 可能是更好的选择

• 如果 [recursive] 输入数组全为零，请确保返回

例如，从Rosetta 代码修改：

void quick_sort (int *a, int n) {
    if (n < 2) return;

    // don't sort all-zero sub-arrays:
    int c = 0,i;
    for (i=0; i < n; i++) { c += a[i]; }
    if (!c) return;

    // don't choose 0 as the pivot value:
    int p;
    do {
       p = a[rand()%n];
    } while (p == 0); 

    int *l = a;
    int *r = a + n - 1;

    // make sure not to move zeros:
    while (l[0] == 0 || l <= r) {
        if (*l < p) {
            l++;
            continue;
        }   
        if (r[0] == 0 || *r > p) {
            r--;
            continue; 
        }   
        int t = *l; 
        *l++ = *r; 
        *r-- = t;
    }   
    quick_sort(a, r - a + 1); 
    quick_sort(l, a + n - l); 
}

Answer 3

首先，从观察开始，当您将域限制为整数时，只有一个零。要忽略的值不需要保留在内存中。否则，如果您不是对整数进行排序，而是对按第一个坐标排序的整数对进行排序，那么将会有很多零（<0,0>, <0,1>, ... ）并且您必须以某种方式存储它们。

在这种情况下，您可以将所有非零数字移动到数组的开头，将它们移动到最初包含零的位置；在这样做的同时，记录零位于数组末尾的索引。

此时，您可以对数组的开头进行排序，然后用零按顺序将值交错，因为您将在数组的末尾有适当的索引。