我有这个一维数组:
0, 0, 2, 0, 0, 0, 1, 7, 4, 0
我需要能够使用比冒泡排序更有效的排序算法在 C 中对这个数组进行排序,比如插入排序。我还需要在不创建新数组的情况下就地排序。但是,我需要忽略 0。
一个示例排序数组将是:
0, 0, 1, 0, 0, 0, 2, 4, 7, 0
您运行的算法与为插入排序运行的算法相同,只是在实际移动值时会跳过零。
所以举个例子:
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)
修改快速排序算法,以便:
当您决定一个项目是在枢轴的左侧还是右侧时,它会保持原样,就像 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);
}
首先,从观察开始,当您将域限制为整数时,只有一个零。要忽略的值不需要保留在内存中。否则,如果您不是对整数进行排序,而是对按第一个坐标排序的整数对进行排序,那么将会有很多零(<0,0>
, <0,1>
, ... )并且您必须以某种方式存储它们。
在这种情况下,您可以将所有非零数字移动到数组的开头,将它们移动到最初包含零的位置;在这样做的同时,记录零位于数组末尾的索引。
此时,您可以对数组的开头进行排序,然后用零按顺序将值交错,因为您将在数组的末尾有适当的索引。