1帆赢、三門(mén)問(wèn)題

三門(mén)問(wèn)題:

舞臺(tái)上有3個(gè)門(mén)茶敏，其中一扇門(mén)后面有一輛轎車(chē)
抽獎(jiǎng)人選一個(gè)門(mén)壤靶，主持人打開(kāi)另外一個(gè)沒(méi)有轎車(chē)的門(mén)
主持人問(wèn)：抽獎(jiǎng)人要不要選剩下的那個(gè)門(mén)打開(kāi) ？
題目問(wèn)：選剩下的門(mén)惊搏，和贮乳，堅(jiān)持原來(lái)的選擇忧换，哪個(gè)中獎(jiǎng)概率高一些 ？

答案：

用代碼模擬上萬(wàn)次向拆，可以發(fā)現(xiàn)亚茬，選擇剩下的門(mén)的概率更高一些。

2浓恳、中獎(jiǎng)概率問(wèn)題

問(wèn)題：

游戲里每個(gè)寶箱抽中屠龍寶刀的概率是20%刹缝，打開(kāi)5個(gè)寶箱，是否能一定中寶刀 颈将？

答案：

不一定

解答：

5 * 0.2 = 1 是一個(gè)期望值梢夯。這件事發(fā)生的期望是5次，也就是很多用戶(hù)晴圾，每個(gè)用戶(hù)都一個(gè)個(gè)寶箱的抽厨疙，平均下來(lái)，人均抽5次疑务，大家都拿到寶刀了沾凄。
其實(shí)這個(gè)5次都抽不到寶箱的概率是0.8的5次方，所以知允，打開(kāi)5個(gè)寶箱撒蟀，抽到寶刀的概率就是 1- 0.8^5。

3温鸽、快速排序

算法步驟:

第一遍：比較第一個(gè)保屯，第二個(gè)數(shù)字大小，如果第二個(gè)小于第一個(gè)涤垫，那么交換位置姑尺。
第二遍：比較第三個(gè)和第二個(gè)的大小，如果小于第二個(gè)那么蝠猬，交換二三的位置切蟋，再比價(jià)第一二個(gè)的大小，如果第二個(gè)小于第一個(gè)榆芦，那么交換一二的位置柄粹。
...
第N邊: 比較第N個(gè)和第N-1個(gè)的大小，匆绣。驻右。。也就是說(shuō)崎淳，把第N個(gè)數(shù)字堪夭，進(jìn)入到前面N-1的某一個(gè)位置中去

4、選擇排序

算法步驟：

第一遍：選出這個(gè)數(shù)組的最小的數(shù)，放到第一個(gè)位置

第二遍：選出從第2個(gè)到最后中最小的書(shū)森爽，放到第二個(gè)位置

第N-1遍：選出第 N-1 和 第N個(gè)數(shù)哪個(gè)大恨豁，哪個(gè)小

核心代碼:

for (int i=0; i< data.N(); i++) {
     // 尋找[i, n) 區(qū)間里最小值的索引
     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);
 }

備注：

選擇排序的比較復(fù)雜度大概是 O(n^2)
所以選擇排序的一個(gè)應(yīng)用場(chǎng)景在于此
因?yàn)檫x擇排序的交換次數(shù)少，穩(wěn)定在O(n)拗秘，
對(duì)于現(xiàn)實(shí)中圣絮，集裝箱排序較為實(shí)用，因?yàn)榧b箱移動(dòng)起來(lái)不方便雕旨。

5扮匠、蒙特卡洛

• 蒙特卡洛不僅僅用來(lái)球π值，它主要特指一種計(jì)算機(jī)模擬思想凡涩，例如棒搜，用簡(jiǎn)化現(xiàn)實(shí)中的事情，讓計(jì)算機(jī)大量模擬活箕，來(lái)求得近似值力麸，可以用于決策。
• 求π：

正方形面積 = 4 * R * R 
圓形面積 = π * R * R
在這個(gè)正方形里隨機(jī)撒點(diǎn)育韩，落到圓形里的數(shù)量 / 總點(diǎn)數(shù) = 圓形面積 / 正方形面積 = π/4
從而求得 π 值

