在go语言中实现替代排序算法示例代码

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

在go语言中有个sort包可以对任何数据类型的数组进行排序，想了解更多用法自行去手册查阅

https://pkg.go.dev/sort

需求

给定一个整数数组，以这样的方式打印数组：

第一个元素是第一个最大数，第二个元素是第一个最小数，依此类推。

示例

输入：
arr[] = {6, 3, 1, 2, 4, 5, 7}
输出：
7 1 6 2 5 3 4

输入：
arr[] = {1, 6, 9, 4, 3, 7, 8, 2}
输出：
9 1 8 2 7 3 6 4

思路

一个简单的解决方案1

是首先打印最大元素，然后是最小值，然后是第二个最大值，依此类推。

这种方法的时间复杂度是 O(n 2 )。

一个有效的解决方案2

包括以下步骤。

使用 O(n Log n) 算法对输入数组进行排序。 

我们在有序数组中维护两个指针，一个从开始，一个从结束。我们交替打印由两个指针指向的元素并将它们彼此移动。

替换排序算法示例代码：

/* 
替代性排序问题
例子
输入 : arr[] = {6, 3, 1, 2, 4, 5, 7}。
输出：7 1 6 2 5 3 4
输入：arr[] = {1, 6, 9, 4, 3, 7, 8, 2}。
输出：9 1 8 2 7 3 6 4
*/

package main

import (
    "fmt"
     "sort"
)

func alternativeSorting(arr []int) {
  sort.Ints(arr)
  fmt.Println("排序的数组",arr)
  
  left := 0
  right := len(arr)-1
  for left < right {
     fmt.Printf("%d %d ",arr[right],arr[left])
     left++
     right--
  }
  
  if len(arr) % 2 != 0 {
    fmt.Printf("%d ",arr[left])
  }
}

func main() {
  arr := []int{12, 1, 6, 4, 7, 10}
  fmt.Println("之前",arr)
  
  alternativeSorting(arr)

}

输出：

在[1 12 4 6 7 10]之前
排序的数组[1 4 6 7 10 12]
12 1 10 4 7 6