O(nlogn)

归并排序(Merge Sort)

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

用递归实现归并排序：

• 递推公式：merge_sort(start…end) = merge(merge_sort(start…mid), merge_sort(mid+1…end))
  • 下标 mid 等于 start 和 end 的中间位置，也就是 (start+end)/2
• 终止条件：start >= end 不用再继续分解

 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

func MergeSort(arr []int) {
    arrLen := len(arr)
    if arrLen <= 1 {
        return
    }

    mergeSort(arr, 0, arrLen-1)
}

func mergeSort(arr []int, start, end int) {
    if start >= end {
        return
    }

    mid := (start + end) / 2
    mergeSort(arr, start, mid)
    mergeSort(arr, mid+1, end)
    merge(arr, start, mid, end)
}

// 相当于merge(arr[start...end], arr[start...mid], arr[mid+1...end])
func merge(arr []int, start, mid, end int) {
    //1. 先将要合并的两个放到tmpLeft和tmpRight数组,其中每个数组都多出一个位置放哨兵
    tmpLeft := make([]int, mid-start+1+1)
    tmpRight := make([]int, end-mid+1)

    //2. tmpLeft[leftSize] = int.MaxValue; tmpRight[rightSize] = int.MaxValue;
    copy(tmpLeft[0:mid-start+1], arr[start:mid+1])
    tmpLeft[mid-start+1] = math.MaxInt32
    copy(tmpRight[0:end-mid], arr[mid+1:end+1])
    tmpRight[end-mid] = math.MaxInt32

    //3. 比较两个tmp数组,哪个小就放到原数组,使用哨兵不用再判断是否有剩下的有序数组
    for k,i,j := start,0,0; k<= end; k++ {
        // 必须使用<=，保证如果 tmpLeft和 tmpRight之间有值相同的元素，先把 tmpLeft中的元素放入 arr 数组
        if tmpLeft[i] <= tmpRight[j] {
            arr[k] = tmpLeft[i]
            i++
        } else {
            arr[k] = tmpRight[j]
            j++
        }
    }
}

归并排序的空间复杂度是多少？

• 递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。
• 在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

归并排序的时间复杂度是多少？

• 如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我们就可以得到这样的递推关系式：T(a) = T(b) + T(c) + K
  • 其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。
  • 不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
• 归并排序的时间复杂度的计算公式是：

  T(1) = C; n=1时，只需要常量级的执行时间，所以表示为C。
  T(n) = 2*T(n/2) + n; n>1
       = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
       = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
       = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
       ......
       = 2^k * T(n/2^k) + k * n
       ......
  

• 结论：
  • T(n) = 2^kT(n/2^k)+kn，当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 $k=log_2 n$
  • 我们将 k 值代入上面的公式，得到 $T(n)=Cn+nlog_2 n$ 。
  • 如果我们用大 O 标记法来表示的话，T(n) 就等于 $O(nlogn)$

快排

如果要排序数组中下标从 start 到 end 之间的一组数据，我们选择 start 到 end 之间的任意一个数据作为 pivot（分区点）。

我们遍历 start 到 end 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。
经过这一步骤之后，数组 start 到 end 之间的数据就被分成了三个部分：

• 前面 start 到 i-1 之间都是小于 pivot 的，
• 中间是 pivot，
• 后面的 i+1 到 end 之间是大于 pivot 的。

用递归实现快排：

• 递推公式：quick_sort(start…end) = quick_sort(start…i-1) + quick_sort(i+1…end)
• 终止条件：start >= end 不用再继续分解

 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

func QuickSort(arr []int) {
    separateSort(arr, 0, len(arr)-1)
}

func separateSort(arr []int, start, end int) {
    if start >= end {
        return
    }
    i := partition(arr, start, end)
    separateSort(arr, start, i-1)
    separateSort(arr, i+1, end)
}

func partition(arr []int, start, end int) int {
    // 选取最后一位当对比数字
    pivot := arr[end]

    // 处理过程类似选择排序: 注意在数组中插入数据时，不再使用多次数据搬移，而是仅仅交换一次数据。
    // 通过游标 i 把 arr[start...end-1]分成两部分。arr[start...i-1]的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，arr[i...end-1]是“未处理区间”
    // 我们每次都从未处理的区间 arr[i...end-1]中取一个元素 arr[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 arr[i]的位置。
    var i = start
    for j := i; j < end; j++ {
        if arr[j] < pivot {
            if !(i == j) {
                // 交换位置
                arr[i], arr[j] = arr[j], arr[i]
            }
            i++
        }
    }

    arr[i], arr[end] = arr[end], arr[i]

    return i
}

快排是稳定的排序算法吗？

• 因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。
• 所以，快速排序并不是一个稳定的排序算法。

快排的时间复杂度是多少？

