深入解析排序算法之——归并排序

2744557306

1 基础介绍
: X/ O/ F( B2 R排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

. L- D  P" q0 W以下是一些常见的排序算法：

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）
6 t% E7 ?- K9 l. E% z
选择排序（Selection Sort）
. y2 J8 S5 T  R7 j6 c/ O
- E, s/ W; D$ m# ?归并排序（Merge Sort）
8 M; p: v: h; i8 G, Y% _6 D
快速排序（Quick Sort）

堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

0 b2 G6 G0 B6 t归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
% ]9 P' \( u9 l4 ~. M& A: E; m( Q
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
* a& k1 t- K5 |' Y  Y3 S
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

! }$ p; d2 `- q/ Z( I比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
+ d" x9 D: i3 w5 M1 J, x( @. O% o) P
0 t: ?2 R; @  ~2 ^6 ?* b) ^7 A9 E重复步骤 2，直到其中一个数组的元素全部放入 C 中。
; E3 J; ]' j5 ]) O( C; U
将另一个数组中剩余的元素放入 C 中。

/ ?* D7 A& E2 I9 g) U4 ^归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
% ^. i/ c( G% J
7 S" s+ l: ~) ]1 J8 E4 x& D4 c# B7 b原理简单示例
$ y! P  R1 p$ x" N9 l: O/ A以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
3 B# c% R) O: h; ?) i3 ]
对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
  }9 i6 H  F# r0 a! C8 i) f
( n9 m5 K$ N) }9 N1 L接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

0 }' A# k# j, H$ k将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 i 指向其起始位置，即 0；对于右半部分，指针 j 指向其起始位置，即 0。比较左右两部分的元素大小，发现左半部分的第一个元素 5 大于右半部分的第一个元素 1，因此将 1 添加到新的数组 sorted_arr 中，并将右半部分的指针 j 向后移动一位。此时，sorted_arr 的内容为 [1]。接着比较左半部分的第二个元素 2 和右半部分的第一个元素 3，发现左半部分的元素较小，因此将 2 添加到 sorted_arr 中，并将左半部分的指针 i 向后移动一位。此时，sorted_arr 的内容为 [1, 2]。接着继续比较左右两部分的元素大小，将它们依次添加到 sorted_arr 中。最终得到排好序的数组 [1, 2, 3, 5, 6]。

因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
  K# @  G+ f$ b. j) z/ h6 Z) v2 S
9 k* W1 {; j& |2 O2 Z, k1.2 复杂度
% N; _9 i4 G3 N7 ~3 N$ ]归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
/ n$ h* b6 x, m; x" d
这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
8 @/ {0 b* v2 `- a
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
# D2 E2 `+ N7 i4 Y
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
- O; U5 \% z" C1 l8 Q  F) I3 J& G- a
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

4 g( @% m, [# F9 M, e对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
* Y: u  Y$ z! ]7 ?! C) a) x
) v4 E5 Q% j" r总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
7 C' T: c- N9 Z- Q
二、代码实现
2.1 Python 实现
( R8 z) O( u6 j以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):8 |  g\" d; u0 Q\" G: w9 N9 G3 t
   
2.     if len(arr) <= 1:
   % o9 D! K$ \8 @+ T( P  k
3.         return arr+ Y) t/ a# H\" [* c, I3 s# `) [
   
4. 
   0 n  n2 W( D/ i- v) u: _) S0 L6 [
5.     # 将数组分成两个部分8 a) h% E; k\" k! M' @$ ]
   
6.     mid = len(arr) // 2
   4 B4 g2 `: V( n8 ~
7.     left_half = arr[:mid]9 f/ d' v* n* e; m
   
8.     right_half = arr[mid:]. y: z. p/ A# Z$ h( `
   
9. 
     w\" B) b( ]  f. o+ y+ J! @- J
10.     # 对左右两部分分别递归调用归并排序+ c; G+ j\" p6 s, x- z
    
11.     left_half = merge_sort(left_half)9 [. d$ j) P  q
    
12.     right_half = merge_sort(right_half)$ K' }/ E) u. e  W
    
13. ; e2 c. q8 r' g5 p) T
    
14.     # 合并左右两部分
    . f; A; o, C) H6 K0 b: s: F' V& D
