算法练习

1. 常见算法以及实现

1.1 排序算法

1.1.1 快速排序

// 快速排序
// 0. 退出条件 arr.count>1 else return
// 1. 选择中间值pivot支点
// 2. > pivot的数组arr1， < pivot的数组arr2， = pivot的arr3
// 3. 拼接arr 返回

func quickSort<T: Comparable>(arr: [T]) -> [T] {
    guard arr.count > 1 else {
        reutrn arr
    }
    
    let pivot = arr[0]
    let arr1 = arr.filter { $0 > pivot }
    let arr2 = arr.filter { $0 == pivot}
    let arr3 = arr.filter { $0 < pivot }
    
    return quickSort(arr3)   arr2   arr1
}

1.1.2 选择排序

// 选择排序：
// 选择最大放头

// 0. 退出条件 arr.count>1 else return arr
// 1. 找max 放数组sortArr
// 2. 返回 max   selectSort（arr）  min
func selectionSort<T: Comparable>(_ arr: [T]) -> [T] {
    guard arr.count > 1 else {
        return arr
    }
    
    var sortArr = [T]()
    var arr = arr
    while(arr.count > 0) {
        var minIndex = 0
        var min = arr[minIndex]
        for index in 0 ..< arr.count {
            let value = arr[index]
            if min > value {
                min = value
                minIndex = index
            }
        }
        sortArr.append(min)
        arr.remove(at: minIndex)
    }
    
    return sortArr
}

let selectionArray = selectionSort(unsortedArray) // [2, 3, 5, 6, 7, 10]

1.1.3 冒泡排序

// 冒泡排序：
// 比较大者前置

// 0. 循环遍历数组arr（count）次选取最大，i从0 ..< count
// 1. 循环遍历数组 arr j从i  1 到 count 排序置换

