[数据结构与算法]算法基础部分2-分治

算法部分 基础2

一、算法例子

??这章节主要学习分治相关知识，因为这是最基础的二分查找和检查排序，后面进行深入学习。这些算法需要搞的特别清楚，倒背如流，以前学习过一遍，但是没有记录，这次再看看，把没理解的再理解理解。
??分治的概念和描述： 把一个任务，分成形式和原任务相同，但规模更小的几个部分任务 (通常是两个部分) ，分别完成，或只需要选一部分完成。然后再处理完成后的这一个或几个部分的结果，实现整个任务的完成。
??分治问题分为两个步骤，一个是分：把大问题分为小问题求解；一个是治：把每一个阶段分得到的问题进行整理求解。

1. 二分法查找(找一对数 农夫和牛)

??在 1. C++基础知识学习到深入理解及其部分算法学习 里面学过了，后来又温习了一遍。后面刷题注意灵活应用和一些更难度的查找学习。
??例题 1：输入 n (n <= 100, 00) 个整数，找出其中的两个数，他们之和等于整数 m (假定肯定有解)。题中所有整数都能用 int 表示。

比较不错的一种解法：
1. 将数组排序，复杂度是 O(n*logn)
2. 查找的时候，设置两个变量 i 和 j 初值是 0 ，j 初值是 n-1 . 看 a[i]+a[j],
如果大于 m ，就让 j 减 1 ，如果小于 m ，就让 i 加 1 ，直到满足a[i]+a[j] = m 停止

这种解法总的复杂度是 O(n*log(n))的。

方法比较简单，就不直接写。排序算法选择快速排血或堆排序，下面会学到。
??例题 2：农夫 John 建造了一座很长的畜栏，它包括 N (2 <= N <= 100,000) 个隔间，这些小隔间位置为 $x_0,x_1,...,x_{n?1}(0<=x_i<=10^{10})$ 他们均为整数，各不相同。
??John 的 C (2<= C <= N) 头牛每头分到一个隔间。牛都希望互相离得远点省的互相打扰。怎样才能使任意两头牛之间的最小距离尽可能大，这个最大最小距离是多少呢？
分析：

1. 先得到排序后的隔间坐标 x(0), x(1), ... x(n-1).
2. 在 [L, R] 内用二分法尝试 "最大最近距离" D = (L+R)/2 (L, R 初值为 1 和 10^10/C)
3. 若 D 可行, 则记住该 D, 然后在新的[L, R] 中继续尝试(L = D + 1), 若 D 
不可行，则在新的[L, R] 中继续尝试 (R = D - 1).

复杂度为 log(10^10/C)*N

2. 归并排序(分治思想)

??数组排序任务可以这样完成：1. 把前一半排序；2. 后一半排序；3. 把两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。
??程序如下，

#include <iostream>

using namespace std;

int a[10] = {13, 27, 19, 2, 8, 12, 2, 8, 30, 89};
int b[10]; // 备用数组，存过程中的数据

void Merge(int a[], int s, int m, int e, int temp[]){
    // 将数组 a 的局部 a[s, m] 和 a[m+1, e] 合并到 temp,
    // 并保证 temp 有序，然后再拷贝 a[s, m], 归并时间复杂
    // 度：O(e-m+1), 是 O(n) 的
    int pb = 0;
    int p1 = s, p2 = m + 1;
    // 可以理解作前面部分和后面部分比较
    while( p1 <= m && p2 <= e ){
        if( a[p1] < a[p2] )
            temp[pb++] = a[p1++];
        else
            temp[pb++] = a[p2++];
    }
    // 已经取完的那个就不用考虑了
    while( p1 <= m )temp[pb++] = a[p1++];
    while( p2 <= e )temp[pb++] = a[p2++];
    for(int i = 0; i < e-s+1; i++){
        a[s+i] = temp[i];
    }
}
void mergeSort(int a[], int s, int e, int temp[]){
    if(s < e){
        int m = s + (e - s) / 2;
        mergeSort(a, s, m, temp);
        mergeSort(a, m+1, e, temp);
        Merge(a, s, m, e, temp);
    }
}

int main(){
    int Size = sizeof(a)/sizeof(int);
    mergeSort(a, 0, Size-1, b);
    for(int i = 0; i < Size; i++)
        cout << a[i] << ",";
    cout << endl;

    return 0;
}

??运行结果如下，

??从分治思想来实现递归程序，先分，分到最后不可以分的时候再进行整理，所以程序理解如下。

??上面的图片一定有些杂乱，继续按照入栈出栈的角度来理解，从而理解了分治的根本思路。

3. 快速排序(分治的典型应用)

??思路：数组排序任务可以如下完成，设 k = a[0] ，将 k 挪到适当的位置，使得比 k 小的元素都在 k 的左边，比 k 大的元素都在 k 右边，和
k 相等的，不关心在 k 左右出现均可( O(n) 时间完成)；把 k 左边的部分快速排序；把 k 右边的部分快速排序。举个快速排序的例子，

举个例子，奇数次交换 i++ ，偶数次交换 j--
k = 7 划分数字
i               j
7 1 3 8 12 11 2 9
偶数次交换 0 次交换

i             j  
2 1 3 8 12 11 7 9
奇数次交换 1 次交换，i++ 4 次

      i       j  
2 1 3 7 12 11 8 9
偶数次交换 2 次交换，j-- 3 次

      ij        
