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)