编写Golang程序以线性时间对二进制数组进行排序

2024-04-11 17:34:03 491

例子

输入数组=[1，0，1，0，1，0，0，1]=>[0，0，0，0，1，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]

方法2

现在，让我们检查第二种方法。

解决这个问题的方法

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

步骤2： 声明枢轴元素及其索引j。

步骤3：迭代给定的数组。如果元素小于支点，则交换并增加支点的索引。

步骤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]

编写Golang程序以线性时间对二进制数组进行排序

例子

解决这个问题的方法

程序

解决这个问题的方法

程序

热门推荐

随机推荐