归并排序

231次阅读

共计 792 个字符,预计需要花费 2 分钟才能阅读完成。

概念

归并排序是一种非常高效的排序算法,它的核心思想是采用分治的思想,将待排序的序列分成两个子序列,然后分别对两个子序列进行排序,最后将两个子序列合并成一个有序的序列。

算法流程如下:

  1. 将待排序序列分解成两个子序列。

  2. 将两个子序列排好序。

  3. 将两个排好序的子序列合并。

代码实现

package main

import "fmt"

func mergeSort(arr []int) []int {if len(arr) <= 1 {return arr}
    mid := len(arr) >> 1
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left []int, right []int) []int {tmp := make([]int, len(left)+len(right))
    i, j, k := 0, 0, 0
    for i < len(left) && j < len(right) {if left[i] <= right[j] {tmp[k] = left[i]
            i++
        } else {tmp[k] = right[j]
            j++
        }
        k++
    }
    for i < len(left) {tmp[k] = left[i]
        i++
        k++
    }
    for j < len(right) {tmp[k] = right[j]
        j++
        k++
    }
    return tmp
}

func main() {arr := []int{5, 4, 7, 8, 9, 2}
    res := mergeSort(arr)
    fmt.Println(res)
}

算法分析

归并排序的时间复杂度是 O(nlogn)。从代码中可以看到,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn)。另外归并排序不是原地排序算法,在合并两个数组的过程中需要借助额外的空间,空间复杂度是 O(n)。

正文完
 
dkp
版权声明:本站原创文章,由 dkp 2023-04-07发表,共计792字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。