分治（未完~持续更新中）_分治法是计算机科学中解决问题的一种基本方法。从字面上来理解就是「分而治之」。

分治

一、分治的定义

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。

二、分治的特征

1.问题缩小到一定规模容易解决

2.分解成的子问题是相同种类的子问题，即该问题具有最优子结构性质

3.分解而成的小问题在解决之后要可以合并

4.子问题是相互独立的，即子问题之间没有公共的子问题

三、方法论

1.分解成很多容易解决的子问题

2.子问题得出的结果如何合并，从而解决整个问题

四、重要应用

分治最重要、最经典的应用无非就是归并排序和快速排序了。

相信有DS基础的玩家都会比较熟悉了

在这里简单介绍一下

1、快速排序

（1）排序思想

通过一趟排序，将待排序记录分割成独立的两部分（两个子问题），其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序（解决整个问题）。

（2）排序算法过程

选基准（Random or first）

swap

（3）实现思路

挖坑填数解决子问题

parameter	In: 		low		 high

init:	i = low			j = high		reference = s[low]

begin:	

​	while(i < j) :

​		if	refer <= s[j]		j := j - 1

​		if	refer > s[j]		s[j] -->  s[i]   i := i + 1

​		if	refer >= s[i]		i : i + 1

​		if	refer < s[i]		s[i] --> s[j]   j :=  j - 1

end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上个代码吧

public void partition(int start, int end) {
        int pivotIndex = start;
        int pivot = nums[pivotIndex];
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] < pivot) {
                i++;
            }
            if (i < j) {
                nums[j --] = nums[i];
            }
            
        }
        nums[i] = pivot;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

当然，要不要考虑一下如何优化？？

基准一定是start的位置吗？？？

不如随机化？？？是不是能提高效率？？？

答案是 能！！！！！而且是大大提高！！！！！！ leetcode亲测有效

（未随机处理 31ms 随机处理4ms）

因此，不妨随机处理一波吧？？

public void partition(int start, int end) {
    	//真 随机选取！！！！！！！！
        int pivotIndex = start + new Random().nextInt(end - start);
        int pivot = nums[pivotIndex];
    
    	//注意交换一下  之前卡住这个坑点好久
        swap(pivotIndex, start);
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] < pivot) {
                i++;
            }
            if (i < j) {
                nums[j --] = nums[i];
            }
        }
        nums[i] = pivot;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

当然，一定要挖坑填数吗？？？

这里再介绍一个方法（与随机挖坑填数差不多）

这里直接上代码吧

希望大家选取自己感兴趣的、容易理解的方法

