题解 | #排序#

package main

//堆排
func MySort( arr []int) []int {
    heapSort(arr)
    return arr
}

func heapSort(nums []int ) []int {
    end := len(nums) -1
    for i := end /2; i >= 0; i-- {
        sink(nums, i, end)
    }
    for i := end; i >= 0; i-- {
        nums[i], nums[0] = nums[0], nums[i]
        end--
        sink(nums, 0, end)
    }
    return nums
}

func sink (heap []int, root, end int) {
    for {
        child := root *2 +1
        if child > end {
            return
        }
        if child < end && heap[child] < heap[child +1] {
            child++
        }
        if heap[root] > heap[child] {
            return
        }

        heap[root], heap[child] = heap[child], heap[root]
        root = child
    }
}



// //快排版本，时间nlogn,最坏n^2,空间logn，不稳定
// func MySort( arr []int) []int {
//     quickSort(arr , 0, len(arr)-1)
//     return arr
// }

// func quickSort(nums []int, left, right int) {
//     if left > right {
//         return
//     }

//     i, j, base := left, right, nums[left]
//     for i < j {
//         for nums[j] >= base && i < j {
//             j--
//         }
//         for nums[i] <= base && i < j {
//             i++
//         }
//         nums[i], nums[j] = nums[j], nums[i]
//     }
//     nums[i], nums[left] = nums[left], nums[i]

//     quickSort(nums, left, i-1)
//     quickSort(nums, i+1, right)
// }



// //归并排序
// func MySort( arr []int) []int {
//     return MergeSort(arr)
// }

// func MergeSort( nums []int) []int {
//     if len(nums) <= 1 {
//         return nums
//     }

//     mid := len(nums) /2
//     left := MergeSort(nums[ :mid])
//     right := MergeSort(nums[mid: ])

//     return Merge(left, right) 
// }

// func Merge(left, right []int) []int {
//     result := make([]int, len(left) + len(right))
//     l, r, i := 0, 0, 0

//     for l < len(left) && r < len(right) {
//         if left[l] < right[r] {
//             result[i] = left[l]
//             l++
//         } else {
//             result[i] = right[r]
//             r++
//         }
//         i++
//     }

//     copy(result[i :], left[l: ])
//     copy(result[i + len(left) - l: ], right[r: ])

//     return result
// }