c++ - 编写一个函数的两个版本，一个用于 "clarity"，一个用于 "speed"

Question

我的教授布置的作业是编写一个函数，该函数接受一个整数数组并将所有零排序到数组的末尾，同时保持非零整数的当前顺序。约束是:

不能使用 STL 或其他模板化容器。必须有两种解决方案:一种强调速度，另一种强调清晰度。

为了提高速度，我写了这个函数:

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

void sortArray(int array[], int size)
{
    int i = 0;
    int j = 1;
    int n = 0;
    for (i = j; i < size;)
    {
        if (array[i] == 0)
        {
            n++;
            i++;
        }
        else if (array[i] != 0 && j != i)
        {
            array[j++] = array[i++];
        }
        else
        {
            i++;
            n++;
        }
    }
    while (j < size)
    {
        array[j++] = 0;
    }
}

int main()
{
    //Example 1
    int array[]{20, 0, 0, 3, 14, 0, 5, 11, 0, 0};
    int size = sizeof(array) / sizeof(array[0]);
    sortArray(array, size);
    cout << "Result :\n";
    for (int i = 0; i < size; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl << "Press any key to exit...";
    cin.get();
    return 0;
}

它输出正确，但是；

• 我不知道它的实际速度是多少，谁能帮我弄清楚如何计算它？
• 我不知道如何着手编写“清晰”的函数；有什么想法吗？

Answer 1

根据我的经验，除非你有非常复杂的算法，否则速度和清晰度会同时出现:

void sortArray(int array[], int size)
{
  int item;
  int dst = 0;
  int src = 0;

  // collect all non-zero elements
  while (src < size) {
    if (item = array[src++]) {
      array[dst++] = item;
    }
  }

  // fill the rest with zeroes
  while (dst < size) { 
    array[dst++] = 0;
  }
}

速度来自好的算法。清晰来自格式化、命名变量和注释。