面试问题:C程序在O(n)中对二进制数组进行排序

Question

我已经提出了以下程序来做它,但它似乎不起作用并进入无限循环.它的工作方式类似于quicksort.

int main()
{
 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int *front, *last;

 front = arr;
 last = arr + N;
 while(front <= last)
 {
  while( (front < last) && (*front == 0) )
   front++;

  while( (front < last) && (*last == 1) )
   last--;

  if( front < last)
  {
   int temp = *front;
   *front = *last;
   *last = temp;
   front ++;
   last--;
  }
 }
 for(int i=0;i<N;i++)
  printf("%d ",arr[i]);

 return 0;
}

Answer 1

你的意思是阵列只有0s和1s吗？

求和所有N个元素,然后覆盖数组:)

int main() {
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
    int N = sizeof arr / sizeof *arr; /* 18 */
    int sum = 0;
    int ndx;
    for (ndx=0; ndx<N; ndx++) sum += arr[ndx];
    for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0;
    for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1;
}

Answer 2

我在程序中看到至少两个问题:

问题1:

last = arr + N;

是不正确的.它应该是:

last = arr + N - 1;

因为

(arr + 0) points to 0th ele
(arr + 1) points to 1st ele
...
(arr + N -1) points to (N-1)th ele..which is the last element.

问题2:
接下来你的while循环:

while(front <= last)

是不正确的,应该是:

while(front < last)

在你的情况下,当前面和最后一个变得相等时,你的循环继续,但此时前面和后面都没有被修改,导致无限循环.

当前面和后面变得相等时,没有必要继续,你的阵列将被排序.

Answer 3

您的算法的基本思想很好,并且可以简化实现:

int a[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};

int *begin = a;
int *end = begin + 17;

while (begin < end) {
   if (*begin == 0)
      begin++;
   else if (*end == 1)
      end--;
   else {
      *begin = 0;
      *end = 1;
   }
}

注意,这(begin < end)是一个更强的循环终止条件,并且在一次动作(移动指针或交换值)的每次迭代中都采用,简化了代码并使得更容易理解循环将真正终止.