public void partition(int start, int end) {
    	//随机化选取基准
        int pivotIndex = start + new Random().nextInt(end - start);
        int pivot = nums[pivotIndex];
        swap(pivotIndex, end);
        int swapIndex = start;
        
        for (int i = start; i <= end; i++) {
            if (nums[i] < pivot) {
                swap(i, swapIndex);
                swapIndex++;
            }
        }
        swap(swapIndex, end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分治！！！！！！！！！！！！！！！！

挖坑填数调整s

quick_sort(s, l, i - 1)

quick_sort(s,i + 1,r)

（4）代码实现

比较简单，这里来个违和的c语言吧

重要的技巧都在上面介绍了，这里代码不赘述。

//快速排序
void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                s[i++] = s[j];
        
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2、归并排序

（1）背景

归并排序效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

（2）思想

将两个或两个以上的有序序列合并成一个有序序列。

①初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；

②对所有有序子序列进行两两归并

③重复② ，直到得到长度为n的有序序列为止。

（3）实例

两堆扑克牌，都已从小到大排好序，要将两堆合并为一堆且要求从小到大排序。

◆将两堆最上面的抽出(设为C1，C2)比较大小，将小者置于一边作为新的一堆(不妨设C1<C2)；再从第一堆中抽出一张继续与C2进行比较，将较小的放置在新堆的最下面；

◆重复上述过程，直到某一堆已抽完，然后将剩下一堆中的所有牌转移到新堆中。

（4）代码

    public static int[] divide(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            divide(nums, low, mid);
            // 右边
            divide(nums, mid + 1, high);
            // 左右归并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = nums[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }
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

（5）小练习

在这里想放一个归并排序的简单应用来帮助大家更好理解归并的思想

Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

本题的实现与归并排序可以说是几乎如出一辙。

思路

（1）divide

二分分割，保证两部分都有序

（2）merge

合并两个有序数组。合并方式参考归并排序。这里可以使用递归使算法实现更简单。

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return divide(lists, 0 , lists.length - 1);
    }
    
    public ListNode divide(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode left = divide(lists, start, mid);
        ListNode right = divide(lists, mid + 1, end);
        return mergeTwoLists(left, right);
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
    }
    
}
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

3、快速选择

Problem：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

这是快速排序算法的一个简单变形

大家可以感受一下，相信对分治算法的理解会有很大帮助。

（1）思想

快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。

（2）实现思路

子问题：将小于和大于基准元素的分在左右两边（可以采用上述快排中介绍的两种思路，注意随机选取进行优化！！！！）

分治：

我们只需要一边即可！！！！

quick_select(start, store_index - 1, k) or quick_select(store_index + 1, end, k)

（3）时间复杂度

分治策略中，不递归双边，降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n^2)。

（4）代码实现

注释部分为其他方法，有兴趣可以自己阅读。

class Solution {
    int[] nums;
    
    private void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public int findKthLargest(int[] nums ,int k) {
        this.nums = nums;
        //System.out.println(quickSelect(0, nums.length - 1, nums.length - k));
        return quickSelect(0, nums.length - 1, nums.length - k);
    }
    
    public int quickSelect(int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        int storeIndex = partition(start, end);
        if (k == storeIndex) {
            return nums[storeIndex];
        } else if (k < storeIndex) {
            return quickSelect(start, storeIndex - 1, k);
        } else {
            return quickSelect(storeIndex + 1, end, k);
        }
    }
    
    public int partition(int start, int end) {
        //System.out.println(start);
        //System.out.println(end);
        int pivotIndex = start + new Random().nextInt(end - start);
        int pivot = nums[pivotIndex];
        swap(pivotIndex, start);
        //System.out.println(pivot);
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            //System.out.println(Arrays.toString(nums));
            while (i < j && nums[i] < pivot) {
                i++;
            }
            if (i < j) {
                //swap(i, j);
                //j--;
                nums[j --] = nums[i];
            }
            //System.out.println(Arrays.toString(nums));
        }
        //System.out.println(Arrays.toString(nums));
        nums[i] = pivot;
        //System.out.println(Arrays.toString(nums));
        //System.out.println(i);
        return i;
    }
    
    
    /*public int partition(int start, int end) {
        //System.out.println(start);
        //System.out.println(end);
        int pivotIndex = start + new Random().nextInt(end - start);
        int pivot = nums[pivotIndex];
        swap(pivotIndex, end);
        //System.out.println(pivotIndex);
        //System.out.println(Arrays.toString(nums));
        int swapIndex = start;
        
        for (int i = start; i <= end; i++) {
            if (nums[i] < pivot) {
                swap(i, swapIndex);
                //System.out.println("*" + Arrays.toString(nums));
                swapIndex++;
            }
        }
        swap(swapIndex, end);
        //System.out.println(swapIndex);
        //System.out.println(Arrays.toString(nums));
        return swapIndex;
    }*/
    
    //小顶堆方法
    /*
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            heap.add(nums[i]);
        }
        System.out.println(heap.peek());
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.remove();
                heap.add(nums[i]);
            }
        }
        return heap.peek();
    }*/
    /*public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }*/
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

五、重要问题分析

稍后更新，敬请期待~