golang 归并排序,快速排序, 堆排序

chenyi_li · · 612 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

  1. 归并排序


    在这里插入图片描述
func sortArray(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    partA := sortArray(nums[:len(nums)/2])
    partB := sortArray(nums[len(nums)/2:])
    
    temp := make([]int, len(partA) + len(partB))

    aPointer := 0
    bPointer := 0
    i := 0
    
    for aPointer < len(partA) && bPointer < len(partB) {
        if partA[aPointer] < partB[bPointer] {
            temp[i] = partA[aPointer]
            aPointer++
        } else {
            temp[i] = partB[bPointer]
            bPointer++
        }
        i++
    }
    for aPointer < len(partA) {
        temp[i] = partA[aPointer]
        aPointer++
        i++
    }
    for bPointer < len(partB) {
        temp[i] = partB[bPointer]
        bPointer++
        i++
    }
    return temp
}
  1. 快速排序


    在这里插入图片描述

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] <= nums[0] {
            left++
            continue
        }
        nums[left], nums[right] = nums[right], nums[left]
    }
    nums[0], nums[right] = nums[right], nums[0]
    if len(nums[:right]) > 1 {
        sortArray(nums[:right])
    }
    if len(nums[right + 1:]) > 1 {
        sortArray(nums[right + 1:])
    }
}
  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 <= end && nums[right] > nums[temp] {
        temp = right
    }

    if nums[temp] <= nums[pos] {
        return
    }

    nums[temp], nums[pos] = nums[pos], nums[temp]

    // 如果发生了交换的话 就要继续调查后续子节点(只调查交换了的后续,不用全调查,不然会超时)
    heapSort(nums, temp)
}
  1. 卑鄙排序
在这里插入图片描述
func sortArray(nums []int) []int {
    sort.Ints(nums)
    return nums
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:chenyi_li

查看原文:golang 归并排序,快速排序, 堆排序

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

612 次点击  
加入收藏 微博
上一篇:golang准备
下一篇:leetcode_617
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传