分治算法的简介

分治策略是：对于一个规模为N的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为K个个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原来的问题的解，这种算法设计策略叫做分治法。

分治法的精髓：
分 – 将问题分解为规模更小的子问题；
治 – 将这些规模更小的子问题逐个击破；
合 – 将已解决的子问题合并，最终得出“母”问题的解；

一言以蔽之：分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法求解的几个经典问题：
（1）二分搜索
（2）大整数乘法
（3）快速排序
（4）最接近点对问题
（5）循环赛日程表
（6）汉诺塔

快速排序为例：

图示概要：
一串数字从 5 2 4 6 1 3 2 6 ——> 1 2 2 3 4 5 6 6

代码如下：

using System;

namespace 快速排序
{ class Program { /// <summary> /// 对传入数组中索引从left到right之间的数做排序 /// </summary> /// <param name="dataArray">数组</param> /// <param name="left">要排序的数据的开始索引</param> /// <param name="right">要排序的数据的结束索引</param> static void QuickSort(int[] dataArray, int left, int right) { if (left < right) { int x = dataArray[left];   //基准数，把比他下或者等于他的放在他左边，把比他大的放在右边 int i = left; int j = right;  //用于做循环的标志位 while (i < j)  //当i == j的时候说明，说明我们找到了一个中间位置，这个中间位置就是基准数 { //从后往前比较（右到左）找到一个比x小或者（=）的数字，放在当前i的位置 while (i < j) { if (dataArray[j] <= x) //找到了一个比基准数小于或者等于的数字，应该把它放在x的左边 { dataArray[i] = dataArray[j]; break; } else { j--;  // 向左移动到下一个数字，然后做比较 } } //从前往后比较（左到右）找到一个比x大的数字，放在当前i的位置 while (i < j) { if (dataArray[i] > x) { dataArray[j] = dataArray[i]; break; } else { i++; } } } //----------跳出循环 也就是 i==j了---------------- dataArray[i] = x;   //left  -- i  -- right 分成了两个区间， //递归  left -- i   然后  i -- right  QuickSort(dataArray, left, i - 1); QuickSort(dataArray, i + 1, right); } } static void Main(string[] args) { int[] arr = { 42, 20, 17, 27, 13, 8, 17, 48 }; QuickSort(arr, 0, arr.Length - 1); for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } Console.ReadKey(); } }
}
  
 

  
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
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78778052