在go语言中使用一个循环对数组进行排序示例代码

Go  /  管理员 发布于 2年前   598

排序是程序员之间常见的事情，也是最常用的，所以今天我们将介绍如何使用左右指针在一个循环中对数组进行排序，在获取每个值后，我们开始重置循环以重新开始从头开始寻找下一个值。

需求：

给定一个大小为 N 的数组，任务是使用单个循环对该数组进行排序。

由于所有已知的排序方法都使用超过1个循环，因此很难想象用一个循环来做同样的事情。

实际上，这样做并非不可能，但这样做可能不是最优解。

示例1： 下面的代码将对包含整数元素的数组进行排序。

package main

import (
    "fmt"
)

func sort(arr []int) {
    for current := 0; current < len(arr)-1; current++ {
        if arr[current] > arr[current+1] {
            arr[current], arr[current+1] = arr[current+1], arr[current]
            current = -1      
    }
}

func main() {
    //非反转数组
    arr := []int{1, 2, 45, 65, 32, 34}
    // output: {1,2,32,34,45,65}
    fmt.Printf("非反转数组: %d\n", arr)
    //调用上面的排序函数
    sort(arr)
    fmt.Printf("反转数组: %d\n", arr)
}

输出:

非反转数组: [1 2 45 65 32 34]
反转数组: [1 2 32 34 45 65]

示例2：下面的代码将对包含数字的字符串切片进行排序。

package main

import (
    "fmt"
)

func sort(arr []string) {
  for current := 0; current < len(arr)-1; current++ {
        if arr[current] > arr[current+1] {
            arr[current], arr[current+1] = arr[current+1], arr[current]
            current = -1
        }
    }
}

func main() {
    //非反转数组
    arr := []string{"1", "2", "45", "65", "32", "34"}
    //输出: {"1","2","32","34","45","65"}
    fmt.Printf("非反转数组: %s\n", arr)
    //调用上面的排序函数
    sort(arr)
    fmt.Printf("反转数组: %s\n", arr)
}

输出:

非反转数组: [1 2 45 65 32 34]
反转数组: [1 2 32 34 45 65]

示例3：使用与字符串 []string 切片相同的方法对字母字符串进行排序。

package main

import (
    "fmt"
    "strings"
)

func sort(arr []string) {
  for current := 0; current < len(arr)-1; current++ {
        if arr[current] > arr[current+1] {
            arr[current], arr[current+1] = arr[current+1], arr[current]
            current = -1
        }
    }
}

func main() {
  s := "PROGRAMMINGEEKSCLUB"
  
  //非反转数组
  arr := strings.Split(s,"")
  //输出: [A B C E E G G I K L M M N O P R R S U]
  fmt.Printf("非反转数组: %s\n", arr)
  //调用排序函数
  sort(arr)
  
  fmt.Printf("反转数组: %s\n",arr)
}

输出:

非反转数组: [P R O G R A M M I N G E E K S C L U B]
反转数组: [A B C E E G G I K L M M N O P R R S U]

总结：

在单个循环中排序虽然看起来更好，但并不一定是最优解。

以下是使用单循环排序之前需要考虑的几点： 

1.排序的时间复杂度在单个循环中不会改变（与多个循环排序相比）

2.单循环排序表明循环次数与算法的时间复杂度关系不大。

3.使用单个循环仅有助于缩短代码