常见排序算法及其时间复杂度

蛮力排序

这类算法通常原理简单，易于实现，但代价往往较高，有较大的提升空间。

选择排序算法

算法总是在未排序的部分中寻找最大元素，之后将最大元素与未排序部分的末尾元素交换，最后扩大已排序部分。总而言之，该算法使已排序部分从末尾逐渐向前增长，直至排序完成。

伪代码如下，它将按照从小到大的顺序对A进行排序：

def selection_sort(A: list):
    for i in reverse(range(len(A))): # i标识了当前未排序部分的末尾位置，因此i是逐步减小的
        index_max = get_max(A, 0, i) # 取得未排序部分的最大元素
        swap(A[index_max], A[i]) # 将未排序部分的最大元素放到末尾，从而扩大了已排序部分

考虑到寻找最大元素的时间复杂度为\(O(n)\)，而寻找最大元素的过程将进行\(n\)次，因此总时间复杂度为\(O(n^2)\)。

不难看出该算法无需额外开辟其他空间，所以它的空间复杂度为\(O(1)\)，我们称这些空间复杂度为\(O(1)\)的排序算法为原地排序算法。

插入排序算法

这种算法可以利用到输入元素可能存在的有序性。算法总是从未排序部分取出一个元素，然后插入到已排序部分中。如果输入的元素已经具有一定有序性，那么操作次数将大大减少。

伪代码如下，它将按照从小到大的顺序对A进行排序：

def insertion_sort(A: list):
    for i in range(1, len(A)): # 开始时，将第一个元素视为已排序部分
        temp = A[i]
        j = i-1
        while j>=0 and A[j]>A[i]: # 寻找合适的插入位置
            A[j+1] = A[j] # 为待插入元素腾位置
            j -= 1
        A[j+1] = temp

可以看出，在输入元素相对有序时，代码中用于寻找插入位置的while循环部分将会减少执行次数。在输入元素完全有序（指输入与算法运行结果一致）时，用于寻找插入位置的while循环部分不会被执行，在此时，算法的时间复杂度为\(O(n)\)。但是，在输入元素顺序与算法运行结果完全相反时，用于寻找插入位置的while循环部分总会执行j次，在这种情况下，算法的时间复杂度为\(O(n^2)\)。

算法的平均时间复杂度为\(O(n^2)\)。

分治排序

分治策略的关键是对子问题的划分和对子问题解的合并。通常，根据这两个步骤的难易程度可以把分治算法分成“难分易合型”和“易分难合型”。通过分治，可以将排序的时间复杂度从\(O(n^2)\)改进到\(O(nlogn)\)，\(O(nlogn)\)是基于比较的排序算法的最优时间复杂度。

快速排序算法

算法首先选取一个基准元素（pivot），然后把比它小的元素放在它的左边，把比它大的元素放在它的右边，这样我们就得到了三个部分：小于pivot的元素，pivot，大于pivot的元素，此时pivot显然已经处于正确的位置，只需要对小于和大于pivot的元素递归地排序即可完成排序。

把小于pivot的元素，pivot和大于pivot的元素合起来是容易的（不需要其他操作），而把元素划分为小于pivot，pivot和大于pivot这三部分的操作却是复杂的，所以我们称这个算法是难分易合的算法。

伪代码如下，它将按照从小到大的顺序对A进行排序：

def partition(A: list, p, r):
    pivot = A[r] # 选择pivot，这里选择末尾元素作为pivot，也可以选择其他元素
    i = p-1 # 标识小于pivot的部分，开始时没有元素小于pivot，所以是p-1
    for j in range(p, r):
        if A[j]<pivot:
            i += 1 # "开辟"空间存放新的小于pivot的元素
            swap(A[j], A[i])
    # 现在，A中从p到i存放着小于pivot的元素，而从i+1到r-1存放着大于pivot的元素，A[r]存放着pivot
    swap(A[i+1], A[r]) # 把pivot放到中间
    return i+1 # 返回pivot的位置

def quick_sort(A: list, p, r):
    if p<r:
        pivot_idx = partition(A, p, r) # 划分
        quick_sort(A, p, pivot_idx-1) # 对左半部分排序
        quick_sort(A, pivot_idx+1, r) # 对右半部分排序

在分析时间复杂度时，假定每次划分是均匀的（把输入的数据平均分成两半），而划分的过程显然是\(\Theta(n)\)的，那么可以得出时间复杂度的递推式\(T(n)=2T(n/2)+\Theta(n)\)。根据Master Theorem，\(E=log_22=1\)，因此\(\Theta(n)\in\Theta(n^E)\)，算法时间复杂度为\(\Theta(nlogn)\)。

合并排序（归并排序）

算法的整体思想是将所给的输入序列分成两半，然后对这两半递归地进行排序，之后合并两个已经有序的序列。这里对序列的划分显然是容易的（分成两半即可），而对两个有序序列的合并却是相对困难的，因此我们称这个算法是易分难合的算法。

在合并两个有序序列（这里指从小到大排列）时，我们总是对比两个序列的第一个元素，将其中较小的元素取出并放进最终的结果序列中，重复这个过程直到两个有序序列都为空，就完成了合并。

伪代码如下，它将按照从小到大的顺序对A进行排序：

def merge(A: list, p, q, r):
    left_a = A[p:q+1]
    right_a = A[q:r+1] # 取出两个有序的子序列
    left_a.append(inf)
    right_a.append(inf) # 为了方便接下来的合并
    left = 0
    right = 0
    for i in range(p, r+1):
        if left_a[left] < right_a[right]:
            A[i] = left_a[left]
            left += 1
        else:
            A[i] = right_a[right]
            right += 1
  
def merge_sort(A: list, p, r):
    if p<r:
        q = (p+r)/2 # 拆分
        merge_sort(A, p, q) # 排序
        merge_sort(A, q+1, r) # 排序
        merge(A, p, q, r) # 合并

不难看出，合并（merge）部分的时间复杂度为\(\Theta(n)\)，则可以写出归并排序时间复杂度的递推式\(T(n)=2T(n/2)+\Theta(n)\)。根据Master Theorem，\(E=log_22=1\)，因此\(\Theta(n)\in\Theta(n^E)\)，算法时间复杂度为\(\Theta(nlogn)\)。