Determine the complexity of sorting a binary array
I agree with your analysis that both algorithms have O(n) time complexity (where n is the number of elements in the array). An important factor to note is that both algorithms also use constant extra space.
However, you can include other metrics in your analysis too. Anything that may be expensive  to do can be considered. Two common metrics are the number of comparisons and the number of exchanges.
The number of comparisons tells you how often an element of the array is accessed and then compared. Memory access can be quite expensive, depending on how far up the memory hierarchy (registers, cache levels, RAM, local storage, external storage) you need to traverse before getting the value.
The number of exchanges tells you how many times elements are swapped. This can be expensive any time writing to memory is. For instance, writing to shared memory in a multi-process program.

Taking the above into account, ignoring the error checking case, and also ignoring any potential optimisations from the compiler, I would argue the second algorithm is better. For the first implementation I count 2 comparisons per element, and 1 exchange per element. For the second, I count 1 comparison per element, and then 1 assignment per element (an assignment of a constant is cheaper than exchanging two elements).
You can replace the exchange with assignments in the first implementation. Since the array only contains the values 0 and 1, and you've checked that the two elements are different.
if (j &gt; i &amp;&amp; value[i] &gt; value[j] )
{
    value[j] = 1;
    value[i] = 0;
    j--;
    i++;
}

Without profiling the code, I don't think it is possible to tell if the extra number of comparisons in the first implementation are more costly than the overhead of the second pass through the array in the second implementation. I would not be surprised if the numerous bounds checks in the first piece of code (i &lt; j) are the actually largest performance hit.

Third implementation
Based on the comment that the first implementation is still faster, here is another solution that tries to improve upon the second. I'm hoping that by writing it with well known operations, the compiler can work some magic.
public static int[] SortOnesZerosAlternate(int[] values)
{
    int countOfZeros = values.Length - values.sum();
    // Maybe replace this with values.Clear?
    for (int i = 0; i &lt; countOfZeros; i++)
    {
        values[i] = 0;
    }

    for (int i = countOfZeros; i &lt; values.Length; i++)
    {
        values[i] = 1;
    }

    return values;
}