1、三门问题

三门问题:

舞台上有3个门，其中一扇门后面有一辆轿车
抽奖人选一个门，主持人打开另外一个没有轿车的门
主持人问：抽奖人要不要选剩下的那个门打开 ？
题目问：选剩下的门，和，坚持原来的选择，哪个中奖概率高一些 ？

答案：

用代码模拟上万次，可以发现，选择剩下的门的概率更高一些。

2、中奖概率问题

问题：

游戏里每个宝箱抽中屠龙宝刀的概率是20%，打开5个宝箱，是否能一定中宝刀 ？

答案：

不一定

解答：

5 * 0.2 = 1 是一个期望值。这件事发生的期望是5次，也就是很多用户，每个用户都一个个宝箱的抽，平均下来，人均抽5次，大家都拿到宝刀了。
其实这个5次都抽不到宝箱的概率是0.8的5次方，所以，打开5个宝箱，抽到宝刀的概率就是 1- 0.8^5。

3、快速排序

算法步骤:

第一遍：比较第一个，第二个数字大小，如果第二个小于第一个，那么交换位置。
第二遍：比较第三个和第二个的大小，如果小于第二个那么，交换二三的位置，再比价第一二个的大小，如果第二个小于第一个，那么交换一二的位置。
...
第N边: 比较第N个和第N-1个的大小，。。。也就是说，把第N个数字，进入到前面N-1的某一个位置中去

4、选择排序

算法步骤：

第一遍：选出这个数组的最小的数，放到第一个位置

第二遍：选出从第2个到最后中最小的书，放到第二个位置

第N-1遍：选出第 N-1 和 第N个数哪个大，哪个小

核心代码:

for (int i=0; i< data.N(); i++) {
     // 寻找[i, n) 区间里最小值的索引
     int minIndex = i;
     for (int j = i+1; j < data.N(); j++) {
         if (data.get(j)<data.get(minIndex)) {
             minIndex = j;
         }
     }
     data.swap(i, minIndex);
 }

备注：

选择排序的比较复杂度大概是 O(n^2)
所以选择排序的一个应用场景在于此
因为选择排序的交换次数少，稳定在O(n)，
对于现实中，集装箱排序较为实用，因为集装箱移动起来不方便。

5、蒙特卡洛

• 蒙特卡洛不仅仅用来球π值，它主要特指一种计算机模拟思想，例如，用简化现实中的事情，让计算机大量模拟，来求得近似值，可以用于决策。
• 求π：

正方形面积 = 4 * R * R 
圆形面积 = π * R * R
在这个正方形里随机撒点，落到圆形里的数量 / 总点数 = 圆形面积 / 正方形面积 = π/4
从而求得 π 值

6、插入排序

算法分析：

这里对数组进行排序的过程需要两个序列才能完成。 一个待排序的乱序序列，一个是已排序的有序序列。我们现在要要做的就是把乱序的元素一个一个地从乱序列中插入到有序序列中去。

可是，这里还是有一些不太好的地方，比较明显地方就是我们需要额外添加一个辅助数组。如果这个待排序数据比较大，那么可能添加辅助数组的策略就不能使用了。 
这里我们不难想到，在原始数组中，有这样的一个等式：整体序列 = 有序序列 + 乱序序列 
也就是说我们可以把当前序列数组一分为二，左边为有序，右边为乱序。 

这样每次从乱序序列中取出第一个元素，从有序列中插入。直到序列整体有序为止。

算法步骤：

一开始a[0]是有序的，
1、取a[i]
2、对把a[i]插入到a[0]~a[i-1]这个有序的部分的序列的合适位置中
重复1，2步骤

核心代码：

for(int i=0; i<data.N(); i++) {
    for(int j=i; j>0 && data[j] < data[j-1]; j--) {
        data.swap(j,j-1);
    }
}

备注：

这里的最坏的情况和平均情况从代码中就可以看出来，因为有两嵌套的for循环嘛。那么其最好的情况呢？这个就是对于一个有序的序列来说，不需要进行交换，只是比较了n次，所以这里最好的时间复杂度就是O(n)。