func bubbleSort<T: Comparable>(_ arr: [T]) -> [T] {
    let count = arr.count
    var arr = arr
    for i in 0 ..< count {
        for j in i 1 ..< count {
            if arr[i] > arr[j] {
                let temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

1.1.4 插入排序

// 插入排序
// 将数组分为有序和无序两部分,每次从无序数组中取出第一个元素,插入到有序数组中的合适位置。

// 时间复杂度：O（n^2）
// 空间复杂度：O(1)
func insertionSort<T: Comparable>(_ arr: [T]) -> [T] {
    let count = arr.count
    var result = arr
    for i in 1..<count  {
        var j = i
        while j > 0 && result[j] < result[j-1] {
            let value = result[j]
            result.remove(at: j)
            result.insert(value, at: j-1)
            j -= 1
        }
    }
    return result
}

let insertionArray = insertionSort(unsortedArray)
print("sort array = (insertionArray)")

1.1.5 归并排序

// 归并排序
// 分治思想，分解为有序表，合并为有序表

// 分解 mergeSort
// guard arr.count > 1 else { return arr }
// let sort1 = mergeSort(arr[0..<middle])
// let sort2 = mergeSort(arr[middle..<count)
// return merge(sort1, sort2)
// 合并 merge
// var leftIndex = 0
// var rightIndex = 0
// var result = [T]()
// while leftIndex < sort1.count && rightIndex < sort2.count {
//      if sort1[leftIndex] < sort2[rightIndex] {
//          result.append(sort1[leftIndex])
//          leftIndex  = 1
//      } else {
//          result.append(sort2[rightIndex])
//          rightIndex  = 1
//      }
//  }
//  sort1\sort2剩余元素追加

// 时间复杂度: O(nlog2(n))
// 空间复杂度: O(n)
// 场景：空间换时间，排序时间复杂度优于O(n^2)
func mergeSort<T: Comparable>(_ arr: [T]) -> [T] {
    guard arr.count > 1 else {
        return arr
    }
    
    let middle = arr.count / 2
    let left = mergeSort(Array(arr[0..<middle]))
    let right = mergeSort(Array(arr[middle..<arr.count]))
    
    return merge(leftArray: left, rightArray: right)
}

func merge<T: Comparable>(leftArray: [T], rightArray: [T]) -> [T] {
    var result: [T] = []
    var leftIndex = 0
    var rightIndex = 0
    while leftIndex < leftArray.count && rightIndex < rightArray.count {
        if leftArray[leftIndex] > rightArray[rightIndex] {
            result.append(rightArray[rightIndex])
            rightIndex  = 1
        } else {
            result.append(leftArray[leftIndex])
            leftIndex  = 1
        }
    }
    
    while leftIndex < leftArray.count {
        result.append(leftArray[leftIndex])
        leftIndex  = 1
    }
    
    while rightIndex < rightArray.count {
        result.append(rightArray[rightIndex])
        rightIndex  = 1
    }
    
    return result
}

print("unsort array =(unsortedArray)")
let mergeArray = mergeSort(unsortedArray)
print("merged array =(mergeArray)")

1.1.6 堆排序

// 堆排序
// 1.将数组构建成一个大顶堆/小顶堆
// 2.每次取出堆顶元素,与最后一个元素交换位置,然后调整堆产生新的堆顶
// 3. 重复步骤2,直到堆大小为1

// 时间复杂度：最坏 O(nlog2(n)) 空间复杂度O(1)
// 场景：时间复杂度要求为O(nlog2(n))

func heapSort<T: Comparable>(_ arr: [T]) -> [T] {
    
    var array = arr
    // 构建大顶堆
    for i in stride(from: (array.count - 2) / 2, through: 0, by: -1) {
        siftDown(&array, i, array.count)
    }
    
    // 排序,将大顶堆转换成升序数组
    for i in stride(from: array.count - 1, through: 1, by: -1) {
        array.swapAt(0, i) // 交换0，i元素
        siftDown(&array, 0, i)
    }
    return array
}

// 下滤操作,保持大顶堆性质
func siftDown<T: Comparable>(_ array: inout [T], _ index: Int, _ upTo: Int) {
    
    var parent = index
    while true {
        let left = 2 * parent   1
        let right = 2 * parent   2
        var candidate = parent
        
        if left < upTo && array[left] > array[candidate] {
            candidate = left
        }
        
        if right < upTo && array[right] > array[candidate] {
            candidate = right
        }
        
        if candidate == parent {
            return
        }
        
        array.swapAt(parent, candidate)
        parent = candidate
    }
}

let heapArray = heapSort(unsortedArray)
print("heap arrary = (heapArray)")

1.1.7 GPT辅助

排序算法： www.shareclaude.top/c/jxqnqoa

1.2 查询算法

1.2.1 二分查找

// 二分查找
// 升序表，从中间查找，> 则在左侧查找，< 在右侧查找

// while循环格式
// 0. var start = 0; var end = arr.count - 1; var targetIndex = -1
// 1. while(start <= end)
// 2. 找出中间index = (end - start) / 2   start(取整) 中间值center = arr[index]
// 3. if center == target targetIndex = index break ;else if center > target; end = index - 1 else start = index   1
// 4. 循环到1

func binarySearch<T: Comparable>(_ arr: [T], target: T) -> Int {
    var start = 0
    var end = arr.count - 1
    var targetIndex = -1
    while start <= end {
        var index = (end - start) / 2   start
        var center = arr[index]
        if center == target {
            targetIndex = index
            break
        }else if center > target {
            end = index - 1
        } else {
            start = index   1
        }
    }
    return targetIndex
}

let target = 10
let index = binarySearch(bubbleArray, target: target)
if index == -1 {
    print("bubbleArray= (bubbleArray), 未找到(target) ")
}else {
    print("bubbleArray= (bubbleArray), index= (index), value =(selectionArray[index])")
}

1.2.2 哈希查找

1.3 二叉树

1.3.1 二叉树创建与遍历

• 深度遍历
• 广度遍历

1.3.2 B数与B 数

1.4 回溯算法

1.5 动态规划

1.6 分支限界

2. 特殊算法练习

2.1 大数运算

3. GPT提示词

请以“常见算法总结”为题，创作一个思维导图，要求：从算法应用场景角度分析，脉络清晰，尽可能全面、真实；使用```markdown文件代码的格式展示出来

展开讲一下堆排序算法，并从核心思想、伪代码、时间/空间复杂度、缺点、使用场景、swift代码示例等方面展示出来

这篇好文章是转载于：学新通技术网