Go语言程序：排序包含0、1和2的数组

在Go语言中，与其他编程语言一样，我们可以编写逻辑来对包含0、1和2作为元素的数组进行排序。排序意味着按升序或降序排列数据。这是面试中关于数组的常见问题之一。我们可以采用两种方法来实现这一点，我们将逐一探讨。

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

方法一

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

算法

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

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

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

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

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

示例

这是使用预构建排序函数在Go语言中对包含0、1和2作为元素的数组进行排序的代码。

Open Compiler
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

方法二

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

算法

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

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

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

  • 然后我们调用`sortArray()`函数，并将数组作为参数传递，该函数返回排序后的数组。

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

步骤3

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

  • 然后我们运行一个for循环，其中每个迭代器都与0、1和2进行比较，并相应地使用`swap`函数进行交换。

示例

这是使用双指针算法在Go语言中对包含0、1和2作为元素的数组进行升序排序的代码。

Open Compiler
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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

这是对包含0、1和2作为元素的数组进行排序的两种方法。在编程中，无论何时使用算法解决任何问题陈述，时间复杂度都会降低，这在第二种方法中得到了体现，它在时间效率上优于第一种方法，因为它仅使用双指针算法花费O(N)的时间。要了解更多关于Go语言的信息，您可以浏览这些教程。

更新于：2023年7月10日

80 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告