优秀文章

class Solution {
    func sortArray(_ nums: [Int]) -> [Int] {
        let left = 0, right = nums.count - 1
        var arr = nums
        quickSort(&arr, left, right)
        return arr
    }

    func quickSort(_ nums: inout [Int], _ low: Int, _ high: Int) {
        guard low < high else {
            return
        }

        let randomIndex = Int.random(in: (low...high))
        let pivot = nums[randomIndex]
        // 把随机选择的数放到最前面
        nums.swapAt(low, randomIndex)
        var left = low, right = high

        while left < right {
            while left < right, pivot <= nums[right] {
                right -= 1
            }
            while left < right, nums[left] <= pivot {
                left += 1
            }
            if left < right {
                nums.swapAt(left, right)
            }
        }
        // 把pivot交换回来
        nums.swapAt(left, low)

        quickSort(&nums, low, left - 1)
        quickSort(&nums, left + 1, high)
    }
}

/// traversals 为输出的数组
func preorder(_ node: TreeNode?) {
    guard let node = node else {
      return
    }
    
    /// 前序遍历
    traversals.append(node.val) 
    preorder(node.left)
    preorder(node.right)
    
    /// 中序遍历
    preorder(node.left)
    traversals.append(node.val) 
    preorder(node.right)
    
    /// 后序遍历
    preorder(node.left)
    preorder(node.right)
    traversals.append(node.val) 
}

func preorderIteration(_ root: TreeNode?) {
    var st: [TreeNode?] = [root]
    while !st.isEmpty {
        guard node = st.removeLast() else {
            continue
        }
        traversals.append(node.val)
        st.insert(node.right, at: 0)
        st.insert(node.left, at: 0)
    }
}

func inorderIteration(_ root: TreeNode?) {
    var st: [TreeNode?] = []
    var cur: TreeNode? = root
    while cur != nil || !st.isEmpty {
        if cur != nil {
            st.append(cur)
            cur = cur?.left
        } else {
            let lastNode = st.popLast()
            traversals.append(lastNode!.val)
            cur = lastNode?.right
        }
    }
}

func postorderIteration(_ root: TreeNode?) {
    var st: [TreeNode?] = [root]
    while !st.isEmpty {
        let node = st.removeFirst()
        if node != nil {
            traversals.append(node!.val)
        } else {
            continue
        }
        st.insert(node?.left, at: 0)
        st.insert(node?.right, at: 0)
    }
    traversals = traversals.reversed()
}

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    
    var traversals = [Int]()
    
    var stack = [(root, false)]
    
    while !stack.isEmpty {
        let (node, isVisted) = stack.removeLast()
        guard let node == node else {
            continue
        }
        
        if isVisted {
            traversals.append(node.val)
            continue
        }
        
        // ------ 逆序添加 ------
        
        ///前序遍历
        stack.append((node.right, false))
        stack.append((node.left, false))
        stack.append((node, true))
        
        ///中序遍历
        stack.append((node.right, false))
        stack.append((node, true))
        stack.append((node.left, false))
        
        ///后序遍历
        stack.append((node, true))
        stack.append((node.right, false))
        stack.append((node.left, false))
    }
    return traversals
}

// 堆排序
func sortArray(_ nums: [Int]) -> [Int] {
    var nums = nums
    var endIndex = nums.count - 1
    // 1.把当前数组构建成一个大顶堆
    // 2.接着第一个值与最后一个值调换(把最大值放到最后)
    // 3.然后把刨除最后最大值的数组重新构建成大顶推，
    // 4.再然后递归执行上面的流程
    repeat {
        buildMaxHeap(&nums, endIndex)
        (nums[endIndex], nums[0]) = (nums[0], nums[endIndex])
        endIndex = endIndex - 1
    } while(endIndex > 0)
    
    return nums
}

// 把数组构建成大顶堆
private func buildMaxHeap(_ nums: inout [Int], _ endIndex: Int) {
    var parentIndex = endIndex >> 1
    
    while parentIndex >= 0 {
        let parentValue = nums[parentIndex]
        var minNodeIndex = parentIndex
        
        let leftChildIndex = parentIndex * 2 + 1
        if endIndex >= leftChildIndex && nums[leftChildIndex] > parentValue {
            minNodeIndex = leftChildIndex
        }
        
        let rightChildIndex = parentIndex * 2 + 2
        if rightChildIndex <= endIndex && nums[rightChildIndex] > nums[minNodeIndex] {
            minNodeIndex = rightChildIndex
        }
        
        // 如果父节点不是最大的值，那么与最大值进行交换，保证堆顶是最大值
        if minNodeIndex != parentIndex {
            (nums[minNodeIndex], nums[parentIndex]) = (nums[parentIndex], nums[minNodeIndex])
        }
        
        parentIndex = parentIndex - 1
    }
}

// 基数排序
func radixSort(_ nums: [Int]) -> [Int] {
    // 最终结果
    var resultArray = nums
    
    //通过基数排序实现
    var maxDigit = 0 //最大位数
    var digit = 0 //当前所在位数(个十百千万)
    var maxValue = 0
    repeat {
        //1、建立20个桶((-9 - 9)一个数字一个桶),负数放在前10个桶,正数放到后10个桶
        var buckets = [[Int]]()
        for _ in 0 ..< 20 {
            buckets.append([Int]())
        }
        
        //2、按每个位上的值放入对应的桶中
        //let digit10n = NSDecimalNumber(decimal: pow(Decimal(10), digit)).intValue
        let digit10n = Int(pow(Double(10), Double(digit)))
        for num in resultArray {
            let mod = num / digit10n % 10 //取得某位上的值
            buckets[mod + 10].append(num)
            //首次遍历时获取到数组中的最大值，后面要用它计算最大位数是多少位
            if digit == 0 {
                maxValue = max(maxValue, abs(num))
            }
        }
        
        //resultArray.removeAll()
        //3、二维数组降维成一维数组，用于二次递归
        resultArray = buckets.flatMap {$0}
        
        // 计算绝对值最大的数的位数
        if digit == 0 {
            var tempMaxValue = maxValue
            while tempMaxValue != 0 {
                tempMaxValue = tempMaxValue / 10
                maxDigit = maxDigit + 1
            }
        }
        
        //4、进位
        digit = digit + 1
    } while (digit < maxDigit)
    
    return resultArray
}

- (__kindof MAS_VIEW *)mas_closestCommonSuperview:(MAS_VIEW *)view {
    MAS_VIEW *closestCommonSuperview = self;
    MAS_VIEW *secondViewSuperview = view;

    while (closestCommonSuperview != secondViewSuperview) {
        closestCommonSuperview = closestCommonSuperview == nil ? view : closestCommonSuperview.superview;
        secondViewSuperview = secondViewSuperview == nil ? self : secondViewSuperview.superview;
    }

    return closestCommonSuperview;
}