排序数组-最少步骤

Question

我想知道用最少的交换来排序二进制数组的最好算法是什么？(具有数组，例如0,0,0,1,0,1,0变成0,0,0,0,0,1,1)。

我实现了一些冒泡排序，但我想知道对这些排序的优化是什么？

我的代码是用python编写的，但是任何语言都是受欢迎的，如果任何人有一个能真正改进我的程序的最少交换的解决方案，我将不胜感激！

Answer 1

如果你真的想使用交换，你可以从两端开始，把左边的1换成右边的0。

A       = [0,0,0,1,0,1,0]
left1s  = (i for i,b in enumerate(A) if b==1)
right0s = (len(A)-j for j,b in enumerate(reversed(A),1) if b==0)
swapCount = 0
for i,j in zip(left1s,right0s):
    if i>=j:break
    A[i],A[j] = A[j],A[i]
    swapCount += 1
    
print(A)                 # [0, 0, 0, 0, 0, 1, 1]
print(swapCount,"swaps") # 1 swaps

请注意，可以在不使用迭代器和zip的情况下编写相同的逻辑：

A     = [0,0,0,1,0,1,0]
swaps = 0
f,b   = 0,len(A)-1                            # forward and backward indexes
while f<b:                                    # until forward meets backward 
    if   A[f]==0: f += 1                      # skip 0s forward
    elif A[b]==1: b -= 1                      # skip 1s backward
    else: swaps,A[f],A[b] = swaps+1,A[b],A[f] # swap misplaced bits

print(A)             # [0, 0, 0, 0, 0, 1, 1]
print(swaps,"swaps") # 1 swaps

Answer 2

许多语言都有自己的实现。

javascript示例：

[0,0,0,1,0,1,0].sort();

返回

[ 0, 0, 0, 0, 0, 1, 1 ]

编辑:在javascript上添加我自己的实现。

策略是从begin和stop when found 1导航，然后从end导航到found 0以交换。

它是多种可能的实现之一。

function sortBinaryArray(binArr){
    let i = 0;
    let j = binArr.length;
    let swapCount = 0;
    while(i < j){
        if(binArr[i] === 0) {
            // found 0 on  position i. Its sorted until now.
            i++;
            continue;
        }
        // Found 1 on posittion i. Search from the end for 0 to swap
        j--;
        while(i < j){
            if (binArr[j] === 0) {
                // Found position to swap
                binArr[i] = 0;
                binArr[j] = 1;
                i++;
                swapCount++;
                break;
            }
            j--
        }
    }
    console.log('swapCount='+swapCount);
}

var myArr = [0,0,0,1,0,1,0];
sortBinaryArray(myArr);
console.log(myArr)

输出：

swapCount=1
Array(7) [ 0, 0, 0, 0, 0, 1, 1 ]

Answer 3

如果你不想使用.sort()或类似的东西，我可以想到这个解决方案：

arr = [0,0,0,1,0,1,0]
print([0] * arr.count(0) + [1] * arr.count(1))

，它最终以[0, 0, 0, 0, 0, 1, 1]的形式出现。

编辑：

l = len(arr)
z = arr.count(0)
print([0]*z + [1] * (l - z))

使用timeit.timeit似乎更快