7、归并排序

算法分析：

1、一个数组分成左右两部分
2、分别对左右两边数组排序，然后归并成一个数组
左边：重复2步骤
右边：重复2步骤
...
最后，分成了一个个只有一个元素的数组
3、然后归并最小数组，两两归并
然后再重复3步骤

核心有两个：一是2所处的递归，二是3所处的归并数组

算法步骤：

问题1：如何将数组分开，并进行分别排序？

答：使用递归实现

问题2：如何将两个有序的数组进行合并排序？

假设如上图的第二行中，需要合并（2,4,5,8）和（1,3,6,7）两个数组。

1，因为这两个数组都是增序的，只需要比较俩个数组的第一个数，那么比较小的数必然是两数组中最小的数。

　　例：比较（2,4,5,8）的2 和（1,3,6,7）的1，那么1必然是两数组中最小的数。

2，将这个数放入一个新的数组。

　　例：将1放入数组a[]中，两数组还有（2,4,5,8）的2 和（3,6,7）
　　
a[] 成为 [1]

3，再次重复第1步。
比较（2,4,5,8）的2 和（3,6,7）的3，那么2必然是两数组中最小的数。
a[] 成为 [1,2]
比较（4,5,8）的4 和（3,6,7）的3，那么3必然是两数组中最小的数。
a[] 成为 [1,2,3]
比较（4,5,8）的4 和（6,7）的6，那么4必然是两数组中最小的数。
a[] 成为 [1,2,3,4]
.....

如此比较直到其中一个数组结束，将另一个数组剩下的值全部放入数组a

那么数组a便是排好序的数组。

核心代码：

    // 3、第三步：将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){
            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            } else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
                
            // 左半部分所指元素 < 右半部分所指元素
            } else if( aux[i-l].compareTo(aux[j-l]) < 0 ){ 
                arr[k] = aux[i-l]; i ++;
            } else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }
    
    // 2、第二步： 递归使用归并排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {
        // 对于小规模数组, 使用插入排序
        //if( r - l <= 15 ){
        //   InsertionSort.sort(arr, l, r);
        //  return;
        //}
        if (l >= r) {
            return;
        }
        int mid = (l+r)/2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
        if( arr[mid].compareTo(arr[mid+1]) > 0 ){
            merge(arr, l, mid, r);
        }
    }
    // 1、第一步：
    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr, 0, n-1);
    }

备注：

递归：对于第二步的递归：
    1，sort调用自己后，5/2=2 2/2=1  1/2=0 
    sort(arr,0,2)
    sort(arr,0,1)
    sort(arr,0,0)
    sort(arr,1,1)
    merge(arr,0,0,1)
    sort(arr,1,2)
    merge(arr,0,1,2)
合并：对于第三步的合并：
    出来3个变量，i,j,k分别标记arr的下标位置，每次拿arr[i]或arr[j]给arr[k]赋值；
    
复杂度：O(nlogn)
      可以在1秒之内轻松处理100万数量级的数据
      不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据
      否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异；

8、快速排序

算法思想：

采用了一种分治的策略。通常称其为分治法(Divide and ConquerMethod)。
即先对整体进行分治，划分左右两段(左边的数值小于等于右边的值或者左边的值大于等于右边的值)。
再把划分的好的段当作一个整体继续划分为两段，以此递归。

算法步骤：

1，分割(把数组第一个数L当做分割点，从第二个数j和第三个数i开始，
如果i<L，就交换ij，ji同时++
如果i>L，i++, j不动)
遍历结束找到一个位置p，既j的值，交换p和L；
此时，p作为分割点找到了，进入递归

2，递归调用分割

核心代码：

private void quickSort(int l, int r){
//        if( l >= r )
//            return;
        if( l > r )  return;
        if( l == r ){ return; }
        int p = partition(l, r);
        quickSort(l, p-1 );
        quickSort(p+1, r);
 }
 // 这个方法里的L是找的一个数组中随机位置的数字
 private int partition(int l, int r){
        int p = (int)(Math.random()*(r-l+1)) + l; 
        data.swap(l, p);
        int v = data.get(l); 
        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ ) {
            if (data.get(i) < v) {
                j++;
                data.swap(j, i);
            }
        }
        data.swap(l, j);
        return j;
  }

