分治策略是：对于一个规模为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();

        }

    }

}

作者：Czhenya

链接：https://czhenya.blog.csdn.net/article/details/78778052

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。