Golang 对0、1和2的数组进行排序

在Golang中，和其他编程语言一样，我们可以编写逻辑来对具有0、1和2作为元素的数组进行排序。排序意味着将数据按照升序或降序分配。这是一个在面试中经常被问到的关于数组的著名问题。我们可以通过两种方法来实现这个目标。

例如，我们有一个数组2、1、0、0、1、2，排序后的数组将变为0、0、1、1、2、2。

方法1

在这个示例中，我们将使用预先构建的排序函数来按照升序对数组进行排序。这种方法的时间复杂度是O(nlogn)，因为它将使用归并排序在后台进行排序。

步骤

步骤1： 使用import关键字在顶部导入所需的包。

步骤2： 然后，首先运行主函数。

• 首先，我们声明并初始化数组。

• 然后，我们使用预先构建的排序函数对数组进行排序。

• 最后，我们打印排序后的数组。

示例

这是使用预先构建的排序函数在Golang中对0、1和2的数组进行排序的代码。

package main

import (
    "fmt"
    "sort"
)

// function to print the array with array and
// size of the array as argument
func printArray(array [5]int, size int) {
    for i := 0; i < 5; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func main() {
    // shorthand array declaration
    array := [5]int{2, 1, 1, 2, 0}

    fmt.Println("Golang program to sort 1s, 2s, and 3s in O(NLog(N)) time complexity.")

    fmt.Println("Printing array before sorting.")
    // calling function to print the array
    printArray(array, 5)

    // calling sortArray function to sort the array by
    // passing array as reference
    sort.Ints(array[:])

    fmt.Println("Printing array after sorting.")
    // calling function to print the array
    printArray(array, 5)
}

输出

Golang program to sort 1s, 2s, and 3s in O(NLog(N)) time complexity.
Printing array before sorting.
2 1 1 2 0 
Printing array after sorting.
0 1 1 2 2

方法2

在这个示例中，我们将使用双指针算法按升序对数组进行排序。这种方法的时间复杂度是O(N)，其中N是数组的大小。

步骤

步骤1： 使用import关键字在顶部导入所需的包。

步骤2： 然后主函数将首先运行。

• 首先，我们声明并初始化数组。

• 然后我们调用sortArray()函数，其中我们传递一个数组作为参数，并且函数返回排序后的数组。

• 最后，我们打印排序后的数组。

步骤3：

• 在sortArray()函数中，我们首先声明并初始化0、1和2的迭代器。

• 然后我们运行一个循环，其中每个迭代器与0、1和2进行比较，并根据需要使用swap函数进行交换。

示例

这是使用双指针算法按升序对数组中的0、1和2进行排序的代码示例。

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array [5]int, size int) {
    for i := 0; i < 5; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

// function to swap two int values
func swap(a *int, b *int) {
    temp := *a
    *a = *b
    *b = temp
}

// function to sort the array that has values 0s, 1s and 2s
func sortArray(array *[5]int, size int) {
    // declaring variables using the var keyword
    var i, j, k int

    //Initializing the variables
    i = 0
    j = 0
    k = size - 1

    // running loop till i is less than j
    for j <= k {
        if array[j] == 0 {
            // if the value at index jth is 0 replace with ith index
            swap(&array[i], &array[j])
            i++
            j++
        } else if array[j] == 2 {
            // If the value at index jth is 0 replace with ith index
            swap(&array[k], &array[j])
            k--
        } else if array[j] == 1 {
            // increasing jth iterator if the value is 1 at the current index
            j++
        }
    }
}

func main() {
    // shorthand array declaration
    array := [5]int{2, 1, 1, 2, 0}

    fmt.Println("Golang program to sort 1s, 2s, and 3s in O(N) time complexity.")

    fmt.Println("Printing array before sorting.")
    // calling function to print the array
    printArray(array, 5)

    // calling sortArray function to sort the array by
    // passing array as reference
    sortArray(&array, 5)

    fmt.Println("Printing array after sorting.")
    // calling function to print the array
    printArray(array, 5)
}

输出

Golang program to sort 1s, 2s, and 3s in O(N) time complexity.
Printing array before sorting.
2 1 1 2 0 
Printing array after sorting.
0 1 1 2 2

结论

这是排序由0、1和2组成的数组的两种方法。在编程中，当我们使用算法解决问题时，时间复杂性得到了降低，第二种方法在时间上更有效，只需要O(N)的时间，使用了两个指针算法。要了解更多关于Golang的内容，您可以探索这些教程。