算法-归并排序

归并排序

归并排序是一种分治(divide and conquer)算法,其运行时间比插入排序低。 归并排序算法通过使用递归来工作; 它会重复将未排序的列表分成两半。 当列表为空或只有单个元素时,它被当做是已排序的; 这是基准情形

大部分的排序工作是在merge函数中执行的,merge函数负责将两部分合并在一起。 merge函数在合并过程中使用与输入数组大小相同的临时数组,因此它具有较高的空间复杂度O(n)。

算法描述

  • divide:如果集合 S 为零或一个,则直接返回它,因为它已经完成了排序。 否则,将其分成两个序列S1S2S1包含S的前N/2个元素,S2包含剩余的N/2个元素。
  • conquer:如果 S1S2 满足了基准情形(列表元素数量为 1 或 0),则对其排序。否则就再次分割列表直到满足基准情形
  • merge: 将已排序的S1S2子列表合并到一个已排序的序列中并返回元素。




查看视频

Swift 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public func mergerSort<T:Comparable>(_ list: [T]) -> [T] {
guard list.count > 1 else {
return list
}

func merge<T: Comparable>(_ lhs: [T], _ rhs: [T]) -> [T] {
var leftIndex: Int = 0
var rightIndex: Int = 0
var tempList = [T]()
tempList.reserveCapacity(lhs.count + rhs.count)

while leftIndex < lhs.count, rightIndex < rhs.count {
if lhs[leftIndex] < rhs[rightIndex] {
tempList.append(lhs[leftIndex])
leftIndex += 1
} else if lhs[leftIndex] > rhs[rightIndex] {
tempList.append(rhs[rightIndex])
rightIndex += 1
} else {
tempList.append(lhs[leftIndex])
tempList.append(rhs[rightIndex])
leftIndex += 1
rightIndex += 1
}
}

tempList += lhs[leftIndex ..< lhs.endIndex]
tempList += rhs[rightIndex ..< rhs.endIndex]
return tempList
}

let center = list.count / 2
return merge(mergerSort([T](list[0 ..< center])), mergerSort([T](list[center ..< list.endIndex])))
}

算法分析

比较操作的次数介于 (nlog n)/2nlog n - n + 1 赋值操作的次数是 2nlog n

数据结构: 数组
最坏时间复杂度:O(nlog n)
最优时间复杂度:O(nlog n)
平均时间复杂度:O(nlog n)
空间复杂度为:Θ(n)

Reference