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

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

文章图片

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 := 0bPointer := 0i := 0for 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]排序完成。

文章图片

func sortArray(nums []int) []int {quickSort(nums)return nums}func quickSort(nums []int) {left, right := 0, len(nums) - 1for 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:])}}

堆排序

文章图片

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) - 1left := 2 * pos + 1if left > end {return}right := 2 * pos + 2temp := 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)}

卑鄙排序