给定N个项目的数组,Merge Sort将:
1.将每对单独的元素(默认情况下,已排序)合并为2个元素的排序数组(Merge each pair of individual element (which is by default, sorted) into sorted arrays of 2 elements,

2.将每对2个元素的排序数组合并为4个元素的排序数组, 重复这个过程...,(Merge each pair of sorted arrays of 2 elements into sorted arrays of 4 elements, Repeat the process...,

3.最后一步:合并2个N / 2个元素的排序数组(为了简化本讨论,我们假设N是偶数)来获得N个元素的完全排序数组。(Final step: Merge 2 sorted arrays of N/2 elements (for simplicity of this discussion, we assume that N is even) to obtain a fully sorted array of N elements.

This is just the general idea and we need a few more details before we can discuss the true form of Merge Sort.


我们首先讨论归并排序算法的最重要的子程序:O( N )归并,然后解析这个归并排序算法。
We will dissect this Merge Sort algorithm by first discussing its most important sub-routine: The O(N) merge.

给定两个大小为 N1 和 N2 的排序数组 A 和 B,我们可以在O( N ) 时间内将它们有效地归并成一个大小为 N = N1 + N2的组合排序数组。
Given two sorted array, A and B, of size N1 and N2, we can efficiently merge them into one larger combined sorted array of size N = N1+N2, in O(N) time.

这是通过简单地比较两个阵列的头部并始终取两个中较小的一个来实现的。 但是,这个简单但快速的O( N )合并子例程将需要额外的数组来正确地进行合并。
This is achieved by simply comparing the front of the two arrays and take the smaller of the two at all times. However, this simple but fast O(N) merge sub-routine will need additional array to do this merging correctly. See the next slide.

-----子程序代码实现:

void merge(int a[], int low, int mid, int high) {
  // subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
  int N = high-low+1;
  int b[N];        // discuss: why do we need a temporary array b?
  int left = low, right = mid+1, bIdx = 0;
  while (left <= mid && right <= high)       // the merging
    b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
  while (left <= mid) b[bIdx++] = a[left++];       // leftover, if any  ※...它解决了我的疑问
  while (right <= high) b[bIdx++] = a[right++];       // leftover, if any
  for (int k = 0; k < N; k++) a[low+k] = b[k];       // copy back

Before we continue, let's talk about Divide(划分) and Conquer(合并) (abbreviated as D&C), a powerful problem solving paradigm.

Divide and Conquer algorithm solves (certain kind of) problem — like our sorting problem — in the following steps:
    1.Divide step: Divide the large, original problem into smaller sub-problems and recursively solve the smaller sub-problems,
(将较大的原始问题划分为较小的子问题,并递归地解决较小的子问题,)
    2.Conquer step: Combine the results of the smaller sub-problems to produce the result of the larger, original problem.
(结合较小子问题的结果,以产生较大的原始问题的结果。)

Merge Sort is a Divide and Conquer sorting algorithm.  

(归并排序是一种分而治之的排序算法)

The divide step is simple: Divide the current array into two halves (perfectly equal if N is even or one side is slightly greater by one element if N is odd) and then recursively sort the two halves.(划分步骤很简单:将当前数组分成两半(如果N是偶数则完全相等,或者如果N是奇数,则一侧稍微大一个元素)然后递归地对两半进行排序。)

The conquer step is the one that does the most work: Merge the two (sorted) halves to form a sorted array, using the merge sub-routine discussed earlier.(合并步骤则是最有效的:使用前面讨论的合并子例程合并两个(已排序)的一半以形成一个有序数组。)

C++实现:

void mergeSort(int a[], int low, int high) {
  // the array to be sorted is a[low..high]
  if (low < high) {      // base case: low >= high (0 or 1 item)
    int mid = (low+high) / 2;    
    mergeSort(a, low  , mid );   // divide into two halves (分成两半)
    mergeSort(a, mid+1, high);    // then recursively sort them(然后递归地对他们进行排序)
    merge(a, low, mid, high);   // conquer : the merge subroutine (合并子程序)
  }
}

from:
     https://visualgo.net/en/sorting?slide=10

     枚举算法(穷举法),就是按照问题本身的性质,一一列举出该问题所有可能的解,并在列举的过程中, 逐一检验 每个解是否就是真正的解。 若是,则采纳这个解;否则抛弃它。
注意:
    · 不能遗漏,否则可能导致结果不正确(边界与特殊值检查、容易挖坑)

    · 不能重复 ,否则可能导致效率比较低 (优化的意义)

 特点:1.枚举的解准确而全面
           2.实现简单 (通过循环/递归实现)
           3.执行效率提升空间往往比较大

枚举三步:  
         1.确定枚对象 枚举对象可以理解为问题解的表达形式,一般需要用若干个参数(p1,p2,...pk)来描述
     · 参数之间要 相互独立 ,而且,参数的数目越少(求解变量的数目越少)、问题解的搜索空间的维度也相应地小。
    ·每个参数 取值范围 越小,问题解的搜索空间也越小(尽可能的减小范围)

         2.逐一列举可能解 根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况。

         3.逐一验证可能解 根据问题解的要求,一一验证枚举对象表达式的每一个取值,如果满足条件,则采纳它,否则,抛弃之。

--

例1:模糊数字问题

(原始)1.  一个5位数、百位数看不清(百位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

    输入: 每一行对应一个测试样例,每一行包含四个数字,依此是万位数,千位数,十位数和个位数。  最后一行包含四个 -1 ,表示输入结束。
    输出:每组测试样例的结果输出占一行,第一个数字表示满足条件的编码的个数,后面按照升序输出所有满足条件的编码,数字与数字间用空格隔开。

解:    记百位为h、百位数字可能是0~9,逐一例举 即 for(h=0;h<=9;h++);
    逐一验证 即 if(((19095+100*h)%57 )== 0 && (19h95%67 == 0))
    

(进阶)2.    一个5位数、万位和百位数看不清(万位、百位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

输入: 每一行对应一个测试样例,每一行包含四个数字,依此是万位数,千位数,十位数和个位数。  最后一行包含3个 -1 ,表示输入结束。
    输出:每组测试样例的结果输出占一行,第一个数字表示满足条件的编码的个数,后面按照升序输出所有满足条件的编码,数字与数字间用空格隔开。

解:    百位为h、万位为m, 百位0~9、万位1~9;(双层for循环)(经试验:)
    逐一验证....if()

(再改)3.  一个5位数、末尾是95、万位百位和百位数看不清(万位、百位、千位模糊)知道是一个57和67的倍数、输出所有满足这些条件的五位数,并统计这样数的个数。

解:    万位、千位、百位分别为 d1,d2,d3;  逐一列举(三层for)
    for(d1=1;d1<10;d1++)   //万位1~9
      for(d2=0;d2<10;d2++)
        for(d3=0;d3<10;d3++)
    逐一验证   d110000+d21000+d3*100+95 能否整除 56 & 57 。

方法2(优化) :  前三位数字记为 d ,d=100~999;
    逐一列举  for(d=100;d<=999;d++);
    逐一验证  d*100 + 95 能否整除 56 & 57

代码实现(类似模板方式):

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int d1,d2,d4,d5,h,myValue=0;
    int myCount=0;
    int  allResult[10];  //最多有10个,节约空间 
    scanf("%d%d%d%d",&d5,&d4,&d2,&d1);
         while(d5!=-1){
             myCount=0;
             for(h=0;h<10;h++){   //枚举 
                 myValue = d5*10000+d4*1000+d2*10+d1+h*100;
                 if((myValue%57==0)&&(myValue%67==0))  //验证
                  {
                      allResult[myCount] = myValue;
                      cout<<myValue;
                      myCount++;   //这种位置顺序会导致多一位 
                  }
             }
             cout<<myCount<<endl;  //个数(有几种)
             for(int i=0;i<myCount;i++){   //因为16行,所以是 < myCount而不是 <=  
             cout<<allResult[i]; }  //

             printf("\r\n");   // \r是制表符,enter上方是\ 
             cin>>d5>>d4>>d2>>d1; //务必和第一次输入顺序一样 
    }
    return 0;
}

优化(整理)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int d1,d2,d4,d5,h,myValue=0;
    int myCount=0;
    int  allResult[10];  //最多有10个,节约空间 
//    scanf("%d%d%d%d",&d5,&d4,&d2,&d1);
         while(scanf("%d%d%d%d",&d5,&d4,&d2,&d1) && (d5!=-1)){
             myCount=0;
             for(h=0;h<10;h=h+1){   //枚举 
                 myValue = d5*10000+d4*1000+d2*10+d1+h*100;
                 if((myValue%57==0)&&(myValue%67==0))  //验证
                  {
                      allResult[myCount] = myValue;
            //          cout<<myValue;
                    
            //        cout<<myCount;
                      myCount++;   //这种位置顺序会导致多一位 
                  }
            //      cout<<h;
            
             }
             cout<<myCount<<endl;
             for(int i=0;i<myCount;i++){   //因为16行,所以是 < myCount而不是 <=  
             cout<<allResult[i]; }

             printf("\r\n");   // \r是制表符,enter上方是\ 
//          scanf("%d%d%d%d",&d5,&d4,&d2,&d1); //务必和第一次输入顺序一样 
    }
    return 0;
}

模板是 c++ 最重要的特性之一,模板函数、模板类、类中的模板函数、类中的模板类、模板类中的模板类等等,可以写出太多强大的代码,这也是模板的魅力所在,而 STL 就是基于模板的,所以各种意义上都有必要掌握模板的基本用法。

引用《c++ primer》, 《STL 源码解析》

                                                 ※ 使用模板的目的就是能够让程序员编写与类型无关的代码。※

比如C++编写了一个交换两个int类型的swap函数,这个函数就只能实现int型,对double、char真相类型就无法实现,要实现这些类型的交换就要重新编写另一个swap函数。而使用模板的目的就是要让这些程序的实现与类型无关。比如让一个swap模板函数既可以实现int型,又可以实现double型的交换。
 (模板是相对于编译器而言,顾名思义就是向编译器提供一个处理事务的模板,以后需要处理的东西,如果都是这个事务类型、那么统统可以用这个模板处理。)

模板编程是 STL 的基石,也是 c++11 的核心特性之一。

1.函数模板的基本语法如下:
template <typename/class T>   (T为形参名,换个字母也可以)

模板函数即
template <typename/class 形参名,typename/class 形参名.....>  返回类型 函数名(参数列表)
{
    函数体
}

其中template和class是关键字,class可以用typename 关键字代替,在这里typename 和class在使用上没有区别,<>括号中的参数叫模板形参,模板形参和函数形参很相像,模板形参不能为空。一但声明了模板函数就可以用模板函数的形参名声明类中的成员变量和成员函数,即可以在该函数中使用内置类型的地方都可以使用模板形参名。
※比如swap的模板函数形式为:

template <typename T> void swap(T& a, T& b){},

当调用这样的模板函数时类型T就会被被调用时的类型所代替,比如swap(a,b)其中a和b是int 型,这时模板函数swap中的形参T就会被int 所代替,模板函数就变为swap(int &a, int &b)。而当swap(c,d)其中c和d是double类型时,模板函数会被替换为swap(double &a, double &b) ;
例2:

template<tempname T>   
  T add(const T lva ,const T rva)       //const修饰函数参数,传递过来的参数在函数内不可改变
  {   T a;      a = lva + rva;
      return a;   }

 我们可以写出add(1,2) 这样的函数,也可以写出add(2.5,4.6)这样的函数,向 add 函数提供参数时,编译器会自动分析参数的类型,然后将所有用到 T 定义的换成相对性的类型;(※但如果我们使用add(1,2.0)是会报错的,因为编译器无法找到add(int,double)  )


 基本语法:

template <class 形参名,class形参名,...>  class 类名
{ ... };

例子:

1.

template <class T>
class Myclass 
{
    T a;
    public : 
        T add(const T lva ,const T rva);
};

2.

template <class T> 
T Myclass<T>::add(const T lva, const T rva)
{
    a = lva + rva;
    return a;
}

关于类模板的使用:类模板的使用实际上是将类模板实例化成一个具体的类
它的格式为:类名<实际的类型>
即,上面那个是个简单且经典的类模板,但在程序中给出的模板并不能使用它,还必须实例化出一个具体的类,
比如:    Myclass<int> A;    //用int实例化一个类A
    Myclass<double> B;    //用double实例化一个类B

模板类是类模板实例化后的一个产物,(说个具体点的例子吧,我们把类模板比作是一个做饼干的模子,而模板类就是用这个模子做出来的饼干,至于这个饼干是什么味道的就要看你自己在实例化时用的是什么材料了,你可以做巧克力饼干,也可以做牛奶饼干,这些饼干出了材料不一样外,其它的东西都是一样的了。)


3.成员模板

模板的使用范围是广泛的,不仅可以用作函数模板,类模板,还可以用作 class ,struct ,template class 的成员。而要实现 STL 这是我们必须掌握和使用的特性。我们先看一个简单的例子,用上面的类改编而来:

template <class T>
class Myclass
{
    public :
        T a;
        template <typename type_1, typename type_2>  //
         type_1 add(const type_1 lva ,const type_2 rva);    //成员作模板
};

template <class T>
    template <typename type_1 ,typename type_2>
type_1 Myclass<T>::add(const type_1 lva, const type_2 rva)
{
    a = lva + rva;
    return a;
}

在类的声明中使用了一个嵌套的模板声明。且通过一个作用域运算符::指出add是类的成员。

(需要注意的一点,有些编译器不支持模板成员,而有些编译器不支持在类外定义。我们默认大家的编译器都支持。模板如此强大,甚至能够允许我们在模板类中再建立模板类)


4.模板中的静态成员

我们知道,在类中定义的静态成员是存储在静态区中,被所有类对象共享,并不属于某一个类所有,同样的,在模板类中的静态成员也不会被复制多份,而是被同类实例化的类对象共享,比如所有 int 和所有 double 的类对象,享有相互独立的静态变量。也可以说是编译器生成了 int 和 double 两个版本的类定义。


※ 5.关于 typename 和 class

typename和class是模板中经常使用的两个关键词 ,在模板定义的时候没有什么区别。以前用的是 class,后来 c++ 委员会加入了 typename。因为历史原因,两个是可以通用的。对有些程序员来说,在定义类模板的时候,常常使用 class 作为关键字,增加代码可读性。其它则用 typename,上面的代码大都遵循这样的标准,但是并无强制规定。
那么如果二者并没有差别,为什么还要再加入typename呢?因为在 c++ 中,允许我们在类中定义一个类型别名,且使用的时候和类名访问类成员的方法一样。这样编译器在编译的时候就会产生二义性,它根本不知道这是一个类型还是别名,所以我们加上 typename 显式说明出来。当然如果这里没有二义性,比如Myclass ::test * a ,加上 typename 是会报错的。(此外,在 class 的 STL 底层还有一个特性,用于保留模板参数,但是在 c++17 中已经舍弃。)

关于cdn,稍微进行一点介绍:

CDN的全称是Content Delivery Network,即内容分发网络。这个概念始于1996年,是美国麻省理工学院的一个研究小组为改善互联网的服务质量而提出的。为了能在传统IP网上发布丰富的宽带媒体内容,他们提出在现有互联网基础上建立一个内容分发平台专门为网站提供服务,并于1999年成立了专门的CDN服务公司,为Yahoo提供专业服务。由于CDN是为加快网络访问速度而被优化的网络覆盖层,因此被形象地称为“网络加速器”。
——简而言之就是使网站访问速度更快的一种服务(大多是收费的)
 
V)CQXQW{G36W`_ZE5L.png
上次...或说之前一直使用的是 cloudflare 的cdn服务;之前的服务器搭在美国、所以在“域名一直没有备案所以无法使用国内cdn”的原因之外,也有它对国外服务器提供免费ssl证书的优势在里,而且它的速度在当时相对也一直还算过得去(毕竟vps本身的响应速度就已经慢的要死了),所以就一直用着。
而现在嘛,既然已经花费那么多时间把域名备案下来了,由不怎么再需要吸引国外的网友,不如改用国内的CDN比较方便。   正好在寻找着合适的CDN这样,想着不如正好写一篇文章可以给大家做参考:

国内CDN的选取介绍

首先要说一下国内的CDN基本都是需要先去备案的,买国外VPS搭网站的人请放下资本主义的猖狂去工信部备个案先

1.华为云CDN

广告上看到的,因为这次服务器买的就是华为的学生套餐,感觉速度很快而且客服小姐姐说话很好听,所以想考虑一下。基本上价格还算良心,可选流量计费和带宽计费,具体价格说明:https://support.huaweicloud.com/price-cdn/zh-cn_topic_0088467571.html
最近双十一还在打折,可以考虑一下
官网 https://www.huaweicloud.com/s/JUNETiU
50IU0$UE${9OHZ8P~G29UZP.png

2.百度云加速

同样是广告上看到的,分为免费版和四个付费版,付费版海外网站据说也能很好支持加速(很贵而且还是得备案别想了)、关于免费版,本来我记得之前免费版一直不支持https(那谁还用啊),但是现在(2019.11.15)已经支持上传SSL加速了! 没错,已经支持HTTPS加速了! ↓

官网 https://su.baidu.com/
GS35FTO2801O8T2M)QG~I0V.png

虽然曾经被人诟病为百度云减速,但实际用了一下其实还是不错的,缺钱且对百度没有什么厌恶心理的可以试一下。

3.奇安信网站卫士(360网站卫士)

这个是网友推荐的,免费CDN,不限流量、速度似乎还合适,缺钱的可以试一下
支持上传SSL证书,还提供免费的网站备案服务...不过emm奇虎360嘛,仁者见仁......

网站 https://wangzhan.qianxin.com/
EW6IRZ2{6_BV@I95.png

4.乌云盾

曾经是圈子里口碑很好的一个CDN,但刚才查到现在已经取消了免费版。 就不介绍了,当然不缺钱的依然可以考虑一下。
https://www.wafcloud.net/safe/

S)O@ZYP.png

5.七牛云

也是蛮有名的一个CDN了,每个月可使用10G的免费存储量和10G的CDN流量与100万次的Get请求数、但是账户最少需要有十元余额。总体来说性价比很高,图片缓存用这个的人很多。
https://www.qiniu.com/
)KHJ%}AV%RZ~5{ALZ3)GE3L.png

6.性能魔方

免费版前3个月免费使用百余个CDN节点和每月1000GB流量,之后每月可获得200GB的免费流量、此网站还免费提供网站云监测和WEB检测服务,总之和目前已经支持https的百度云加速一样,反正不要钱,这么良心的免费版推荐一试。
http://www.mmtrix.com/ispeed/

OP(B{7ZH2B9A_)@78X.png

7.腾讯云CDN加速

曾经是最良心的一个CDN服务,即便是现在,也是性价比最高的稳定CDN之一。 我域名就是在疼讯买的(第一年半价真香),申请ssl证书很方便,而且CDN对HTTPS的支持很好。最关键的是,虽然名义上是收费CDN,但是每个月都会赠送10G的流量,小站基本上都够用了。
另外注册新用户的话给300 G专享流量包,分六个月,每月50GB发给你。
怎么说呢, (真香)
官网 https://cloud.tencent.com/product/cdn/
![D8YVIDLHX2]8$(YYM%8_9SX.png][4]

国外CDN

1.cloudflare

最开始是从一个学弟那里听到的。之前一直用的这个,真的良心,不光提供完全免费的SSL证书一键实现https访问,连CDN都有免费版的,而且外网访问飞快,真正的全球加速 (笑) ,就是国内的网不怎么行。<p>
服务器在美国且不愿意备案的,强烈推荐这个。

官网 https://www.cloudflare.com/
DF)87WT1P%0Z`6DE@~{91OI.png

说真的,因为cloudflare已经太好了所以我没能其它能匹敌的高性价比国外cdn给你们推荐。(逃