2 1 3 7 12 11 8 9
第一次划分结束

??程序如下，

#include <iostream>

using namespace std;

int a[10] = {13, 27, 19, 2, 8, 12, 2, 8, 30, 89};

void swap(int & a, int & b){
    int temp = a;
    a = b;
    b = temp;
}
void quickSort(int a[], int s, int e){
    if( s >= e )return ;
    int k = a[s];  // 第一个数作为标注
    int i = s, j = e;
    while( i != j ){
        while( j > i && a[j] >= k )j--;
        swap( a[i], a[j] );
        while( i < j && a[i] < k )i++;
        swap( a[i], a[j] );
    } // 处理完成以后，a[i] = k
    quickSort( a, s, i-1 );
    quickSort( a, i+1, e );
}

int main(){
    int Size = sizeof(a)/sizeof(int);
    quickSort(a, 0, Size-1);
    for(int i = 0; i < Size; i++)
        cout << a[i] << ",";
    cout << endl;

    return 0;
}

??运行结果为，

??当划分到只剩下一个数的时候递归返回上一层，并且之前的数据都已经排好序了，那样就所有都排序完成。

4. 输出前 m 大的数(分治的应用)

??描述：给定一个数组包括 n 个元素，统计前 m 大的数并且把 m 个数从大到小输出。
??分析

排序后再输出，复杂度 O(nlogn)
用分治处理，复杂度 O( n + mlogm )

思路：
把前 m 大的都弄到数组最右边，然后对最右边 m 个元素进行排序，再输出。

方法：
引入操作 arrangeRight(k): 把数组(或数组一部分)前 k 大的都弄到最右边
如何将前 k 大的都弄到右边
1. 设 key = a[0], 将 key 挪到适当的位置，使得 key 小的元素都在 key 的左边，比 key 大的元素都在 key 右边(线性时间完成)
2. 选择数组的前部或者后部再进行 arrangeRight 操作

因为视频里没有程序，不看上面程序，按照理解自己试着写写，程序如下，

#include <iostream>

using namespace std;

int a[10] = {13, 27, 19, 2, 8, 12, 2, 8, 30, 89};
int Size = sizeof(a) / sizeof(int);

void Swap(int & a, int & b){
    int temp = a;
    a = b;
    b = temp;
}
void arrangeRight(int a[], int s, int e, int k){
    if(s >= e)return ;
    int key = a[0];
    int i = s, j = e;
    while(i != j){
        while(i < j && a[j] > key)j--;
        Swap(a[j], key);
        while(i < j && a[i] <= key)i++;
        Swap(a[i], key);
    }
    if(i > Size - k){
        arrangeRight(a, s, i - 1, k);
    }
    else{
        arrangeRight(a, i + 1, e, k);
    }
}

int main(){

    int k = 4;
    // cin >> key;
    arrangeRight(a, 0, Size-1, k);
    for(int i = Size-1; i > Size - k - 1; i-- ){
        cout << a[i] << " ";
    }
    cout << endl;
}

按照思路写了一下程序，运行结果如下，

输出前 5 个大的程序，如果要输出前 m(值) 大的程序改为 a[i] 和 k 值比较即可。

5. 求排列的逆序数(分治的应用)

?? 题目描述：考虑 1, 2, … n (n <= 10^6 ) 的排列 $i_1,i_2,...,i_n$ ，如果其中存在 j, k, 满足 j < k 且 $i_j>i_k$ 是这个排列的一个逆序。
?? 举个例子，一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有 8 个逆序 (2, 1), (6, 3), (6, 4), (6, 5), (6, 1), (3, 1), (4, 1), (5, 1), 因此该排列的逆序数就是 8 . 现在给定 1, 2, 3, …, n 一个排列，求它的逆序数。不理解，看下面这个例子，

求排列32514的逆序数是多少。

解题过程（对32514依次分析）：
1、3后面比它小的数有2个。
2、2后面比它小的数有1个。
3、5 后面比它小的数有有2个。
4、1 后面比它小的数没有。
5、4 后面比它小的数没有。

最后将这些个数加起来就是 2 + 1 + 2 = 5，所以逆序数是 5 。

?? 因此思路如下，

分治思路：O(n log n):
1. 将数组分为两半，分别求出左半边的逆序数和右半边的逆序数；
2. 再算有多少逆序数是由左半边取一个数和右半边取一个数构成(要求 O(n) 实现)

第二步实现的关键，(要求 O(n) 实现)
左半边和右半边都是排好序的。比如，都是从大到小排序的。这样，左右半边只需要从头到尾各扫一遍，就可以找出由两边各取一个数构成的逆序的个数。
举个例子，对两边排好序
i          j
10 8 7 3 | 12 11 5 2
12 > 10, 11 > 10, 5 < 10, 小于的后面全部是 10 的逆序数

   i             j
10 8 7 3 | 12 11 5 2
小于的后面全部是 8 的逆序数

     i           j
10 8 7 3 | 12 11 5 2
小于的后面全部是 7 的逆序数

       i         j
10 8 7 3 | 12 11 5 2
5 > 7, 2 < 3 小于的后面全部是 3 的逆序数
从而实现 O(n) 的要求

总结：
由归并排序改进得到，加上计算步骤
mergeSortAndCount: 归并排序并计算逆序数

?? 因为视频没有程序，自己写了试试，程序如下，

二、总结

??还剩两个小例子，明天补上。