归并排序中对小数组采用插入排序

发表于 分类于

纯归并排序的复杂度为O(nlgn)，而纯插入排序的时间复杂度为O(n^2)。数据量很大的时候采用归并排序。

但是在n较小的时候插入排序可能运行的会更快点。因此在归并排序中当子问题变得足够小时， 采用插入排序来使得递归的叶子变粗可以加快排序速度。那么这个足够小到底怎么去衡量呢？ 请看下面：

这么几个我不证明了，比较简单：

  • 插入排序最坏情况下可以在O(nk)时间内排序每个长度为k的n/k个子列表
  • 在最坏情况下可在O(nlg(n/k))的时间内合并这些子表
  • 修订后的算法的最坏情况运行时间复杂度是O(nk + nlg(n/k))

那么，O(nk+nlg(n/k))=O(nlgn).只能最大是k=O(lgn).等式左边中第一项是高阶项。 k如果大于lgn,则比归并排序复杂度大了。 左边可以写成nk+nlgn-nlgk，k等于lgn时，就是2nlgn-nlglgn.忽略恒定系数，则与归并排序是一样的。 最后结论： k < lg(n)的时候，使用插入排序。

实现

首先是插入排序的实现，这个比较简单：

1
2
3
4
5
6
7
8
9
def insertSort(seq):
    for j in range(1, len(seq)):
        key = seq[j]
        # insert arrays[j] into the sorted seq[0...j-1]
        i = j - 1
        while i >= 0 and seq[i] > key:
            seq[i + 1] = seq[i]
            i -= 1
        seq[i + 1] = key

然后是利用了插入排序的归并排序算法：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from math import log

__author__ = 'Xiong Neng'

def mergeSort(seq):
    mergeSortRange(seq, 0, len(seq) - 1, log(len(seq)) - 1)


def mergeOrderedSeq(seq, left, middle, right):
    """
    seq: 待排序序列
    left <= middle <= right
    子数组seq[left..middle]和seq[middle+1..right]都是排好序的
    该排序的时间复杂度为O(n)
    """
    tempSeq = []
    i = left
    j = middle + 1
    while i <= middle and j <= right:
        if seq[i] <= seq[j]:
            tempSeq.append(seq[i])
            i += 1
        else:
            tempSeq.append(seq[j])
            j += 1
    if i <= middle:
        tempSeq.extend(seq[i:middle + 1])
    else:
        tempSeq.extend(seq[j:right + 1])
    seq[left:right + 1] = tempSeq[:]


def mergeSortRange(seq, start, end, threshold):
    """
    归并排序一个序列的子序列
    start: 子序列的start下标
    end: 子序列的end下标
    threshold: 待排序长度低于这个值，就采用插入排序
    """
    if end - start < threshold:
        tempSeq = seq[start: end + 1]
        insertSort(tempSeq)
        seq[start: end + 1] = tempSeq[:]
    elif start < end:  # 如果start >= end就终止递归调用
        middle = (start + end) / 2
        mergeSortRange(seq, start, middle, threshold)  # 排好左边的一半
        mergeSortRange(seq, middle + 1, end, threshold)  # 再排好右边的一半
        mergeOrderedSeq(seq, start, middle, end)  # 最后合并排序结果


if __name__ == '__main__':
    test = [4, 2, 5, 1, 6, 3, 7, 9, 8]
    mergeSort(test)
    print(test)

比较清楚，应该不需要再多解释了。