1. 遞歸

• 遞歸arr[L…R]范圍上求大值
  流程分析如下:
  
  java代碼:

package paixu.class01;

public class Code08_GetMax {public static void main(String[] args) {int[] arr = {3,2,5,6,7,4};
        System.out.println(getMax(arr));
    }

    public static int getMax(int[] arr) {return process(arr, 0, arr.length - 1);
    }

    //arr[L..R]范圍上求大值
    public static int process(int[] arr, int L, int R) {if (L == R){//arr[L..R]范圍上只有一個數(shù)，直接返回
            return arr[L];
        }
        int mid = L + ((R-L) >>1);
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }
}

成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比武勝網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式武勝網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋武勝地區(qū)。費用合理售后完善，十載實體公司更值得信賴。2. Master公式

Master公式用來計算子問題規(guī)模確定的遞歸函數(shù)的時間復(fù)雜度。

master公式的使用
T(N) = a*T(N/b) + O(N^d)

1. log(b,a) >d ->復(fù)雜度為O(N^log(b,a))
2. log(b,a) = d ->復(fù)雜度為O(N^d * logN)
3. log(b,a)< d ->復(fù)雜度為O(N^d)

說明：
T(N)：母問題的規(guī)模
T(N/b)： 子問題的規(guī)模
a： 子問題調(diào)用次數(shù)
O(N^d)：除了子問題之外，其他邏輯的時間復(fù)雜度

例子: 上面遞歸求arr[L…R]范圍上大值。滿足master公式。
T(N) = 2*T(N/2) + O(N^0)

3. 歸并排序

歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。
歸并排序時間復(fù)雜度O(N*logN)，額外空間復(fù)雜度O(N),穩(wěn)定排序
歸并操作，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法。歸并排序的流程圖如下:

在看歸并排序時，我們首先要能夠歸并兩個有序數(shù)組，換句話說就是合并兩個有序數(shù)組為一個有序數(shù)組。
例如歸并以下兩個數(shù)組。素材來源 https://blog.csdn.net/weixin_50941083/article/details/120852477

a[5] = {3，5，7，8，10}
b[7] = {1，2，4，5，8，11，1}

主要思想：

1. 定義一個新數(shù)組c，可以容納a和b兩個數(shù)組中的所有元素；
2. 初始化三個下標（都指向第一個元素），i給a數(shù)組，j給b數(shù)組，k是新數(shù)組c的；
3. a[i]和b[j]進行比較：若a[i]b[j]，將b[j]填入c[k]，j++，k++;
4. 循環(huán)第三步，直至其中一個數(shù)組中的數(shù)據(jù)全部填入數(shù)組c中，再將另外一個還有剩余的數(shù)組中的元素放入新數(shù)組c中。

圖解過程如下：

java代碼:

package paixu.class02;

import java.util.Arrays;

public class Code01_MergeSort_ {public static void main(String[] args) {int[] arr = {10,4,6,3,8,2,5,7};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void mergeSort(int[] arr) {if (arr == null || arr.length< 2) {return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void merge(int[] arr, int l, int m, int r) {int[] tempArr = new int[r - l + 1];
        int i = l;
        int j = m + 1;
        int k = 0;
        while (i<= m && j<= r) {if (arr[i]<= arr[j]) {tempArr[k++] = arr[i++];
            }else{tempArr[k++] = arr[j++];
            }
        }
        while (i<= m) {tempArr[k++] = arr[i++];
        }
        while (j<= r) {tempArr[k++] = arr[j++];
        }

        //把臨時保存數(shù)組數(shù)據(jù)拷貝到原數(shù)組
        for (int e = 0; e< tempArr.length; e++) {arr[l++] = tempArr[e];
        }
    }

