双向链表的快速排序(swift版本)

面试经常会被问到的单向链表的快速排序or双向链表的快速排序，现在用swift写了一个双向链表的快速排序，直接上代码
获取源码

//初始化
var linkList = LinkList<Int>()
linkList.append(value: 12)
linkList.append(value: 5)
linkList.append(value: 30)
linkList.append(value: 3)
linkList.append(value: 3)
linkList.append(value: 2)
linkList.append(value: 9)
linkList.append(value: 4)
linkList.append(value: 11)
linkList.append(value: 19)
linkList.append(value: 15)
linkList.append(value: 16)

print("Init Data: \(linkList)")

var firstNode = linkList.searchIndex(index: 0)
var endNode = linkList.searchIndex(index: linkList.linkListSize() - 1)
quickSort(linkList: &linkList, low: &firstNode, high: &endNode)

print("After QuickSort: \(linkList)")
// Print效果
Init Data: [Optional(12), Optional(5), Optional(30), Optional(3), Optional(3), Optional(2), Optional(9), Optional(4), Optional(11), Optional(19), Optional(15), Optional(16)]
After QuickSort: [Optional(2), Optional(3), Optional(3), Optional(4), Optional(5), Optional(9), Optional(11), Optional(12), Optional(15), Optional(16), Optional(19), Optional(30)]
Program ended with exit code: 0

class Node<T> {
    var value: T
    var next: Node?
    weak var previous: Node?

    init(value: T) {
        self.value = value
    }
}

class LinkList<T: Comparable> {
    var head: Node<T>?
    var tail: Node<T>?
    
    // Add
    func append(value: T) {
        let newNode = Node.init(value: value)
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        }
        else {
            head = newNode
        }
        tail = newNode
    }
    
    // Size
    func linkListSize() -> Int {
        if let node = head {
            var index = 1
            var node = node.next
            while node != nil {
                index += 1
                node = node?.next
            }
            return index
        }
        else {
            return 0
        }
    }
    
    // Search
    func searchNode(indexNode: Node<T>) -> Int {
        if let node = head {
            if node === indexNode {
                return 0
            }
            else {
                var index: Int = 0
                var node = node.next
                while node != nil {
                    index += 1
                    if node === indexNode {
                        return index
                    }
                    node = node?.next
                }
                // 不存在返回-1
                return -1
            }

        }
        else {
            // 不存在返回-1
            return -1
        }
    }
    
    func lowBeforeHigh(low: Node<T>, high: Node<T>) -> Bool {
        if low === high {
            return false
        }
        else {
            var node = low.next
            while node != nil {
                if node === high {
                    return true
                }
                node = node?.next
            }
        }
        return false
    }
    
    func searchIndex(index: Int) -> Node<T>? {
        if let node = head {
            if index == 0 {
                return node
            }
            else {
                var node = node.next
                var nodeIndex: Int = 1
                while node != nil {
                    if nodeIndex == index {
                        return node
                    }
                    nodeIndex += 1
                    node = node?.next
                }
                return nil
            }
        }
        else {
            return nil
        }
    }
    
    // Remove
    func remove(node: Node<T>) -> T {
        let preNode = node.previous
        let nextNode = node.next
        
        if let preNode = preNode {
            // 前节点存在
            preNode.next = nextNode
        }
        else {
            // 不存在前节点，将nextNode置成head
            head = nextNode
        }
        nextNode?.previous = preNode
        
        if nextNode == nil {
            tail = preNode
        }
        
        // 将node置成nil
        node.previous = nil
        node.next = nil
        return node.value
    }
    
    func removeAll() {
        head = nil
        tail = nil
    }
}

//MARK: - QuickSort
func quickSort(linkList: inout LinkList<Int>, low: inout Node<Int>?, high: inout Node<Int>?) {
    guard linkList.head != nil && linkList.tail != nil else {
        return
    }
    guard low != nil && high != nil else {
        return
    }
    guard linkList.lowBeforeHigh(low: low!, high: high!) else {
        return
    }
    
    let midIndex = partition(linkList: &linkList, low: &low!, high: &high!)
    // 递归
    quickSort(linkList: &linkList, low: &low, high: &linkList.searchIndex(index: midIndex )!.previous)
    quickSort(linkList: &linkList, low: &linkList.searchIndex(index: midIndex)!.next, high: &high)
}

func partition(linkList: inout LinkList<Int>, low: inout Node<Int>, high: inout Node<Int>) -> Int {
    var value: Int = 0
    var lowNode = low
    var highNode = high
    let lowValue = low.value
    
    while linkList.lowBeforeHigh(low: lowNode, high: highNode) {
        // 从右边向左边扫描
        while linkList.lowBeforeHigh(low: lowNode, high: highNode) && highNode.value >= lowValue {
            highNode = highNode.previous!
        }

        if highNode === lowNode {
            value = linkList.searchNode(indexNode: lowNode)
            break
        }
        
        // lowNode和highNode交换值
        let temp1Value = lowNode.value
        lowNode.value = highNode.value
        highNode.value = temp1Value
        
        // 从左边向右边扫描
        while linkList.lowBeforeHigh(low: lowNode, high: highNode) && lowNode.value <= lowValue {
            lowNode = lowNode.next!
        }
        if lowNode === highNode {
            value = linkList.searchNode(indexNode: lowNode)
            break
        }
        // lowNode和highNode交换值
        let temp2Value = lowNode.value
        lowNode.value = highNode.value
        highNode.value = temp2Value
    }
    return value
}

func swapTwoNode(low: inout Node<Int>, high: inout Node<Int>) {
    // 相邻节点
    if low.next === high {
        low.previous?.next = high
        high.previous = low.previous
        
        low.previous = high
        low.next = high.next
        
        high.next?.previous = low
        high.next = low
    }
    else {
        // 非相邻节点
        low.previous?.next = high
        low.next?.previous = high
        
        high.next?.previous = low
        high.previous?.next = low
        
        let temp1 = low.previous
        low.previous = high.previous
        high.previous = temp1
        
        let temp2 = low.next
        low.next = high.next
        high.next = temp2
    }
}