15.     return merge(left_half, right_half)- R) {. e; M9 d3 D8 Z
    
16. 
    8 \# r- w  ]/ v/ \) }
17. def merge(left_half, right_half):' n* n# l8 v9 q4 |9 L) f( Q# e: H  P
    
18.     i = j = 0
    , d6 R' f( d7 E, {( P/ q  o
19.     merged = []
      K; t, t, }6 _( Z5 A+ T1 F. H. O
20. 2 p* J\" n; z& t& g0 A* M* k
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中3 ?, s& ~4 m7 H9 B& }$ m
    
22.     while i < len(left_half) and j < len(right_half):. a( L' b/ \6 l) B
    
23.         if left_half[i] < right_half[j]:0 q3 C% |: q# C4 ^3 d9 k! ?
    
24.             merged.append(left_half[i])
    6 a2 [, k  l- K- Y- y+ l
25.             i += 1: _0 L7 E7 W: B* J( e  z
    
26.         else:# D3 x* y% y, D. U
    
27.             merged.append(right_half[j])
    ( i\" E; P- T\" I  }& s7 w
28.             j += 1
      R: G3 {, i6 N( y) h
29. 1 l+ p\" v2 n; |% [
    
30.     # 将左右两部分中剩余的元素添加到 merged 中7 m8 d* y$ C, s/ ~1 o7 p
    
31.     merged += left_half[i:]
    % u. v+ L+ n7 H# C
32.     merged += right_half[j:]
    \" D8 g\" ~* _6 @  p
33. 
    : G9 Q7 @4 ^; h7 {0 @
34.     return merged

复制代码

代码讲解

这个实现使用了两个函数，一个是 merge_sort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。下面对这两个函数进行详细讲解：

merge_sort() 函数

1. def merge_sort(arr):' i* U9 B: X8 }! h3 n! U! m
   
2.     if len(arr) <= 1:
     l6 X5 [$ o1 n1 t
3.         return arr1 h! O- M\" `1 i* `
   
4. 
   ' I4 F# _' y) U  c\" p
5.     # 将数组分成两个部分
   : `1 k$ G* E, x! ?
6.     mid = len(arr) // 23 Y6 a8 ?7 ^' s; x; B0 q
   
7.     left_half = arr[:mid]- W# U& d1 S: ]6 U
   
8.     right_half = arr[mid:]* W! r  ]3 e; c- z0 g( {6 w. N
   
9. 8 J0 ?& `) Y7 R8 q7 \) F: ]
   
10.     # 对左右两部分分别递归调用归并排序
    \" l7 g- b5 g  g/ w3 s* K
11.     left_half = merge_sort(left_half)7 h, Q9 D3 Q1 C$ M
    
12.     right_half = merge_sort(right_half)3 x! p2 m\" Q9 p- b
    
13. $ Z* U- O* v$ e* B
    
14.     # 合并左右两部分
    4 @0 x! o9 C8 h1 ^1 q5 M2 k2 ^
15.     return merge(left_half, right_half)
    $ ^/ f. b. x# }: @/ O/ X* T3 F
16. ```
    * \; `' P& t( C2 h' z
17. 
    3 i9 M- x* b9 K) T3 C4 e% a0 D. ?
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。1 `# {+ A, W! j5 ]) W; d. P9 {
    

复制代码

merge() 函数

1. def merge(left_half, right_half):8 h8 b& B% f7 Y
   
2.     i = j = 0- q  O! i: c3 ~( f; ~/ h  G
   
3.     merged = []# B* f$ W+ `+ F. L- ~3 s
   
4. 7 G8 p5 j: ]8 d# |
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
     a/ H7 b  r) F4 R) m' u
6.     while i < len(left_half) and j < len(right_half):
     t* P3 p6 f' J5 Q+ y7 _. V
7.         if left_half[i] < right_half[j]:' S7 w. W& M/ p8 B: i
   
8.             merged.append(left_half[i])9 G7 R. M* E$ O1 }1 n
   
9.             i += 1
   5 N, n  r0 G9 \\" {( t& ?+ q0 a5 Z
10.         else:\" u; R4 V2 k9 ^\" I( A( v( l+ y8 L
    
11.             merged.append(right_half[j])1 ~7 ?/ E% }# F# c$ x
    