    public static void process(int[] arr, int L, int R) {if (L == R) {return;
        }
        int mid = L + ((R - L) >>1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
}

master公式分析歸并排序:
merge()的時間復(fù)雜度為O(N)
T(N) = 2T(N/2) + O(N) ->a = 2, b = 2, d = 1
log(b,a) = d ->時間復(fù)雜度為O(N * logN)

1. 小和問題

參考 https://blog.csdn.net/qq_37236745/article/details/83625679
描述
在一個數(shù)組中，每一個數(shù)左邊比當前數(shù)小的數(shù)累加起來，叫做這個數(shù)組的小和。求一個數(shù)組的小和。
例子
[1,3,4,2,5]
1左邊比1小的數(shù)：沒有
3左邊比3小的數(shù)：1
4左邊比4小的數(shù)：1,3
2左邊比2小的數(shù)：1
5左邊比5小的數(shù)：1,3,4,2
所以小和為1+1+3+1+1+3+4+2=16
解題思路
如果直接用兩層for循環(huán)掃，時間復(fù)雜度是O(n ^2) ，但是可以通過歸并排序的方法將時間復(fù)雜度降到O(nlogn)
具體做法：歸并排序分兩步，一是分，二是治。分好說，不停的將數(shù)組劃分為兩部分，比如樣例，最終劃分為如下圖所示的樣子

分完以后開始治，歸并排序的治就是merge的過程，首先對1和3進行merge，在此過程中產(chǎn)生一個小和1；然后將1、3和4進行merge，在此過程中產(chǎn)生小和1、3；然后2和5進行merge，產(chǎn)生小和2；最后將1、3、4和2、5進行一次merge，1比2小，所以一共產(chǎn)生n個1的小和，這個n就是當前右邊的數(shù)的個數(shù)，因為右邊有兩個數(shù)2和5，所以產(chǎn)生2個1的小和，然后將1填入輔助數(shù)組，繼續(xù)比較3和2，2比3小，但是2是右邊的數(shù)，所以不算小和，然后比較3和5，3比5小，所以產(chǎn)生n個3的小和，因為右側(cè)只有一個數(shù)，所以就只產(chǎn)生1個3的小和，同樣的，
產(chǎn)生1個4的小和
這道題換個角度來想，題目要求的是每個數(shù)左邊有哪些數(shù)比自己小，其實不就是右邊有多少個數(shù)比自己大，那么產(chǎn)生的小和就是當前值乘以多少個嗎？還是以上面的樣例舉例，1右邊有4個比1大的數(shù)，所以產(chǎn)生小和14；3右邊有2個比3大的數(shù)，所以產(chǎn)生小和32；4右邊有一個比4大的數(shù)，所以產(chǎn)生小和41；2右邊沒有比2大的數(shù)，所以產(chǎn)生小和為20；5右邊也沒有比5大的數(shù)，所以產(chǎn)生小和5*0

java代碼:

package paixu.class02;


public class Code02_SmallSum {public static void main(String[] args) {int[] arr = {1,3,4,2,5};
        System.out.println(getSmallSum(arr));
    }
    public static int getSmallSum(int[] arr) {if (arr == null || arr.length<= 1) {return 0;
        }
        return process(arr, 0, arr.length - 1);
    }
    public static int merge(int[] arr, int l, int m, int r) {int res = 0;
        int[] tempArr = new int[r - l + 1];
        int i = l;
        int j = m + 1;
        int k = 0;
        while (i<= m && j<= r) {if (arr[i]< arr[j]) {res += arr[i] * (r - j + 1);
                tempArr[k++] = arr[i++];
            }else{tempArr[k++] = arr[j++];
            }
        }
        while (i<= m) {tempArr[k++] = arr[i++];
        }
        while (j<= r) {tempArr[k++] = arr[j++];
        }
        //臨時數(shù)組拷貝到原數(shù)組
        for (int e = 0; e< tempArr.length; e++) {arr[l++] = tempArr[e];
        }
        return res;
    }

    public static int process(int[] arr, int L, int R) {if (L == R) {return 0;
        }
        int mid = L + ((R - L) >>1);
        return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);
    }
}

2. 逆序?qū)?ul>

什么是逆序?qū)δ兀堪俣劝倏七@樣解釋：

設(shè) A 為一個有 n 個數(shù)字的有序集 (n>1)，其中所有數(shù)字各不相同。如果存在正整數(shù) i, j 使得 1 ≤ i< j ≤ n 而且 A[i] >A[j]，則 這個有序?qū)ΨQ為 A 的一個逆序?qū)?，也稱作逆序數(shù)。

• 在一個數(shù)組中，左邊的數(shù)如果比右邊的數(shù)大，則這兩個數(shù)構(gòu)成一個逆序?qū)?，請打印所有逆序?qū)?，或者逆序?qū)?shù)量?

分析：
本題其實就是統(tǒng)計數(shù)組中右邊比左邊小的數(shù)據(jù)對數(shù)。用歸并排序算法的思想
java代碼:

package paixu.class02;