备注：

快速排序最好，最坏，平均复杂度分析
https://blog.csdn.net/weshjiness/article/details/8660583
最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)
在最坏的情况下，待排序的序列为正序或者逆序，最终其时间复杂度为O(n2)。
平均的情况，其数量级为O(nlogn)。快速排序是一种不稳定的排序方法。

随机找位置的那个函数应该就是为了调节上面的那个网页里的那个系数k，让它比较平均

9、双路快排

算法思想：快速排序法的优化——双路快速排序

换一个思路来写partion函数，之前我们都是把大于小于数统统放到一边，这一次我们采用双路快速排序法来提高效率，
使其不用靠i一个变量遍历完所有的数据，我们可以增加一个变量j从数组的尾端同时遍历数组：
增加一个变量j，当i从左往右遍历数组时，碰到不符合小于V的数时停止，
然后j从数组的右边开始遍历，碰到属于大于V的数时停止，
此时我们只需要交换一下i.j指向的数据就可以了，
然后重复i扫描，j扫描，交换两个数的操作，
即使i和j所指向的数据相等时（都等于V）也会进行交换一次，
防止了大量等于V的数据全部推到一边去了。

算法步骤：

1，分割
i处小于v的时候，i++, 相当于把小于v的全过滤掉，
j处大于v的时候，j--，相当于把大于v的全过滤掉，
两个内部while都出去的话，i，j处都找到了小于v的和大于v的数，
那么交换，
i++，j--分别前进后退一位，
如果i>j，那么退出循环
这个时候，j处的位置是小于或者等于v的，因为如果不是，两个内部的while就出不来，
然后交换j和L，确保v处在中间位置
这个时候返回j，j就是中间的分割位置，然后再递归调用自己两次，sort(arr,0,j-1),sort(arr,j+1,n-1);
2，递归

核心代码：

template<typename T>
int __partion(T arr[],int l,int r)//分类子操作，最后返回V处于的位置下标
{
    srand(time(NULL));//随机种子
    swap(arr[l],arr[rand()%(r-l+1)+l]);//随机取参考值的大小
    T v=arr[l];//记录参考值的大小用来作为分类的依据
    int i=l+1,j=r;
    while(true) 
    {
        while(i<=r&&arr[i]<v) i++;//之所以不加=V条件的作用是让=V的数据也进行交换
        while(j>=l+1&&arr[j]>v)j--;
        if(i>j) break;//i.j全部寻找完毕
        swap(arr[i],arr[j]);//交换值
        i++;
        j--;
    }
    swap(arr[l],arr[j]);//把参考值提到中间来
    return j;
}

备注：

10、三路快排

算法思想： 从一道面试题再看三路快排partition

三路快排要做的事情，其实就是将数组分成三部分：小于v，等于v和大于v，之后递归的对小于v和大于v部分进行排序就好了。

算法步骤：

// v为pivot，初始存储在arr[l]的位置  n. 枢轴；中心点；旋转运动
int lt = l;        // 循环过程中保持 arr[l+1...lt] < v  ; less than
int gt = r + 1;    // 循环过程中保持 arr[gt...r] > v    ; greater than
int i = l+1;       // 循环过程中保持 arr[lt+1...i) == v ;
while( i < gt ) {
    if( arr[i] < v ) {
        swap( arr[i++], arr[lt+1]);
        lt ++;
    } else if( arr[i] > v ) {
        swap( arr[i], arr[gt-1]); 
        gt --;
    } else { // arr[i] == v
        i ++;
    }
}
swap( arr[l] , arr[lt] );

// 此时 arr[lt...gt-1]部分为数组中元素等于v的部分
// 之后只需要递归地对arr[l...lt-1]和arr[gt...r]两部分进行三路快排即可

核心代码：