算法

归并排序与快速排序

Posted by kyle on March 29, 2019
  最好 最坏 平均 是否原地算法？ 是否稳定？
归并排序 \( nlogn \) \( nlogn \) \( nlogn \) × √
快速排序 \( nlogn \) \( n^2 \) \( nlogn \) √ ×

归并排序

归并排序是一种基于分治思想的排序算法，通过将数列划分为若干个子数列，然后将子数列按顺序“收集”起来，以到达最终有序的目的。是一种自底向上的算法（子数列先有序，整体最后有序）

实现

可以通过递归实现，其递归表达式为：

r = p + (q - p) / 2
MergeSort(a[p, q]) = merge(MergeSort(a[p, r]), MergeSort(a[r+1, q]))

退出条件：  
p >= q

时间复杂度

假设对n个元素进行归并排序需要时间T(n)，那分解成两个子数组排序的时间为T(n/2)。
merge()函数合并两个有序子数组的时间复杂度为O(n)。
则有：

T(1) = C
T(n) = 2 * T(n/2) + n

继续分解得：

T(n) = 2 * T(n/2) + n
= 2 * (2 * T(n/4) + n/2) + n
= 2 * (2 * (2 * T(n/8) + n/4) + n/2) + n
……
= $ 2^k $ * T(n/$ 2^k $) + k * n
……

当T(n/$ 2^k $)=T(1)时，

n/$ 2^k $ = 1
=> k = $ log_{2}n $

将k值代入上面公式，得到：

T(n) = C * n + n * $ log_{2}n $
= O(nlogn)

快速排序

快速排序也是基于分治思想实现的。与归并算法不同的是，它是一种自顶向下的算法，会挑选出一个“枢轴变量”，然后保证枢轴变量左侧的元素都小于或等于它，右侧的元素都大于它。

实现

用递归实现时，递归表达式为：

pivot = partition(p, q)

quickSort(0, pivot - 1)
quickSort(pivot + 1, q)

退出条件：
p >= q

partition()为分区函数，将原数列以枢轴变量为中心分为两部分。
为了方便处理，一般直接选择最后一个元素为枢轴变量。比起取中间元素为枢轴变量的方法，这种方法不但逻辑清晰些，在细节方面也不需要耗费过多脑力去思考边界值的处理。

以最后一个元素为枢轴变量

func partition(arr []int, p int, q int) int {  
    i := p  
    j := p  
  
    for ; i < q; i++ {  
        if arr[i] < arr[q] {  
            tmp := arr[i]  
            arr[i] = arr[j]  
            arr[j] = tmp  
            j++  
        }  
    }  
  
    tmp := arr[q]  
    arr[q] = arr[j]  
    arr[j] = tmp  
  
    return j  
}

以中间元素为枢轴变量

func partition(arr []int, p int, q int) int {  
    mid := (p + q) / 2  
  
    i := p  
    j := q  
  
    for ; i < j; {  
        for ; i <= j; i++ {  
            if arr[i] >= arr[mid] {  
                break  
            }  
        }  
  
        for ; j > i; j-- {  
            if arr[j] < arr[mid] {  
                break  
            }  
        }  
  
        if i <= j {  
            tmp := arr[i]  
            arr[i] = arr[j]  
            arr[j] = tmp  
            if i == mid {  
                mid = j  
            } else if j == mid {  
                mid = i  
            }  
        } else {  
            i--  
        }  
    }  
  
    tmp := arr[i]  
    arr[i] = arr[mid]  
    arr[mid] = tmp  
  
    return j  
}