数据结构与算法 - 排序算法(下)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

数据结构与算法 - 排序算法(下)

上一篇介绍了排序算法中的选择排序、冒泡排序、插入排序，这三种算法的平均情况时间复杂度都为$O(n^2)$，因此对于数据规模比较大的时候，就不适用了。本节介绍两种效率比较高的算法，归并排序、快速排序。

归并排序

归并排序的思想是：将要排序的数组分成两个子数组，将子数组进行排序，然后合并子数组。可以看出来，归并排序具有非常明显的分治策略特征。排序过程如下：

用递归式表示归并排序如下：

代码如下：

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
--[[

递推公式：
merge_sort(p..r) = merge(merge_sort(p..q),merge_sort(q+1,r))

终止条件
p >= r 不用继续分解

--]]

--- 合并两个子数组
function merge(t,p,q,r)
  local i,j = p,q+1
  local temp = {}
  
  while i<= q and j <= r do
    if t[i] <= t[j] then
      table.insert(temp,t[i])
      i = i + 1
    else
      table.insert(temp,t[j])
      j = j + 1
    end
  end
  
  local start,endIndx = i,q
  if j <= r then
    start,endIndx = j,r
  end
  
  while start<= endIndx do
    table.insert(temp,t[start])
    start = start + 1
  end
  
  for tindex=1,#temp do
    t[p+tindex-1]=temp[tindex]
  end
  
end

--- 归并排序
function merge_sort(t,p,r)
  if p >= r then
    return
  end
  
  local q = (p+r) // 2
  merge_sort(t,p,q)
  merge_sort(t,q+1,r)
  
  merge(t,p,q,r)
end

下面分析一下归并排序：

空间复杂度：因为每次合并都需要分配额外的内存，所以所以最大需要 n 大小数组，因此空间复杂度为$O(n)$。
时间复杂度：采用主方法来计算时间复杂度：

  1. 首先将递归公式改成主方法要求形式：$T(n)=2T(n/2)+n$,其中 a=2，b=2，f(n)=n。
  2. 然后比较 f(n)=n，与$n^{\log_b^a}$=$n$，两者值相同，满足主定理的第二种情况，所以时间复杂度为：$O(n^{\log_b^a}\log{n})=O(n\log{n})$

快速排序

快速排序的思想是这样，对于待排序的数组A，选定数组中的任意元素作为分区点，然后将小于分区点的元素放到前面，大于分区点的放到后面。排序过程如下：

递归公式如下：

在上面递归式中，q代表分区点，分区点的选取方案有多种，可以选取头元素、尾元素作为分区点，但是更多的是采用随机分区点。根据递归公式写出递归代码:

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
--- 分区点选取
function partition(n,s,e)
  -- 随机分区点选取
  local p = math.random(s,e)
  n[p],n[e]=n[e],n[p]
  p = e
  
  -- 已处理区的尾指针
  local i = s
  for j = s,e do
    if n[j] < n[p] then
      n[i],n[j] = n[j],n[i]
      i = i + 1
    end
  end
  
  if i < p then
    n[i],n[p]=n[p],n[i]
  end
end

--- 快速排序算法
function quick_sort(n,s,e)
  if s >= e then
    return
  end
  
  local p = partition(n,s,e)
  quick_sort(n,s,p-1)
  quick_sort(n,p+1,e)
end

这里需要解释一下分区算法的实现思路，它是将待分区的数组分为“已处理”、“未处理”两部分，已处理部分都是小于分区点的元素，其中 i 相当于已处理区的尾指针（已处理和未处理区的分界点，指向的元素属于未处理区），分区过程通过遍历未处理区，如果元素小于分区点，插入到已处理区（与 i 指向的元素进行交换）,最后将分区点与 i 进行交换。

然后分析一下快速排序：

空间复杂度：快速排序也是原址排序，所以空间复杂度为$O(1)$
是否稳定排序：因为分区过程中，涉及到元素的交换，所以不是稳定的排序
利用主方法还计算快排算法的时间复杂度：

  1. 首先将递归式写成主方法要求的形式：$T(n)=2T(n/2)+n$
  2. 根据上式可知，a = 2，b = 2，f(n)=n。
  3. 比较$f(n)=n$，$n^{\log_b^a}=n$，两者相等，所以时间复杂度为:$n{\log}n$

对于快排来说，分区点的选取尤其重要，如果分区点选取不合适，可能造成每次分区都需要遍历整个数组，时间复杂度就会退化为$O(n^2)$，上面采用随机选取分区点，就是为了降低这种可能性。

总结

算法 时间复杂度 空间复杂度 是否稳定排序
归并排序 $n\log{n}$ $O(n)$ 是
快速排序 $n\log{n}$ $O(1)$ 否