golang 归并排序,快速排序,堆排序的实现

Golang 实现归并排序，快速排序和堆排序

简介

排序算法的实现是大多数程序员必备的技能之一。在这个过程中，我们考虑三种经典的排序算法之一：归并排序，快速排序和堆排序。我们在学习它们的同时，也在学习使用 Golang 写出高效的排序算法。

归并排序

算法原理

归并排序是基于归并操作的一种排序算法，该算法的核心思想是将一个数组分成两个较小的数组，然后递归地将它们排序，最后再将它们合并来完成排序。它是一个稳定的算法，时间复杂度为 O(nlogn)，空间复杂度也为 O(nlogn)。

实现步骤

1. 将数组划分为两个更小的数组，其中一个包含前半部分，另一个包含后半部分。
2. 递归地对这两个数组进行排序，直到只有一个元素。
3. 排序时需要合并两个数组，合并时需要遍历两个数组，将较小的元素移动到新的数组中。
4. 最后返回合并之后的结果。

代码示例

下面是归并排序算法的 Golang 实现代码:

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

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

以上代码中，MergeSort 和 merge 都是递归函数，merge 函数合并两个数组并返回一个新的数组。MergeSort 函数将原始数组拆分成两个数组并递归，最后返回合并后的结果。

快速排序

算法原理

快速排序是一种基于比较的排序算法，它使用分治法来将待排序的元素划分为较小和较大的子集，然后使用递归快速排序子集，直到子集为空或只包含一个元素。它是一个原地排序算法，平均时间复杂度为 O(nlogn)，最坏情况为 O(n^2)，空间复杂度为 O(1)。

实现步骤

1. 选择数组中的一个基准元素。
2. 遍历数组，将小于基准元素的放在左侧，大于等于基准元素的放在右侧。
3. 对左右两侧的子数组进行递归，重复以上步骤直到子数组不能再分割。
4. 最后将左侧、基准元素、右侧三部分合并到一起。

代码示例

以下是快速排序算法的 Golang 实现代码:

func QuickSort(arr []int, left, right int) {
    if left < right {
        mid := partition(arr, left, right)
        QuickSort(arr, left, mid-1)
        QuickSort(arr, mid+1, right)
    }
}

func partition(arr []int, left, right int) int {
    pivot := arr[right]
    i := left - 1
    for j := left; j < right; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1
}

以上代码中，QuickSort 函数是递归函数，它定义了一个基准元素 pivot 和两个指针 left 和 right。QuickSort 函数随时分割子数组，从而实现快速排序。partition 函数是将数组分隔成较小值的子数组和较大值的子数组的关键函数。

堆排序

算法原理

堆排序是一种原地的排序，它是一种选择排序算法，它首先构建一个二叉树，并将其转换为堆，然后将所有的元素从堆中提取和删除，直到堆为空为止。它的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

实现步骤

1. 将数组构建成一个大根堆或小根堆。
2. 循环地从堆顶选出最大或最小元素，并将其放在新数组的末尾。
3. 调整堆结构，重新构建堆。
4. 重复步骤 2 和 3 直到堆为空。

代码示例

以下是堆排序的 Golang 实现代码:

func HeapSort(arr []int) []int {
    length := len(arr)
    for i := length/2 - 1; i >= 0; i-- {
        heapify(arr, length, i)
    }
    for i := length - 1; i >= 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
    return arr
}

func heapify(arr []int, length, p int) {
    left, right := p*2+1, p*2+2
    largest := p
    if left < length && arr[left] > arr[largest] {
        largest = left
    }
    if right < length && arr[right] > arr[largest] {
        largest = right
    }
    if largest != p {
        arr[p], arr[largest] = arr[largest], arr[p]
        heapify(arr, length, largest)
    }
}

以上代码中，HeapSort 函数首先构建一个最大堆，然后反复从堆的根节点提取最大元素，并重构最大堆。heapify 函数维护堆的性质，并保证父节点总是大于等于子节点的值。

结束语

以上就是归并排序、快速排序和堆排序算法的实现。这些算法都是经典的排序算法，也是每个程序员必须掌握的算法之一。在实际生产过程中，可以根据实际情况，选择不同的算法进行排序。