Zusammenführungssortierung mithilfe der Einfügungssortierung für kleine Arrays

Die Komplexität der reinen Zusammenführungssortierung beträgt: O(nlgn), während die zeitliche Komplexität der reinen Einfügungssortierung beträgt: O(n^2). Wenn die Datenmenge groß ist, wird die Zusammenführungssortierung

verwendet, aber wenn n klein ist, kann die Einfügungssortierung schneller ausgeführt werden. Wenn das Teilproblem bei der Zusammenführungssortierung klein genug wird, kann die Verwendung der Einfügungssortierung, um die rekursiven Blätter dicker zu machen, die Sortierung beschleunigen. Wie messen Sie also, ob dieser Wert klein genug ist? Siehe unten:

Ich werde diese nicht beweisen, es ist relativ einfach:

A, Einfügungssortierung kann jede Länge k in O(nk)-Zeit sortieren, im schlimmsten Fall n/k Unterlisten

B, diese Unterlisten können im schlimmsten Fall in O(nlg(n/k)) Zeit zusammengeführt werden

C, das Maximum des überarbeiteten Algorithmus. Die Laufzeitkomplexität im schlechten Fall beträgt O (nk + nlg(n/k))

Dann ist O(nk+nlg(n/k))=O(nlgn). Der erste Term Auf der linken Seite der Gleichung steht ein Term höherer Ordnung. Wenn k größer als lgn ist, ist es komplexer als die Zusammenführungssortierung. Die linke Seite kann als nk+nlgn-nlgk geschrieben werden. Wenn k gleich lgn ist, ist es 2nlgn-nlglgn. Ohne den konstanten Koeffizienten ist es dasselbe wie die Zusammenführungssortierung.

Abschließende Schlussfolgerung: Wenn k

from at003_insertsort import insertSort
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__ == &#39;__main__&#39;:
    aa = [4, 2, 5, 1, 6, 3, 7, 9, 8]
    mergeSort(aa)
    print(aa)