go

golang归并排序

介绍

归并排序(Merge Sort)是一种经典的排序算法,它采用分治(Divide and Conquer)的策略来进行排序。它将待排序的数组逐步地划分为较小的子数组,然后对这些子数组进行排序,最后将排序好的子数组合并成一个有序的数组。

归并排序的基本思想如下:

  • 分解:将待排序的数组递归地分解为较小的子数组,直到每个子数组只包含一个元素或为空。
  • 解决:对每个子数组进行排序。当子数组的长度为 1 时,认为它是已排序的。
  • 合并:将两个有序的子数组合并成一个有序的数组。重复这个过程,直到最终合并成一个完整的有序数组。

归并排序的关键步骤是合并操作。合并操作的基本过程如下:

  1. 创建一个临时数组或列表,用于存储合并后的结果。
  2. 初始化两个指针,分别指向两个有序子数组(左子数组和右子数组)的起始位置。
  3. 比较两个指针所指向的元素,将较小的元素放入临时数组,并将相应的指针向后移动一位。
  4. 重复上述步骤,直到其中一个子数组的元素全部被合并。
  5. 将剩余子数组的所有元素直接追加到临时数组的末尾。
  6. 将临时数组中的元素复制回原始数组的相应位置,完成合并。

归并排序是一种稳定的排序算法,具有较好的时间复杂度,适用于大规模数据的排序。但需要注意的是,归并排序在实际应用中可能需要较大的额外空间,因此在空间受限的情况下需要考虑其他排序算法。

代码示例

package main

import "fmt"

func mergeSorted(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    //fmt.Println("mid: ", mid)
    left := mergeSorted(arr[:mid])
    //fmt.Println("left: ", left)
    right := mergeSorted(arr[mid:])
    //fmt.Println("right: ", right)
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    //fmt.Println("1: ", result)
    result = append(result, right[j:]...)
    //fmt.Println("2: ", result)
    return result
}

func main() {
    arr := []int{3, 5, 1, 2, 4}
    fmt.Println(arr)
    fmt.Println(mergeSorted(arr))
}

代码解释

  1. 如果输入的数组长度小于等于 1,直接返回该数组,因为一个元素或者空数组本身就是有序的。
  2. 计算数组的中间位置 mid。
  3. 递归调用 mergeSort 函数对左半部分数组 arr[:mid] 进行排序,得到有序的 left 数组。
  4. 递归调用 mergeSort 函数对右半部分数组 arr[mid:] 进行排序,得到有序的 right 数组。
  5. 调用 merge 函数将两个有序的数组 left 和 right 合并成一个有序的结果数组 result。
  6. 创建一个空的切片 result 用于存储合并后的结果。
  7. 使用两个指针 i 和 j 分别指向 left 和 right 数组的起始位置。
  8. 比较 left[i] 和 right[j] 的大小,将较小的元素追加到 result 中,并将相应的指针向后移动一位。
  9. 重复上述步骤,直到遍历完其中一个数组。
  10. 将左侧子数组 left 中从索引 i 到末尾的所有元素追加到 result 数组的末尾。… 表示将切片 left[i:] 展开为独立的元素,然后使用 append 函数将这些元素追加到 result 数组中。将右侧子数组 right 中从索引 j 到末尾的所有元素追加到 result 数组的末尾。
  11. 返回合并后的结果数组 result。

运行结果

  • [3 5 1 2 4]
  • mid: 2
  • mid: 1
  • left: [3]
  • right: [5]
  • left: [3 5]
  • mid: 1
  • left: [1]
  • mid: 1
  • left: [2]
  • right: [4]
  • right: [2 4]
  • right: [1 2 4]
  • [1 2 3 4 5]

复杂度

时间复杂度:

最好情况、最坏情况和平均情况下,归并排序的时间复杂度都是 O(n log n),其中 n 是待排序数组的长度。归并排序的时间复杂度是稳定的,不受输入数据的影响。

空间复杂度:

归并排序的空间复杂度是 O(n),其中 n 是待排序数组的长度。在合并过程中,需要额外的空间来存储临时数组,以及递归调用时的函数调用栈。

分类: go
0 0 投票数
文章评分
订阅评论
提醒
guest

0 评论
最旧
最新 最多投票
内联反馈
查看所有评论

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部
0
希望看到您的想法,请您发表评论x