6克蚂、插入排序

算法分析：

這里對(duì)數(shù)組進(jìn)行排序的過(guò)程需要兩個(gè)序列才能完成。 一個(gè)待排序的亂序序列筋讨，一個(gè)是已排序的有序序列埃叭。我們現(xiàn)在要要做的就是把亂序的元素一個(gè)一個(gè)地從亂序列中插入到有序序列中去。

可是悉罕，這里還是有一些不太好的地方赤屋，比較明顯地方就是我們需要額外添加一個(gè)輔助數(shù)組。如果這個(gè)待排序數(shù)據(jù)比較大壁袄，那么可能添加輔助數(shù)組的策略就不能使用了类早。 
這里我們不難想到，在原始數(shù)組中嗜逻，有這樣的一個(gè)等式：整體序列 = 有序序列 + 亂序序列 
也就是說(shuō)我們可以把當(dāng)前序列數(shù)組一分為二涩僻，左邊為有序，右邊為亂序变泄。 

這樣每次從亂序序列中取出第一個(gè)元素令哟，從有序列中插入。直到序列整體有序?yàn)橹埂?

算法步驟：

一開(kāi)始a[0]是有序的晴竞，
1蛙卤、取a[i]
2、對(duì)把a(bǔ)[i]插入到a[0]~a[i-1]這個(gè)有序的部分的序列的合適位置中
重復(fù)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);
    }
}

備注：

這里的最壞的情況和平均情況從代碼中就可以看出來(lái)颤难，因?yàn)橛袃汕短椎膄or循環(huán)嘛神年。那么其最好的情況呢？這個(gè)就是對(duì)于一個(gè)有序的序列來(lái)說(shuō)行嗤，不需要進(jìn)行交換已日，只是比較了n次，所以這里最好的時(shí)間復(fù)雜度就是O(n)栅屏。

7飘千、歸并排序

算法分析：

1、一個(gè)數(shù)組分成左右兩部分
2栈雳、分別對(duì)左右兩邊數(shù)組排序护奈，然后歸并成一個(gè)數(shù)組
左邊：重復(fù)2步驟
右邊：重復(fù)2步驟
...
最后，分成了一個(gè)個(gè)只有一個(gè)元素的數(shù)組
3哥纫、然后歸并最小數(shù)組霉旗，兩兩歸并
然后再重復(fù)3步驟

核心有兩個(gè)：一是2所處的遞歸，二是3所處的歸并數(shù)組

算法步驟：

問(wèn)題1：如何將數(shù)組分開(kāi)蛀骇，并進(jìn)行分別排序厌秒？

答：使用遞歸實(shí)現(xiàn)

問(wèn)題2：如何將兩個(gè)有序的數(shù)組進(jìn)行合并排序？

假設(shè)如上圖的第二行中擅憔，需要合并（2,4,5,8）和（1,3,6,7）兩個(gè)數(shù)組鸵闪。

1，因?yàn)檫@兩個(gè)數(shù)組都是增序的雕欺，只需要比較倆個(gè)數(shù)組的第一個(gè)數(shù)岛马，那么比較小的數(shù)必然是兩數(shù)組中最小的數(shù)。

　　例：比較（2,4,5,8）的2 和（1,3,6,7）的1屠列，那么1必然是兩數(shù)組中最小的數(shù)啦逆。

2，將這個(gè)數(shù)放入一個(gè)新的數(shù)組笛洛。

　　例：將1放入數(shù)組a[]中夏志，兩數(shù)組還有（2,4,5,8）的2 和（3,6,7）
　　
a[] 成為 [1]

3，再次重復(fù)第1步苛让。
比較（2,4,5,8）的2 和（3,6,7）的3沟蔑，那么2必然是兩數(shù)組中最小的數(shù)。
a[] 成為 [1,2]
比較（4,5,8）的4 和（3,6,7）的3狱杰，那么3必然是兩數(shù)組中最小的數(shù)瘦材。
a[] 成為 [1,2,3]
比較（4,5,8）的4 和（6,7）的6，那么4必然是兩數(shù)組中最小的數(shù)仿畸。
a[] 成為 [1,2,3,4]
.....

