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

知识点掌握了，还需要不断练习才能熟练运用。下面golang学习网给大家带来一个Golang开发实战，手把手教大家学习《golang归并排序,快速排序,堆排序的实现》，在实现功能的过程中也带大家重新温习相关知识点，温故而知新，回头看看说不定又有不一样的感悟！

归并排序

归并排序使用经典的分治法（Divide and conquer）策略。分治法会将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

func sortArray(nums []int) []int {
    if len(nums) 
<h2>快速排序</h2>
<p>快速排序算法采用的分治算法，因此对一个子数组A[p…r]进行快速排序的三个步骤为：</p>
<p>　　（1）分解：数组A[p...r]被划分为两个（可能为空）子数组A[p...q-1]和A[q+1...r]，给定一个枢轴，使得A[p...q-1]中的每个元素小于等于A[q]，A[q+1...r]中的每个元素大于等于A[q]，q下标是在划分过程中计算得出的。</p>
<p>　　（2）解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。</p>
<p>　　（3）合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[p…r]排序完成。</p>
<p style="text-align:center"><img alt="在这里插入图片描述" src="/uploads/20221227/167211090363aa6337beb63.png"></p>
<pre class="brush:plain;">
func sortArray(nums []int) []int {
    quickSort(nums)
    return nums
}

func quickSort(nums []int) {
    left, right := 0, len(nums) - 1
    for right > left {
        // 右边部分放大于
        if nums[right] > nums[0] {
            right--
            continue
        }
        // 左边部分放小于等于
        if nums[left]  1 {
        sortArray(nums[:right])
    }
    if len(nums[right + 1:]) > 1 {
        sortArray(nums[right + 1:])
    }
}

堆排序

func sortArray(nums []int) []int {
    // 从n/2  最后一个非叶子结点起开始构建大顶堆
    for i := len(nums) / 2; i >= 0; i-- {
        heapSort(nums, i)
    }

    end := len(nums) - 1
    // 每次将大顶堆的最大值与末尾进行交换，并再次排序
    for end > 0 {
        nums[0], nums[end] = nums[end], nums[0]
        heapSort(nums[:end], 0)
        end--
    }
    return nums


}


// 对一个非叶子结点进行排序
func heapSort(nums []int,  pos int) {
    end := len(nums) - 1
    left := 2 * pos + 1

    if left > end {
        return
    }

    right := 2 * pos + 2
    temp := left

    // 先左右子结点进行比较，找出较小的那一个
    if right  nums[temp] {
        temp = right
    }

    if nums[temp] 
<h2>卑鄙排序</h2>
<p style="text-align:center"><img alt="在这里插入图片描述" src="/uploads/20221227/167211090463aa63383b842.png"></p>
<pre class="brush:plain;">func sortArray(nums []int) []int {
    sort.Ints(nums)
    return nums
}

 到此这篇关于golang 归并排序,快速排序,堆排序的实现的文章就介绍到这了,更多相关golang 归并排序,快速排序,堆排序内容请搜索golang学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持golang学习网！

到这里，我们也就讲完了《golang归并排序,快速排序,堆排序的实现》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！