public class Code03_nixudui_ {public static void main(String[] args) {int[] arr = {3,2,4,5,0};
        int res = getNixuNum(arr);
        System.out.println(res);
    }
    public static int getNixuNum(int[] arr) {if (arr == null || arr.length< 1) {return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int merge(int[] arr, int l, int mid, int r) {int res = 0;
        int i = l;
        int j = mid + 1;
        int k = 0;
        int[] tempArr = new int[r - l + 1];
        while (i<= mid && j<= r) {if (arr[i] >arr[j]) {res += (r - j + 1);
                for (int g = j; g<= r; g++) {System.out.println(arr[i] + " ->" + arr[g]);
                }
                tempArr[k++] = arr[i++];
            }else {tempArr[k++] = arr[j++];
            }
        }
        while (i<= mid) {tempArr[k++] = arr[i++];
        }
        while (j<= r) {tempArr[k++] = arr[j++];
        }
        for (int e = 0; e< tempArr.length; e++) {arr[l++] = tempArr[e];
        }
        return res;
    }

    public static int process(int[] arr, int l, int r) {if (l == r) {return 0;
        }
        int mid = l + ((r - l) >>1);
        int left = process(arr, l, mid);
        int right = process(arr, mid + 1, r);
        int merge = merge(arr, l, mid, r);
        return  left + right + merge;
    }
}

4. 快速排序

快速排序算法通過多次比較和交換來實現(xiàn)排序，其排序流程如下：

(1)首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分。
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于或等于分界值。
(3)然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個分界值，將該部分數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
(4)重復(fù)上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。

排序步驟
原理：
設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動。

荷蘭國旗問題
問題一：給定一個數(shù)組arr，和一個數(shù)num，請把小于等于num的數(shù)放在數(shù)組的左邊，大于num的數(shù)放在數(shù)組的右邊。要求額外空間復(fù)雜度O(1)，時間復(fù)雜度O(N)
解決方案:
劃定一個<=區(qū)域 j，初始化為-1，一個指針i 初始化指向arr[0],arr[i]與num比較大小:

1. arr[i]<= num;arr[i] 和<=區(qū)域的下一個數(shù)交換，<=區(qū)域右擴一個（j++），同時 i++; 2)arr[i]
2. arr[i] >num; i++;

例子:arr = [3,5,6,7,4,3,5,8], num = 5。整個流程如下:

java代碼:

//在數(shù)組arr中，把小于num的數(shù)放在數(shù)組左邊，大于num的數(shù)放在右邊
    public static void version1(int[] arr, int num) {int leftArea = -1;
        for (int i = 0; i< arr.length; i++) {if (arr[i]<= num) {swap(arr, i, ++leftArea);
            }
        }
        System.out.println(leftArea);
    }

問題二(荷蘭國旗問題)
給定一個數(shù)組arr，和一個數(shù)num，請把小于num的數(shù)放在數(shù)組的左邊，等于num的數(shù)放在數(shù)組的中間，大于num的數(shù)放在數(shù)組的 右邊。要求額外空間復(fù)雜度O(1)，時間復(fù)雜度O(N)
解決方案:
劃定一個<區(qū)域 ，初始化為-1，一個>區(qū)域，初始化為arr.length()，一個指針i 初始化指向arr[0],arr[i]與num比較大小:

1. arr[i]< num; arr[i] 和<區(qū)域的下一個數(shù)交換，<區(qū)域右擴一個，同時 i++;
   2)arr[i] == num; i++
2. arr[i] >num; arr[i] 和 >區(qū)域的前一個數(shù)交換，>區(qū)域左擴一個;

例子:arr = [3,5,6,3,4,5,2,6,9,0], num = 5。整個流程如下:

java代碼:

//在數(shù)組arr中，把小于num的數(shù)放在數(shù)組左邊，等于num的數(shù)放在中間，大于num的數(shù)放在右邊
    public static int[] version2(int[] arr, int left, int right) {int leftArea = left -1;
        int rightArea = right + 1;
        int i = left;
        int num = arr[right];
        while (i != rightArea) {if (arr[i]< num) {swap(arr, i++, ++leftArea);
            }
            else if (arr[i] == num) {i++;
            }
            else {swap(arr, i, --rightArea);
            }
        }
        System.out.println("leftArea:" + leftArea + "\trightArea:" + rightArea);
        int[] res = {leftArea, rightArea};
        return res;
    }

隨機快速排序（改進的快速排序）:

1）在數(shù)組范圍中，等概率隨機選一個數(shù)作為劃分值，然后把數(shù)組通過荷蘭國旗問題分成三個部分：左側(cè)<劃分值、中間==劃分值、右側(cè)>劃分值
2）對左側(cè)范圍和右側(cè)范圍，遞歸執(zhí)行
3）時間復(fù)雜度為O(N*logN)

快排代碼如下:

package paixu;

import java.util.Arrays;

public class Kuaipai {public static void main(String[] args) {int[] arr = {3,5,6,3,4,5,2,6,9,0};
        kuaipai(arr, 0,9);
        System.out.println(Arrays.toString(arr));
    }

    //在數(shù)組arr中，把小于num的數(shù)放在數(shù)組左邊，等于num的數(shù)放在中間，大于num的數(shù)放在右邊
    public static int[] version2(int[] arr, int left, int right) {int leftArea = left -1;
        int rightArea = right + 1;
        int i = left;
        int num = arr[right];
        while (i != rightArea) {if (arr[i]< num) {swap(arr, i++, ++leftArea);
            }
            else if (arr[i] == num) {i++;
            }
            else {swap(arr, i, --rightArea);
            }
        }
        System.out.println("leftArea:" + leftArea + "\trightArea:" + rightArea);
        int[] res = {leftArea, rightArea};
        return res;
    }

    public static void kuaipai(int[] arr, int L, int R) {if (L< R) {swap(arr, L + (int)(Math.random() * (R - L - 1)), R);
            int[] p = version2(arr, L, R);
            kuaipai(arr, L, p[0]);
            kuaipai(arr, p[1], R);
        }
    }

    public static void swap(int[] arr, int i, int j) {int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

結(jié)果如下:

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前名稱：2.認識O(logN)的排序-創(chuàng)新互聯(lián)
URL標題：http://weahome.cn/article/pcheh.html