如此比較直到其中一個(gè)數(shù)組結(jié)束食棕，將另一個(gè)數(shù)組剩下的值全部放入數(shù)組a

那么數(shù)組a便是排好序的數(shù)組朗和。

核心代碼：

    // 3、第三步：將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
    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 ){  // 如果左半部分元素已經(jīng)全部處理完畢
                arr[k] = aux[j-l]; j ++;
            } else if( j > r ){   // 如果右半部分元素已經(jīng)全部處理完畢
                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、第二步： 遞歸使用歸并排序,對(duì)arr[l...r]的范圍進(jìn)行排序
    private static void sort(Comparable[] arr, int l, int r) {
        // 對(duì)于小規(guī)模數(shù)組, 使用插入排序
        //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);
        // 對(duì)于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge
        // 對(duì)于近乎有序的數(shù)組非常有效,但是對(duì)于一般情況,有一定的性能損失
        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);
    }

備注：

遞歸：對(duì)于第二步的遞歸：
    1忆植，sort調(diào)用自己后，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)
合并：對(duì)于第三步的合并：
    出來(lái)3個(gè)變量谒臼，i,j,k分別標(biāo)記arr的下標(biāo)位置朝刊，每次拿arr[i]或arr[j]給arr[k]賦值；
    
復(fù)雜度：O(nlogn)
      可以在1秒之內(nèi)輕松處理100萬(wàn)數(shù)量級(jí)的數(shù)據(jù)
      不要輕易嘗試使用SelectionSort, InsertionSort或者BubbleSort處理100萬(wàn)級(jí)的數(shù)據(jù)
      否則屋休，你就見(jiàn)識(shí)了O(n^2)的算法和O(nlogn)算法的本質(zhì)差異坞古；

8、快速排序

算法思想：

采用了一種分治的策略劫樟。通常稱(chēng)其為分治法(Divide and ConquerMethod)痪枫。
即先對(duì)整體進(jìn)行分治，劃分左右兩段(左邊的數(shù)值小于等于右邊的值或者左邊的值大于等于右邊的值)叠艳。
再把劃分的好的段當(dāng)作一個(gè)整體繼續(xù)劃分為兩段奶陈，以此遞歸。

算法步驟：

1附较，分割(把數(shù)組第一個(gè)數(shù)L當(dāng)做分割點(diǎn)吃粒，從第二個(gè)數(shù)j和第三個(gè)數(shù)i開(kāi)始，
如果i<L拒课，就交換ij徐勃，ji同時(shí)++
如果i>L，i++, j不動(dòng))
遍歷結(jié)束找到一個(gè)位置p早像，既j的值僻肖，交換p和L；
此時(shí)卢鹦，p作為分割點(diǎn)找到了臀脏，進(jìn)入遞歸

2，遞歸調(diào)用分割

核心代碼：

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);
 }
 // 這個(gè)方法里的L是找的一個(gè)數(shù)組中隨機(jī)位置的數(shù)字
 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;
  }

備注：

快速排序最好冀自，最壞揉稚，平均復(fù)雜度分析
https://blog.csdn.net/weshjiness/article/details/8660583
最好情況，遞歸樹(shù)的深度為log2n熬粗，其空間復(fù)雜度也就為O(logn)
在最壞的情況下搀玖，待排序的序列為正序或者逆序，最終其時(shí)間復(fù)雜度為O(n2)驻呐。
平均的情況巷怜，其數(shù)量級(jí)為O(nlogn)葛超”┦希快速排序是一種不穩(wěn)定的排序方法延塑。

隨機(jī)找位置的那個(gè)函數(shù)應(yīng)該就是為了調(diào)節(jié)上面的那個(gè)網(wǎng)頁(yè)里的那個(gè)系數(shù)k，讓它比較平均

9答渔、雙路快排

算法思想：快速排序法的優(yōu)化——雙路快速排序

