Golang程序 在线性时间内对二进制数组进行排序

我们有两种方法可以解决这个问题。让我们来看看第一种方法。

方法一

例子

• 输入数组 = [1, 0, 1, 0, 1, 0, 0, 1] => [0, 0, 0, 0, 1, 1, 1)

解决这个问题的方法

第1步： 定义一个接受数组的方法。

第2步： 计算0的数量。

第3步：存储0直到计数变为0，并在其余的索引处存储1。

第4步：最后，返回数组。

程序

package main
import "fmt"
func binarySort(arr []int) []int{
   count := 0
   for i:=0; i<len(arr); i++{
      if arr[i]==0{
         count++
      }
   }
   for j:=0; j<len(arr); j++{
      if j<count{
         arr[j] = 0
      } else {
         arr[j] = 1
      }
   }
   return arr
}

func main(){
   fmt.Println(binarySort([]int{1, 0, 1, 0, 1, 0, 0, 1}))
   fmt.Println(binarySort([]int{1, 1, 1, 1, 1, 1, 1, 1}))
   fmt.Println(binarySort([]int{0, 0, 0, 0, 0, 0, 0, 0}))
}

输出

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

方法二

现在，让我们来看看第二种方法。

解决这个问题的方法

• 第1步： 定义一个接受数组的方法。
• 第2步： 声明支点元素和它的索引 j 。
• 第3步： 对给定的数组进行迭代。如果元素小于pivot，那么交换并增加pivot的索引。
• 第4步： 最后，返回数组。

程序

package main
import "fmt"
func binarySort(arr []int) []int{
   pivot := 1
   index := 0
   for i:=0; i<len(arr); i++ {
      if arr[i]<pivot{
         arr[i], arr[index] = arr[index], arr[i]
         index++
      }
   }
   return arr
}

func main(){
   fmt.Println(binarySort([]int{1, 0, 1, 0, 1, 0, 0, 1}))
   fmt.Println(binarySort([]int{1, 1, 1, 1, 1, 1, 1, 1}))
   fmt.Println(binarySort([]int{0, 0, 0, 0, 0, 0, 0, 0}))
}

输出

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