• 快排的时间复杂度的计算公式是：
  • 假设，每次选择的 pivot 都很合适，正好能将大区间对等地一分为二，那么它的递归公式就和归并排序是一样的：

    T(1) = C;   n=1时，只需要常量级的执行时间，所以表示为C。
    T(n) = 2*T(n/2) + n;  n>1
    

  • 假设每次分区操作都将区间分成大小为 9:1 的两个小区间:

    T(1) = C;   n=1时，只需要常量级的执行时间，所以表示为C。
    T(n) = T(n/10) + T(9*n/10) + n;  n>1
    

    • 这个公式的递推求解的过程非常复杂，虽然可以求解，但我不推荐用这种方法。
    • 实际上，递归的时间复杂度的求解方法除了递推公式之外，还有递归树
  • 如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。
    • 如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。
    • 我们需要进行大约 n 次分区操作，才能完成快排的整个过程。
    • 每次分区我们平均要扫描大约 n/2 个元素。
    • 这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
• 结论：
  • T(n) = 2^kT(n/2^k)+kn，当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 $k=log_2 n$
  • 我们将 k 值代入上面的公式，得到 $T(n)=Cn+nlog_2 n$ 。
  • 如果我们用大 O 标记法来表示的话，T(n) 就等于 $O(nlogn)$

如何用快排思想在O(n)内查找第K大元素？

选择数组区间 A[0…n-1]的最后一个元素 A[n-1]作为 pivot，对数组 A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。

• 如果 p+1=K，那 A[p]就是要求解的元素；
• 如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1]区间，我们再按照上面的思路递归地在 A[p+1…n-1]这个区间内查找
• 如果 K<p+1，那我们就在 A[0…p-1]区间查找。

为什么上述解决思路的时间复杂度是 O(n)？

• 第一次分区查找，我们需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。
• 第二次分区查找，我们只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。
• 依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。
• 如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于 2n-1。所以，上述解决思路的时间复杂度就为 O(n)。

借助递归树来求解递归算法的时间复杂度

归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名字，叫作递归树。

• 依次计算每一层递归操作涉及到的数据规模之和，一般都是n
• 那么所有层需要遍历的数据总和为 $hn$，也就是时间复杂度为 $O(hn)$

1. 用递归树来求解归并排序的时间复杂度

              归并排序递归树
                         m(n)
                  /                  \   -------------------------------n
            m(n/2)                    m(n/2)
          /      \                   /      \ -------------------n/2+n/2=n
    m(n/4)        m(n/4)       m(n/4)        m(n/4)
   /     \       /     \      /     \       /     \  ----n/4+n/4+n/4+n/4=n
m(n/8) m(n/8) m(n/8)m(n/8) m(n/8) m(n/8) m(n/8) m(n/8)

• 每次分解都是一分为二，所以代价很低，我们把时间上的消耗记作常量 1
• 归并算法中比较耗时的是归并操作，也就是把两个子数组合并为大数组
  • 归并操作消耗的时间与数据规模相关
  • 从图中可以看出，每层归并操作，涉及的数据规模累计和都是n。
• 我们只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 $O(n∗h)$。
  • 从归并排序的原理和递归树，可以看出来，归并排序递归树是一棵满二叉树。
  • 满二叉树的高度大约是 log2n，所以，归并排序递归实现的时间复杂度就是 O(nlogn)。

2. 用递归树来求解快速排序的时间复杂度

             快排递归树
                                         q(n)
                         /                                    \                     --------------n
                  q(n/10)                                      q(9n/10)
              /            \                                /               \   -------n/10+9n/10=n
      q(n/10^2)            q(9n/10^2)             q(9n/10^2)                 q(9^2n/10^2)
        /   \                /    \                 /     \                   /      \  -----n/10^2+9n/10^2+9n/10^2+9^2n/10^2=n
q(n/10^3) q(9n/10^3) q(9n/10^3) q(9^2n/10^3) q(9n/10^3) q(9^2n/10^3) q(9^2n/10^3) q(9^3n/10^3)

• 快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是 n。
• 我们现在只要求出递归树的高度 h，这个快排过程遍历的数据个数就是 $h∗n$ ，也就是说，时间复杂度就是 $O(h∗n)$。
  • 快速排序结束的条件就是待排序的小区间，大小为 1，也就是说叶子节点里的数据规模是 1
  • 从根节点 n 到叶子节点 1，递归树中最短的一个路径每次都乘以 101，最长的一个路径每次都乘以 109。
    • 从根节点到叶子节点的最短路径是 $log_{10} n$，最长的路径是 $log_{9\over10} n$。
    • 遍历数据的个数总和就介于 nlog10n 和 nlog910n 之间。根据复杂度的大 O 表示法，对数复杂度的底数不管是多少，我们统一写成 logn，所以，当分区大小比例是 1:9 时，快速排序的时间复杂度仍然是 O(nlogn)。

上一篇 « O(n^2) 下一篇 » O(n)