面试经常会被问到的单向链表的快速排序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
}
}