12.             j += 13 G. {7 a- q1 R5 q, d* A0 t
    
13. 
    0 x5 B. b& g( |8 |9 e' Q' j
14.     # 将左右两部分中剩余的元素添加到 merged 中
    $ f7 H6 E8 ]: j+ G; ?  ~+ ~% A
15.     merged += left_half[i:], g3 L& g1 {7 H3 U, D1 O
    
16.     merged += right_half[j:]- {\" ^0 h* Z) B5 [
    
17. 
    % W: Q$ ~: r: \$ {) W  d$ t* X. E
18.     return merged9 {% b  Q1 O- N0 E1 U1 _
    
19. ```% [; C7 o7 L  R7 \+ O9 {; e
    
20. 3 ~* K: Y\" B/ I) F! T2 g
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
3 ?% h. X8 v# b8 |( ?
0 ~' `6 B" c& K' ^将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
$ e; c* A+ S1 c& ?) y& U
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
  G( u' q5 d- l7 h
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]# G$ H* u' Y) z6 D  F) |
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。

总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
- D- g/ c( V- ^2 J7 t2 C7 y6 ~2.2Java实现

以下是使用 Java 实现归并排序的代码：

1. public class MergeSort {
   5 \8 t  Q- b. @+ ~- R% f
2.     public static void main(String[] args) {& ~; z# R9 l5 D' H
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   9 \/ m\" `1 ^8 [% E$ X  V6 P
4.         mergeSort(arr, 0, arr.length - 1);; Q! J7 t6 B0 ?6 A7 i
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]* P8 ?9 G6 g- g- ^! x9 ^
   
6.     }  ~! }8 T3 x, E4 t2 s, j
   
7. 
   \" V! `# X: {3 q; T0 m  N
8.     public static void mergeSort(int[] arr, int left, int right) {4 I1 M+ ]% o' N, o
   
9.         if (left >= right) {
   ! }  K8 I& Q3 i: Q
10.             return;' Z5 n* i: s6 R# S& N/ |5 k8 n
    
11.         }* h+ C3 u( d) w\" w- B
    
12. 
      l2 k* g5 z  W, k/ p
13.         int mid = (left + right) / 2;
    : m: j- e; t# @1 ]
14.         mergeSort(arr, left, mid);6 l8 o+ r+ @1 `- P& \9 C
    
15.         mergeSort(arr, mid + 1, right);: j6 r$ {4 a, G8 N* {
    
16.         merge(arr, left, mid, right);! ]; }/ Y5 F7 s( a  T( m9 R$ U
    
17.     }, Z- N8 ~$ Q1 L  s* c( U
    
18. 
    - a1 v2 I+ C9 W$ X1 r; I
19.     public static void merge(int[] arr, int left, int mid, int right) {0 w' ^0 j6 ], ^3 q3 A2 n4 c9 o0 a8 m
    
20.         int[] temp = new int[right - left + 1];
    7 M7 {6 G: ?. r' m
21.         int i = left, j = mid + 1, k = 0;
    & w$ S5 n- w6 ?! U  @( r
22. 
    7 d9 g0 B. f0 A9 a% l' F% ^
23.         while (i <= mid && j <= right) {
    & e4 u3 ^( @6 o9 _, z1 k# A, z
24.             if (arr[i] < arr[j]) {% Y7 d; X8 o& N8 k
    
25.                 temp[k++] = arr[i++];
    5 x1 [' X$ Y! g5 u0 t1 o% T
26.             } else {
    + v\" E' q8 Z0 j! h9 ]
27.                 temp[k++] = arr[j++];
    + \5 |2 J, I8 F0 ]/ i/ R6 o\" @/ X
28.             }
    \" r\" O# G/ h( d0 w; A
29.         }
    # }4 t+ _! D( ^4 O) v& U
30. $ n& r% o: p' A8 t
    
31.         while (i <= mid) {9 Y7 A& d% O: \5 _- w1 ]- k7 c
    
32.             temp[k++] = arr[i++];) A6 z% l$ Z( d: E3 U
    
33.         }
    2 l\" P% N$ ~& a7 M- F3 Y1 b0 k; _0 I
34. 1 R1 h& M7 k5 m% K: e/ T# p
    
35.         while (j <= right) {) E+ T: \\" y& n2 ]2 Y
    
36.             temp[k++] = arr[j++];) m) y/ K; U* P
    
37.         }
    9 o  T\" p: ]8 I' J
38. 2 X\" x0 M( f( f5 K
    
39.         for (int m = 0; m < temp.length; m++) {
    * ^$ [: i4 G/ `: q5 l8 _9 R' t
40.             arr[left + m] = temp[m];( Q& g7 Q: M( w% j+ w
    
41.         }$ M( n- v6 r# O
    
42.     }
    ) _- o& {% z% }7 r
43. }

复制代码

这个实现也使用了两个函数，一个是 mergeSort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。

下面对这两个函数进行详细讲解：

+ C2 Y; O& g) P2 imergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   , s; j! `5 P$ D8 B- p4 D
2.     if (left >= right) {
   # G& {: n5 l* U! _
3.         return;5 W5 u+ J4 y# Z
   
4.     }+ C' B( w* Z% p3 k6 D
   
5. 3 Q  g+ b7 M9 {
   
6.     int mid = (left + right) / 2;* N1 v! z  {; D* I. O4 }
   
7.     mergeSort(arr, left, mid);) Z! B+ `4 O# g# i) C
   
