分治策略：是将规模较大的问题分割成为规模较小的子问题。==“问题不变，规模减小”==这是分治策略的核心思想。
分治策略可以解决的问题具有一下特点：
- 该问题缩小到一定的规模很容易求解
- 该问题可以分解为若干个规模较小的子问题
- 使用较小规模的子问题，可以合并成该问题原规模的解
- 该问题分解出的子问题之间是相互独立的
举个简单的例子，现在有50000项任务需要一个项目组去完成，似乎听起来很难很快完成，但是，当这个项目组中有200个成员时，安排第1个成员去完成前250个任务，第2个成员完成接下来的250个任务，这样200个成员同时负责自己的任务，当一个成员完成任务的时候，也就意味着总任务已经完成了。这就是，“缩小规模，分而治之”。
在常用的排序算法中，快排的算法思想就是分治的思想，当数组中从某个数之前的都比他小，后面的都比他大时，我们就可以分开来再进行这样的排序了，直至只剩下一个数（那也就不用排了），排到这里，整个数组也就有序了。
算法思想演示：
选定某次递归数组的起始下标位置的值作为基准值key，从right下标开始，一直向前移动，直到遇到一个比key值小的，停下来，将此right位置直接覆盖原基准开始位置的值，然后，left从起始位置开始向后移动，直到遇到一个大于key的位置，将次left位置填入刚才right位置处，以此类推，在保证left
下面，看看具体的实现：（C++实现）
#include问题:#include #include #include #include #include #include #include
如果数组中的数据有序呢？快排会变慢吗？为什么呢？怎么解决？
数据有序时会变慢，比如这样：
这样的话，每次比较就是n,n-1,n-2… 累加后就是O(n^2)。所以，我们可以事先调整策略，比如，可以考虑随机化一下，这样总不会每次都是全部有序的情况了。
解决方法有两种：
- 随机化法：随机选择下标与0下标元素互换
实现如下：
int RandPartion(int* ar, int left, int right)//随机化法
{
//srand(time(NULL));
int pos = rand() % (right - left) + left;
std::swap(ar[left], ar[pos]);
return Partition(ar, left, right);
}
- 三位数取中法：即在数组第一个位置、中间位置和最后一个位置中选择值是中间大小的那个值作为基准
实现如下：
int MidPartion(int* ar, int left, int right)
{
int mid = (right - left) / 2 + left;
struct IndexNode
{
int key;
int index;
operator int() const { return key; }
};
struct IndexNode KL = { ar[left],left };
struct IndexNode KM = { ar[mid],mid };
struct IndexNode KR = { ar[right],right };
std::priority_queue hp;//优先队列，第二个则是中间值
hp.push(KL);
hp.push(KM);
hp.push(KR);
hp.pop();
struct IndexNode pos = hp.top();
std::swap(ar[KL.index], ar[pos.index]);
return Partition(ar, left, right);
}
这里使用到了优先队列priority_queue，就理解为是具有优先级的一个队列，优先级高的值总是在队头处，那么我们需要找中间值，即在全部入队之后，出一次队列即可，此时队头就是中间值了。
可以不从两边向中间逼近划分吗？要是要求从左到右只遍历一次呢？
可以。设置双指针，i 和 j，双指针始终增长，使得i指针之前的数据都比本次划分的基准值小，i 和 j 之间的数据值都比基准值大，最后当 j 指针指向最后时， i 指针位置就是基准值的位置，返回 i。
实现如下：
int Partition(int* arr, int left, int right)//单向逼近
{
int key = arr[left];
int i = left, j =left+1;
while (j <= right)
{
if (arr[j] < key)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
++i;
}
++j;
}
arr[i] = key;
return i;
}
如果是对链表数据进行快排呢？
实现如下：
typedef int ElemType;
typedef struct ListNode
{
ElemType val;
ListNode* next;
}ListNode;
ListNode* Partition(ListNode* head, ListNode* tail)
{
ListNode* p = head, * q = head;
int key = head->val;
while (q != tail)
{
if (q->val < key)
{
p = p->next;
swap(p->val, q->val);
}
q = q->next;
}
swap(p->val, key);
return p;
}
ListNode* Quick(ListNode* head, ListNode* tail)
{
if (head == tail) return head;
ListNode* mid = Partition(head, tail);
head = Quick(head, mid);
Quick(mid->next, tail);
return head;
}
ListNode* QuickSort(ListNode* head)
{
if (head == NULL || head->next == NULL) return head;
return Quick(head, nullptr);
}
总结
“问题不变，规模变小，分而治之是核心”。
