golang 归并排序,快速排序,堆排序的实现
本文主要介绍了golang 归并排序,快速排序,堆排序的实现，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
归并排序
归并排序使用经典的分治法（Divide and conquer）策略。分治法会将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | 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} |
快速排序
快速排序算法采用的分治算法，因此对一个子数组A[p…r]进行快速排序的三个步骤为：
（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下标是在划分过程中计算得出的。
（2）解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序。
（3）合并：因为两个子数组是就地排序，不需要合并操作，整个数组A[p…r]排序完成。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | 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 2 3 4 | func sortArray(nums []int) []int { sort.Ints(nums) return nums} |
到此这篇关于golang 归并排序,快速排序,堆排序的实现的文章就介绍到这了
原文链接：https://blog.csdn.net/weixin_40486544/article/details/104312428