8.     mergeSort(arr, mid + 1, right);, c* Q\" ?2 H5 l0 _
   
9.     merge(arr, left, mid, right);
   2 L- J: _- w7 P' j2 t$ \\" `8 i
10. }
    4 y6 s4 n, N- [( R) b\" y* @9 l7 r0 {
11. 
    $ ^# V* F, L* G2 k8 D/ f/ z

复制代码

这个函数使用递归的方式对数组进行排序。

& n. W; g( @' W# K8 ]$ }对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

  a* `3 ~5 b4 j/ l最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
. X; S/ @1 Z; K4 L! m! j+ ]merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   ' U# Q1 d' V' b- H8 Y, C
2.     int[] temp = new int[right - left + 1];8 e( s4 V1 [1 ~3 k: Q! i; r/ u
   
3.     int i = left, j = mid + 1, k = 0;
   5 @, W! _8 Y8 ?& c3 n0 Z8 t: j
4. 
   7 t: M3 b4 t\" j5 ]$ D/ U0 j- D& S
5.     while (i <= mid && j <= right) {8 B( s. H  b2 C9 e% R
   
6.         if (arr[i] < arr[j]) {
   % E. b5 c0 m- }3 ^' j# x: F( o, v
7.             temp[k++] = arr[i++];3 A. J% e. @( L- K% U' i) b3 x
   
8.         } else {6 F3 z. n  A7 v! p) K
   
9.             temp[k++] = arr[j++];
   0 [  t7 l9 s, w5 t' G* q
10.         }; M$ q1 i. K0 d/ ~6 O+ Q  c7 C) i
    
11.     }: V% t) z3 P1 s  G
    
12. 
    & m( Q: E; }, p
13.     while (i <= mid) {* y$ E* P  V2 r6 g' C* y9 N\" V7 b( R
    
14.         temp[k++] = arr[i++];7 B' \9 R7 p; I  [+ W6 X
    
15.     }
    0 D- Q2 j% G; g4 T- A  _7 K7 N
16. 5 K\" w. |% P5 z. t/ i- Q( @; w' a
    
17.     while (j <= right) {
    / ]( ]6 j\" C7 r0 D# p! A
18.         temp[k++] = arr[j++];
    / W# C8 z4 T7 o4 ^
19.     }
    7 A& e6 S) j+ P7 V) ?
20. 
    ) o' Y6 G) a. |* c
21.     for (int m = 0; m < temp.length; m++) {
    1 ]8 \+ B4 k1 I/ n3 B- y' c
22.         arr[left + m] = temp[m];) K# @# C0 c- @5 c
    
23.     }
    ; U\" G, l  h' }
24. }
    ; S1 s! s  T) `2 I5 {

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
' s0 r. ]$ ]7 Q( G2 [2 D
6 g  `& w5 U+ L  l3 d6 f0 U" {合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
4 ^  }  `/ c/ ^' C
) n( K( ~0 `# p, p6 z最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
" s, _; `6 d, @, O$ o/ C5 C0 H) W
6 }8 M% G, ]/ k) w; k* o( g需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
" X3 K2 |0 ]* Z, x+ o
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。



! |1 o- j* W( ^# b8 w


1 {* z& q3 r2 E- E+ ]
1 [* V9 V0 z# u' S% U