Golang程序实现中数算法

当数据集排序时，中数是数据集中的中间元素。中数算法是一种强大的技术，用于找出未排序数组中的中数元素。在本文中，我们将通过递归方法和迭代方法实现中数算法。

解释

中数算法是一种确定未排序数组中中数值的高效技术。它引入了两种不同的方法：递归方法和迭代方法。

递归方法 : 引入了findMedianRecursive函数来递归地计算中数。如果数组大小较小（5个或更少的元素），它将对数组进行排序并返回中间值。对于较大的数组，该函数计算子数组中位数，选择中数中位数作为枢轴，并根据枢轴对数组进行分区。此过程递归进行，直到确定最终中数。

Unsorted array: [9, 4, 7, 2, 8, 1, 6, 5, 3]

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Output: 5

迭代法 ：该程序提供了findMedianIterative函数，它迭代地将数组分解成大小为5的子数组。它计算子数组的中位数，用这些中位数更新数组，并重复迭代直到确定最终的中位数。

算法

如果数组arr的长度小于等于5，则对数组进行排序，并将中间元素作为中位数返回。将数组arr分成大小为5的子数组，最后一个子数组可能含有较少的元素。
递归地对每个子数组应用中位数算法来找到它们的中位数。找到上一步获得的中位数的中位数，它成为枢纽元素。
根据枢纽元素对原始数组arr进行划分，将较小的元素放在左侧，较大的元素放在右侧。
如果枢纽元素在索引k处，将k与期望的中位数索引进行比较：如果k等于期望的中位数索引，则将枢纽元素作为中位数返回。如果k大于期望的中位数索引，则在左子数组上递归地应用中位数算法。
如果k小于期望的中位数索引，则在右子数组上递归地应用中位数算法。重复该过程直到找到期望的中位数。

语法

func findMedianRecursive(arr []int) int

语法定义了一个名为findMedianRecursive的函数，该函数以整数切片arr作为输入。该函数旨在返回一个表示中位数元素的整数。

func findMedianIterative(arr []int) int

语法声明一个名为findMedianIterative的函数，该函数接受一个整数切片arr作为参数。通过使用中位数算法的迭代方法，该函数迭代计算并返回所提供未排序数组的中位数。

示例

在这个示例中，我们将使用递归方法实现中位数算法，通过递归方法计算未排序数组的中位数。这里我们有一个未排序数组arr，其中元素为[9, 4, 7, 2, 8, 1, 6, 5, 3]。我们调用findMedianRecursive函数，将数组作为输入。该函数应用中位数算法的递归方法来找到中位数。计算得到的中位数是5，然后将其打印为输出。

package main

import (
    "fmt"
    "sort"
)

func findMedianRecursive(arr []int) int {
    length := len(arr)

    if length <= 5 {
        sort.Ints(arr)
        return arr[length/2]
    }

    numGroups := length / 5
    if length%5 != 0 {
        numGroups++
    }

    medians := make([]int, numGroups)

    for i := 0; i < numGroups; i++ {
        start := i * 5
        end := start + 5
        if end > length {
            end = length
        }
        subarray := arr[start:end]
        medians[i] = findMedianRecursive(subarray)
    }

    pivot := findMedianRecursive(medians)

    left := make([]int, 0)
    right := make([]int, 0)
    equal := make([]int, 0)
    for _, num := range arr {
        if num < pivot {
            left = append(left, num)
        } else if num > pivot {
            right = append(right, num)
        } else {
            equal = append(equal, num)
        }
    }

    desiredIndex := len(left)

    if desiredIndex < len(left) {
        return findMedianRecursive(left)
    } else if desiredIndex >= len(left)+len(equal) {
        return findMedianRecursive(right)
    } else {
        return pivot
    }
}

func main() {
    arr := []int{9, 4, 7, 2, 8, 1, 6, 5, 3}
    median := findMedianRecursive(arr)
    fmt.Println("Median:", median)
}

输出

Median: 7

示例

在这个例子中，我们将使用迭代方法实现golang中的中值选择算法，用于找到未排序数组的中值。这里我们有一个未排序的数组[9, 4, 7, 2, 8, 1, 6, 5, 3]。通过应用中值选择算法的迭代方法，我们计算得到中值为5。这种方法涉及将数组分为子数组，计算它们的中值，并递归地缩小范围，直到找到所需的中值为止。

package main

import (
    "fmt"
    "sort"
)

func findMedianIterative(arr []int) int {
    length := len(arr)

    for length > 5 {
        medians := make([]int, 0)
        numGroups := length / 5

        if length%5 != 0 {
            numGroups++
        }

        for i := 0; i < numGroups; i++ {
            start := i * 5
            end := start + 5
            if end > length {
                end = length
            }
            subarray := arr[start:end]
            sort.Ints(subarray)
            medians = append(medians, subarray[len(subarray)/2])
        }

        arr = medians
        length = len(arr)
    }

    sort.Ints(arr)
    return arr[length/2]
}

func main() {
    arr := []int{9, 4, 7, 2, 8, 1, 6, 5, 3}
    median := findMedianIterative(arr)
    fmt.Println("Median:", median)
}