遞歸
例子引出
- 使用遞歸的方法求出數(shù)組中的最大值（利用的是棧）
- 求中點的方法改進
mid = (left + right) / 2 //但是如果left和right的數(shù)很大，相加會造成內(nèi)容溢出
改進為 mid = left + (right - left) / 2 //(right - left)得到整個的長度，除以2之后，再加上左邊的點，就可以得到中點的位置
改進為 mid = left + (right - left) >> 1 //使用位運算，加快計算速度
代碼?
package com.example.demo.class01;public class Code08_GetMax {public static void main(String[] args) {int arr[] = {1,2,4,3,2,8,6};int c = 0;c = getMax(arr);System.out.println(c);}public static int getMax(int[] arr){if(arr == null || arr.length == 0){System.out.println("輸入數(shù)組不合理");}return process(arr,0,arr.length - 1);}public static int process(int[] arr,int L,int R){if(L == R){return arr[L];} //arr[L..R]只有一個數(shù)的時候，直接返回，base caseint mid = L + ((R - L)>>1);int leftMax = process(arr,L,mid);int rightMax = process(arr,mid+1,R);return Math.max(leftMax,rightMax);}
}
//8
master公示的使用
- 用于分析遞歸，用于解決 子問題規(guī)模 是一致的問題
T(N) = a*T(N/b) + O(N^d)1,log(b,a) > d -> 復雜度為O(N^log(b,a))
2,log(b,a) = d -> 復雜度為O(N^d * logN)
3,log(b,a) < d -> 復雜度為O(N^d)
歸并排序
- 整體就是一個簡單排序，左邊排好順序，右邊排好順序，使整體有序
- 時間復雜度是O(N*logN)
- 額外復雜度是O(N)
-
代碼
package com.example.demo.class01;import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) {return;}process(arr, 0, arr.length - 1);}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);}public static void merge(int[] arr, int L, int M, int R) {int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= M) {help[i++] = arr[p1++];}while (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);mergeSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);mergeSort(arr);printArray(arr);}}
小和問題
使用歸并排序解決小和問題
- 歸并排序，遇到相同的元素，先移動左側(cè)，是為了保證程序的穩(wěn)定性；而這里先移動右側(cè)的元素，是為了確定比左側(cè)指針指向的元素大的右側(cè)區(qū)塊中的元素的個數(shù)
- 小和問題出現(xiàn)在三個地方：左側(cè)區(qū)塊內(nèi)排序；右側(cè)區(qū)塊內(nèi)排序；左右側(cè)區(qū)塊合并
代碼
package class02;public class Code02_SmallSum {public static int smallSum(int[] arr) {if (arr == null || arr.length < 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序，也要求小和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);}public static int merge(int[] arr, int L, int m, int r) {int[] help = new int[r - L + 1];int i = 0;int p1 = L;int p2 = m + 1;int res = 0;while (p1 <= m && p2 <= r) {res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= m) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}return res;}// for testpublic static int comparator(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int res = 0;for (int i = 1; i < arr.length; i++) {for (int j = 0; j < i; j++) {res += arr[j] < arr[i] ? arr[j] : 0;}}return res;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);if (smallSum(arr1) != comparator(arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");}}
- 類似于逆序?qū)栴}：如果左邊的數(shù)比右邊的數(shù)大，則二者構(gòu)成一個逆序?qū)?#xff0c;原理類似
- res += arr[p1] > arr[p2] ? (m - p1 +1) : 0;
荷蘭國旗問題
- 快速排序?
- 給定數(shù)組arr和數(shù)num，將小于等于num的數(shù)放在數(shù)組的左邊，大于num的數(shù)放在數(shù)組的右邊，要求時間復雜度為O(N),空間復雜度為O(1);不要求內(nèi)部有序
- 將數(shù)組分為三個部分，以num為界限，分為小于等于區(qū)、大于區(qū)和待定區(qū)。指針指向數(shù)組的第一個元素，判定指針指向的元素是否小于等于num，如果成立當前數(shù)和小于等于區(qū)的下一個數(shù)交換，然后小于等于區(qū)向右移動，指針也向右移動
- 如果指針指向的元素大于num，那么指針直接跳過該元素，向右移動。
package class02;public class Code05_NetherlandsFlag {public static int[] partition(int[] arr, int l, int r, int p) {int less = l - 1;int more = r + 1;while (l < more) {if (arr[l] < p) {swap(arr, ++less, l++);} else if (arr[l] > p) {swap(arr, --more, l);} else {l++;}}return new int[] { less + 1, more - 1 };}// for testpublic static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static int[] generateArray() {int[] arr = new int[10];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 3);}return arr;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] test = generateArray();printArray(test);int[] res = partition(test, 0, test.length - 1, 1);printArray(test);System.out.println(res[0]);System.out.println(res[1]);}
}
第二個問題
- 荷蘭國旗問題：給定數(shù)組arr和數(shù)num，將小于等于num的數(shù)放在數(shù)組的左邊，等于num的數(shù)放在數(shù)組的中間，大于num的數(shù)放在數(shù)組的右邊，要求時間復雜度為O(N),空間復雜度為O(1)
- 將數(shù)組分為三個部分，小于區(qū)、中間區(qū)和大于區(qū)。
- 首先用指針指向數(shù)組的第一個元素，如果當前指向的數(shù)小于num，則小于區(qū)下一個元素和當前數(shù)值側(cè)面交換，小于區(qū)域向右邊擴，指針向右邊移動
- 如果當前指針指向的元素和num相等，那么指針直接跳過，移動到下一個位置
- 如果當前指針指向的元素大于num，那么大于區(qū)的前一個元素和當前指針指向的元素交換，大于區(qū)域向左邊擴展，但是當前指針不可以移動位置，因為，交換了元素，不知道這個交換元素和num的大小
package class02;import java.util.Arrays;public class Code06_QuickSort {public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) {return;}quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int l, int r) {if (l < r) {swap(arr, l + (int) (Math.random() * (r - l + 1)), r);int[] p = partition(arr, l, r);quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] + 1, r);}}public static int[] partition(int[] arr, int l, int r) {int less = l - 1;int more = r;while (l < more) {if (arr[l] < arr[r]) {swap(arr, ++less, l++);} else if (arr[l] > arr[r]) {swap(arr, --more, l);} else {l++;}}swap(arr, more, r);return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {//l到r隨機選一個數(shù)做等概率劃分 ，最差情況發(fā)生概率下降int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);quickSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);quickSort(arr);printArray(arr);}}
總結(jié)
以上是生活随笔為你收集整理的算法入门篇二 认识O(NlogN)的排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
