常用的几种排序写法——快速排序&归并排序&堆排序

```go
// 堆排
func heapSort(nums []int) {
    n := len(nums)
    if n < 2 {
        return
    }
    lastParent := (n - 2) / 2
    for i := lastParent; i >= 0; i-- {
        pushDown(nums, i, n)
    }
    for i := n-1; i > 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        pushDown(nums, 0, i)
    }
}

func pushDown(nums []int, i, heapSize int) {
    for {
        left := i * 2 + 1
        right := i * 2 + 2
        largest := i
        if left < heapSize && nums[largest] < nums[left] {
            largest = left
        }
        if right < heapSize && nums[largest] < nums[right] {
            largest = right
        }
        if largest == i {
            break
        }
        nums[i], nums[largest] = nums[largest], nums[i]
        i = largest
    }
}

// 快排
func qSort(nums []int, left, right int) {
    if left >= right {
        return
    }
    // 随机化pivot
    pivotIdx := rand.Intn(right-left+1) + left
    nums[right], nums[pivotIdx] = nums[pivotIdx], nums[right]
  
    pivot := right
    i := left
    for j := left; j < right; j++ {
        if nums[j] < nums[pivot] {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[pivot] = nums[pivot], nums[i]
    qSort(nums, left, i-1)
    qSort(nums, i+1, right)
}

// 归并排序
func mergeSort(nums []int, left, right int) []int {
    if left >= right {
        return []int{nums[left]}
    }
    mid := left + ((right - left) >> 1)
    l := mergeSort(nums, left, mid)
    r := mergeSort(nums, mid+1, right)
    return merge(l, r)
}

func merge(a, b []int) []int {
    n, m := len(a), len(b)
    res := make([]int, n+m)
    p1, p2 := 0, 0
    i := 0
    for p1 < n && p2 < m {
        if a[p1] < b[p2] {
            res[i] = a[p1]
            i++
            p1++
        } else {
            res[i] = b[p2]
            i++
            p2++
        }
    }
    for p1 < n {
        res[i] = a[p1]
        i++
        p1++
    }
    for p2 < m {
        res[i] = b[p2]
        i++
        p2++
    }
    return res
}

// 链表版本
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    mid := findMid(head)
    left := sortList(head)
    right := sortList(mid)
    return merge(left, right)
}

func merge(a, b *ListNode) *ListNode {
    dummy := &ListNode{}
    p := dummy
    for a != nil && b != nil {
        if a.Val < b.Val {
            p.Next = a
            a = a.Next
            p = p.Next
        } else {
            p.Next = b
            b = b.Next
            p = p.Next
        }
    }
    if a != nil {
        p.Next = a
    }
    if b != nil {
        p.Next = b
    }
    return dummy.Next
}

func findMid(head *ListNode) *ListNode {
    var prev *ListNode
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    if prev != nil {
        prev.Next = nil
    }
    return slow
}
```

Last modification：July 16, 2025