排序算法

冒泡

// BubbleSort 冒泡排序。
// 核心思想是：每一轮都比较相邻两个元素，
// 如果前面的元素更大，就交换位置。
// 这样一轮结束后，当前未排序区间中最大的元素会“冒泡”到最后面。
func BubbleSort(nums []int) {
    n := len(nums)
    if n <= 1 {
        return
    }

    for i := 0; i < n-1; i++ {
        swapped := false

        for j := 0; j < n-1-i; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = true
            }
        }

        // 如果这一轮一次交换都没有发生，
        // 说明切片已经有序，可以提前结束。
        if !swapped {
            return
        }
    }
}

快速排序

// QuickSort 快速排序。
// 核心思想是：
// 1. 先选一个基准值 pivot
// 2. 把比 pivot 小的放左边，比 pivot 大的放右边
// 3. 再分别对左右两部分继续递归排序
func QuickSort(nums []int) {
    if len(nums) <= 1 {
        return
    }

    quickSort(nums, 0, len(nums)-1)
}

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

    pivotIndex := partition(nums, left, right)
    quickSort(nums, left, pivotIndex-1)
    quickSort(nums, pivotIndex+1, right)
}

// partition 完成一轮分区，并返回基准值最终落下的位置。
func partition(nums []int, left, right int) int {
    pivot := nums[right]
    i := left - 1

    for j := left; j < right; j++ {
        if nums[j] < pivot {
            i++
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    nums[i+1], nums[right] = nums[right], nums[i+1]
    return i + 1
}

堆排序

// HeapSort 堆排序。
// 核心思想是：
// 1. 先把切片调整成大顶堆
// 2. 堆顶元素就是最大值，把它放到切片末尾
// 3. 缩小堆的范围后，继续调整堆
func HeapSort(nums []int) {
    n := len(nums)
    if n <= 1 {
        return
    }

    // 先从最后一个非叶子节点开始，自底向上构建大顶堆。
    for i := n/2 - 1; i >= 0; i-- {
        heapify(nums, n, i)
    }

    // 把堆顶最大值放到末尾，然后继续调整剩余部分。
    for end := n - 1; end > 0; end-- {
        nums[0], nums[end] = nums[end], nums[0]
        heapify(nums, end, 0)
    }
}

// heapify 保证以 root 为根的子树满足大顶堆性质。
func heapify(nums []int, heapSize, root int) {
    largest := root
    left := 2*root + 1
    right := 2*root + 2

    if left < heapSize && nums[left] > nums[largest] {
        largest = left
    }

    if right < heapSize && nums[right] > nums[largest] {
        largest = right
    }

    if largest != root {
        nums[root], nums[largest] = nums[largest], nums[root]
        heapify(nums, heapSize, largest)
    }
}