Skip to content

02-sorting-algorithms.md

Latest commit

 

History

History
331 lines (244 loc) · 6.05 KB

02-sorting-algorithms.md

File metadata and controls

331 lines (244 loc) · 6.05 KB

4.2 排序与查找算法

📍 导航：返回目录 | 上一节：数据结构 | 下一节：动态规划

快速排序

原理

选择基准值，将数组分为两部分：小于基准和大于基准。

func quickSort(arr []int, left, right int) {
    if left >= right {
        return
    }
    
    pivot := partition(arr, left, right)
    quickSort(arr, left, pivot-1)
    quickSort(arr, pivot+1, right)
}

func partition(arr []int, left, right int) int {
    pivot := arr[right]
    i := left - 1
    
    for j := left; j < right; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1
}

时间复杂度：

  • 平均：O(n log n)
  • 最坏：O(n²)

空间复杂度：O(log n)

归并排序

原理

分治策略：分割 → 排序 → 合并

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    
    return result
}

时间复杂度：O(n log n)（稳定）
空间复杂度：O(n)

二分查找

标准模板

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    
    for left <= right {
        mid := left + (right-left)/2
        
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1
}

变种：查找第一个等于target的位置

func binarySearchFirst(arr []int, target int) int {
    left, right := 0, len(arr)-1
    result := -1
    
    for left <= right {
        mid := left + (right-left)/2
        
        if arr[mid] == target {
            result = mid
            right = mid - 1  // 继续向左查找
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

时间复杂度：O(log n)

滑动窗口

最长无重复子串

func lengthOfLongestSubstring(s string) int {
    charMap := make(map[byte]int)
    left, maxLen := 0, 0
    
    for right := 0; right < len(s); right++ {
        if pos, exists := charMap[s[right]]; exists {
            left = max(left, pos+1)
        }
        
        charMap[s[right]] = right
        maxLen = max(maxLen, right-left+1)
    }
    
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

固定大小窗口：最大和

func maxSumSubarray(arr []int, k int) int {
    if len(arr) < k {
        return 0
    }
    
    // 初始窗口和
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += arr[i]
    }
    
    maxSum := windowSum
    
    // 滑动窗口
    for i := k; i < len(arr); i++ {
        windowSum = windowSum - arr[i-k] + arr[i]
        maxSum = max(maxSum, windowSum)
    }
    
    return maxSum
}

双指针技巧

两数之和（有序数组）

func twoSum(arr []int, target int) []int {
    left, right := 0, len(arr)-1
    
    for left < right {
        sum := arr[left] + arr[right]
        
        if sum == target {
            return []int{left, right}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    
    return nil
}

删除重复元素

func removeDuplicates(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    
    slow := 0
    for fast := 1; fast < len(arr); fast++ {
        if arr[fast] != arr[slow] {
            slow++
            arr[slow] = arr[fast]
        }
    }
    
    return slow + 1
}

TopK问题

堆排序实现

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 查找最大的K个元素
func topKLargest(arr []int, k int) []int {
    if k >= len(arr) {
        return arr
    }
    
    // 最小堆
    h := &IntHeap{}
    heap.Init(h)
    
    for _, num := range arr {
        if h.Len() < k {
            heap.Push(h, num)
        } else if num > (*h)[0] {
            heap.Pop(h)
            heap.Push(h, num)
        }
    }
    
    result := make([]int, k)
    for i := k - 1; i >= 0; i-- {
        result[i] = heap.Pop(h).(int)
    }
    
    return result
}

时间复杂度：O(n log k)

本章小结

关键要点：

  • ✅ 快速排序：平均O(n log n)，原地排序
  • ✅ 归并排序：稳定排序，适合链表
  • ✅ 二分查找：有序数组，O(log n)
  • ✅ 滑动窗口：子串/子数组问题的利器

扩展阅读

💡 思考题：

  1. 什么时候用快排？什么时候用归并排序？
  2. 二分查找的边界条件如何处理？
  3. 滑动窗口适用于哪些场景？

⏮️ 上一节：数据结构 | ⏭️ 下一节：动态规划