換一個(gè)思路來(lái)寫(xiě)partion函數(shù)关带，之前我們都是把大于小于數(shù)統(tǒng)統(tǒng)放到一邊，這一次我們采用雙路快速排序法來(lái)提高效率沼撕，
使其不用靠i一個(gè)變量遍歷完所有的數(shù)據(jù)宋雏，我們可以增加一個(gè)變量j從數(shù)組的尾端同時(shí)遍歷數(shù)組：
增加一個(gè)變量j，當(dāng)i從左往右遍歷數(shù)組時(shí)务豺，碰到不符合小于V的數(shù)時(shí)停止磨总，
然后j從數(shù)組的右邊開(kāi)始遍歷，碰到屬于大于V的數(shù)時(shí)停止笼沥，
此時(shí)我們只需要交換一下i.j指向的數(shù)據(jù)就可以了蚪燕，
然后重復(fù)i掃描，j掃描奔浅，交換兩個(gè)數(shù)的操作馆纳，
即使i和j所指向的數(shù)據(jù)相等時(shí)（都等于V）也會(huì)進(jìn)行交換一次，
防止了大量等于V的數(shù)據(jù)全部推到一邊去了汹桦。

算法步驟：

1鲁驶，分割
i處小于v的時(shí)候，i++, 相當(dāng)于把小于v的全過(guò)濾掉舞骆，
j處大于v的時(shí)候钥弯，j--，相當(dāng)于把大于v的全過(guò)濾掉督禽，
兩個(gè)內(nèi)部while都出去的話(huà)脆霎，i，j處都找到了小于v的和大于v的數(shù)赂蠢，
那么交換绪穆，
i++，j--分別前進(jìn)后退一位虱岂，
如果i>j玖院，那么退出循環(huán)
這個(gè)時(shí)候，j處的位置是小于或者等于v的第岖，因?yàn)槿绻皇悄丫瑑蓚€(gè)內(nèi)部的while就出不來(lái)，
然后交換j和L蔑滓，確保v處在中間位置
這個(gè)時(shí)候返回j郊酒，j就是中間的分割位置遇绞，然后再遞歸調(diào)用自己兩次，sort(arr,0,j-1),sort(arr,j+1,n-1);
2燎窘，遞歸

核心代碼：

template<typename T>
int __partion(T arr[],int l,int r)//分類(lèi)子操作摹闽，最后返回V處于的位置下標(biāo)
{
    srand(time(NULL));//隨機(jī)種子
    swap(arr[l],arr[rand()%(r-l+1)+l]);//隨機(jī)取參考值的大小
    T v=arr[l];//記錄參考值的大小用來(lái)作為分類(lèi)的依據(jù)
    int i=l+1,j=r;
    while(true) 
    {
        while(i<=r&&arr[i]<v) i++;//之所以不加=V條件的作用是讓=V的數(shù)據(jù)也進(jìn)行交換
        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]);//把參考值提到中間來(lái)
    return j;
}

備注：

10、三路快排

算法思想： 從一道面試題再看三路快排partition

三路快排要做的事情褐健，其實(shí)就是將數(shù)組分成三部分：小于v付鹿，等于v和大于v，之后遞歸的對(duì)小于v和大于v部分進(jìn)行排序就好了蚜迅。

算法步驟：

// v為pivot舵匾，初始存儲(chǔ)在arr[l]的位置  n. 樞軸；中心點(diǎn)谁不；旋轉(zhuǎn)運(yùn)動(dòng)
int lt = l;        // 循環(huán)過(guò)程中保持 arr[l+1...lt] < v  ; less than
int gt = r + 1;    // 循環(huán)過(guò)程中保持 arr[gt...r] > v    ; greater than
int i = l+1;       // 循環(huán)過(guò)程中保持 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] );

// 此時(shí) arr[lt...gt-1]部分為數(shù)組中元素等于v的部分
// 之后只需要遞歸地對(duì)arr[l...lt-1]和arr[gt...r]兩部分進(jìn)行三路快排即可

核心代碼：