排序算法之Swift实践

当我们站在历史的今天,往过去回顾,总会发现一些在当下习以为常的观念,惊讶在过去竟然没人意识到,比如生产力决定生产关系,比如自由平等,这就是所谓的进步。我生于上世纪九十年代初,年纪尚轻,这些观念的巨大变革,我大多从书上学来的,如果要找一些真正有切身体会的,我想就是当下有点烂大街的用户体验。与过去单纯讲究功能性的时代相比,用户体验绝对是完全颠覆的,它完全变换了产品的核心,给人一种醍醐灌顶的顿悟感,想及此,还是要感谢乔布斯和他的苹果。

算法与用户体验看似没有关系,其实算法是上佳用户体验的基础,因为没有高效的算法,机子会卡。我至今仍是编程小白,为加深对算法的理解,本文尝试用Swift实现大部分常用的排序算法。

经典排序算法

插入排序

//不改变输入数组的状态,返回排序完成的降序数组
func insertionSort(var arr:[Int]) -> [Int] {
    for var i = 1; i < arr.count; i++ {
        let key = arr[i]
        var j = i - 1
        while j >= 0  && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
    return arr
}

翻转二叉树之Swift实践

Google: 90% of our engineers use the software you wrote(HomeBrew), but you can’t invert a binary tree on a whiteboard so fuck off.

HomeBrew作者,天才程序员Max Howell兴致盎然地去Google面试(估计是刚好路过),结果却因不会在白板上翻转二叉树被Google粗鲁地拒绝了,舆论甚是哗然,其中缘由知乎上也讨论的热火朝天。谁料,始作俑者翻转二叉树这道题目,一时也热地不要不要的。作为程序员小白的我,从未翻过二叉树。最近闲来无事,闲暇之余,想及至此,就顺手用Swift翻转了二叉树。

如果您对二叉树的概念不甚清晰,可以先到维基百科上(不推荐百度百科,因为要养成良好的搜索习惯)再温习温习二叉树相关知识。

二叉树定义

先定义一个二叉树类Tree,主要定义树的三个必要属性,关键值key,左子树leftTree和右子树rightTree

//define Tree class
class Tree {
    var key: Int
    var leftTree: Tree?
    var rightTree: Tree?
    
    init(key: Int) {
        self.key = key
    }
    
}

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×