時間復(fù)雜度O(n log n)的排序算法
以下排序算法的時間復(fù)雜度都是O(n log n)
歸并排序
分而治之的思想，將數(shù)組不斷向下二分略贮，直到將相鄰2個元素比較排序明场，再相鄰4個元素比較排序减余，直到所有元素比較完畢累驮。
public func mergeSort<Element: Comparable>(_ array: [Element]) -> [Element] {
guard array.count > 1 else { return array }
let middle = array.count / 2
let left = mergeSort(Array(array[..<middle]))
let right = mergeSort(Array(array[middle...]))
return merge(left, right)
}
private func merge<Element: Comparable>(_ left: [Element], _ right: [Element]) -> [Element] {
var leftIndex = 0
var rightIndex = 0
var result: [Element] = []
while leftIndex < left.count, rightIndex < right.count {
let leftElement = left[leftIndex]
let rightElement = right[rightIndex]
if leftElement < rightElement {
result.append(leftElement)
leftIndex += 1
} else if leftElement > rightElement {
result.append(rightElement)
rightIndex += 1
} else {
result.append(leftElement)
leftIndex += 1
result.append(rightElement)
rightIndex += 1
}
}
if leftIndex < left.count {
result.append(contentsOf: left[leftIndex...])
}
if rightIndex < right.count {
result.append(contentsOf: right[rightIndex...])
}
return result
}
基數(shù)排序
按照整數(shù)的長度進(jìn)行排序
public extension Array where Element == Int {
mutating func radixSort() {
let base = 10
var done = false
var digits = 1
while !done {
done = true
var buckets: [[Int]] = .init(repeating: [], count: base)
forEach { number in
let remainingPart = number / digits
let digit = remainingPart % base
buckets[digit].append(number)
if remainingPart > 0 {
done = false
}
}
digits *= base
self = buckets.flatMap { $0 }
}
}
}
堆排序
構(gòu)造一個堆結(jié)構(gòu)，利用堆的性質(zhì)煎饼，進(jìn)行排序
struct Heap<Element: Equatable> {
var elements: [Element] = []
let sort: (Element, Element) -> Bool
init(sort: @escaping (Element, Element) -> Bool, elements: [Element]) {
self.sort = sort
self.elements = elements
if !elements.isEmpty {
for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
siftDown(from: i)
}
}
}
var isEmpty: Bool {
elements.isEmpty
}
var count: Int {
elements.count
}
func peek() -> Element? {
elements.first
}
func leftChildIndex(ofParentAt index: Int) -> Int {
(2 * index) + 1
}
func rightChildIndex(ofParentAt index: Int) -> Int {
(2 * index) + 2
}
func parentIndex(ofChildAt index: Int) -> Int {
(index - 1) / 2
}
}
extension Heap {
mutating func remove() -> Element? {
guard !isEmpty else { return nil }
elements.swapAt(0, count - 1)
defer {
siftDown(from: 0)
}
return elements.removeLast()
}
mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent
if left < count, sort(elements[left], elements[candidate]) {
candidate = left
}
if right < count, sort(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent {
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}
mutating func siftDown(from index: Int, upTo size: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent
if left < size, sort(elements[left], elements[candidate]) {
candidate = left
}
if right < size, sort(elements[left], elements[candidate]) {
candidate = right
}
if candidate == parent {
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}
mutating func insert(_ element: Element) {
elements.append(element)
siftUp(from: elements.count - 1)
}
mutating func siftUp(from index: Int) {
var child = index
var parent = parentIndex(ofChildAt: child)
while child > 0, sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
parent = parentIndex(ofChildAt: child)
}
}
mutating func remove(at index: Int) -> Element? {
guard index < elements.count else {
return nil
}
if index == elements.count - 1 {
return elements.removeLast()
} else {
elements.swapAt(index, elements.count - 1)
defer {
siftDown(from: index)
siftDown(from: index)
}
return elements.removeLast()
}
}
func index(of element: Element, startingAt i: Int) -> Int? {
if i >= count {
return nil
}
if sort(element, elements[i]) {
return nil
}
if element == elements[i] {
return i
}
if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
return j
}
if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
return j
}
return nil
}
}
// MARK: - Heap Sort
extension Heap {
func sorted() -> [Element] {
var heap = Heap(sort: sort, elements: elements)
for index in heap.elements.indices.reversed() {
heap.elements.swapAt(0, index)
heap.siftDown(from: 0, upTo: index)
}
return heap.elements
}
}
快速排序
分而治之讹挎，在一個點， 把一串?dāng)?shù)組拆分為兩串吆玖，然后遞歸進(jìn)行下去筒溃。
public func quicksortNaive<Element: Comparable>(_ a: [Element]) -> [Element] {
guard a.count > 1 else { return a }
let pivot = a[a.count / 2]
let less = a.filter { $0 < pivot }
let equal = a.filter { $0 == pivot }
let greater = a.filter { $0 > pivot }
return quicksortNaive(less) + equal + quicksortNaive(greater)
}
github倉庫地址 https://github.com/SunZhiC/DataStructuresInSwift
References
Data Structures & Algorithms in Swift by Matthijs Hollemans.
https://github.com/apple/swift-algorithms
https://github.com/raywenderlich/swift-algorithm-club
