我想知道什么是最好的演算法來對二進制陣列進行最少的交換排序？(例如，將陣列 [0,0,0,1,0,1,0] 變成 [0,0,0,0,1,1]）。
我實作了一些泡沫排序，但不知道這些排序的優化情況如何？
uj5u.com熱心網友回復：
ar = [0,0, 0,1,0,1, 0]
ar.sort()
print(ar)
uj5u.com熱心網友回復：
如果你不想使用.sort()或類似的東西，我可以想到這個解決方案：
arr = [0,0, 0,1,0,1, 0]
print([0] * arr.count(0) [1] * arr.count(1)
結果是[0, 0, 0, 0, 1, 1]
編輯：
l = len（arr）。
z = arr.count(0)
print([0]*z [1] *（l - z）)
似乎用timeit.timeit
uj5u.com熱心網友回復：
許多語言都有自己的實作。
以javascript為例：
[0,0,0。 1,0,1,0】。] sort()。
回傳
[ 0, 0, 0。0, 0, 1, 1 ]
編輯：添加我自己在javascript上的實作。
該策略是從開始導航，發現1時停止，然后從結束導航到發現0時交換。
這是多種可能的實作之一。
function sortBinaryArray(binArr){
讓i = 0;
讓j = binArr.length;
let swapCount = 0;
while（i < j）{
if(binArr[i] === 0) {
//在位置i上發現了0，其排序直到現在。
i ;
continue。
}
1在第i個位置找到了1，從最后尋找 0到交換。
j--;
while（i < j）{
if (binArr[j] === 0) {
//找到要交換的位置
binArr[i] = 0;
binArr[j] = 1;
swapCount ;
break;
}
j--
}
}
console.log('swapCount='/span> swapCount)。
}
var myArr = [0,0,0, 1,0,1,0】。]
sortBinaryArray(myArr);
console.log(myArr)
輸出：
swapCount=1
陣列(7) [ 0, 0, 0, 0, 0, 1, 1 ]
uj5u.com熱心網友回復：
你不需要對二進制陣列進行排序，尤其是使用python的小整數互換功能。
1的計數是由
給出的ones = sum(lst)
零的計數是長度分鐘，即：
zeros = len（lst）- ones
你可以用
構建正確的串列[0] * zeros [1] * ones
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/310782.html
標籤：
下一篇：PHP-按數字順序排序