前言本文主要使用Java

什么，是快樂星球@#￥@%……什么是算法？

算法是一組完成任務(wù)的指令。任何代碼片段都可視為算法，但我們主要介紹常見算法

一、引入——二分查找

二分查找是一種算法，其輸入是一個(gè)有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否則返回 null 。

一個(gè)簡單的例子，你想一個(gè)1-100之間的數(shù)，我去猜，我猜50，你說大了或者小了，如果大了我再猜25…………不管你心里想的是哪個(gè)數(shù)字，我在7次之內(nèi)都能猜到，而一個(gè)數(shù)一個(gè)數(shù)的枚舉我可能要猜100次

一般而言，對(duì)于包含n個(gè)元素的列表，用二分查找最多需要log 2 n步，而簡單查找最多需要n步。

由此我們先引入運(yùn)行時(shí)間，每次介紹算法時(shí)，我都將討論其運(yùn)行時(shí)間。一般而言，應(yīng)選擇效率最高的算法，以最大限度地減少運(yùn)行時(shí)間或占用空間。

我們?cè)谝氪驩表示法，這是一種特殊的表示法，指出了算法的速度有多快。

假設(shè)列表包含n個(gè)元素。簡單查找需要檢查每個(gè)元素，因此需要執(zhí)行n次操作。使用大O表示法，
這個(gè)運(yùn)行時(shí)間為O(n)。單位秒呢？沒有——大O表示法指的并非以秒為單位的速度。大O表示法
讓你能夠比較操作數(shù)，它指出了算法運(yùn)行時(shí)間的增速。
再來看一個(gè)例子。為檢查長度為n的列表，二分查找需要執(zhí)行l(wèi)og n次操作。使用大O表示法，
這個(gè)運(yùn)行時(shí)間怎么表示呢？O(log n)。

所謂大O表示法，就是一個(gè)O加上（），里面放操作數(shù)

大 O 表示法指出了最糟情況下的運(yùn)行時(shí)間，比如猜1-100的數(shù)，如果你想的數(shù)字是1，我用簡單查找（枚舉）第一次就把1才出來了，運(yùn)行時(shí)間是O(n)而不是O(1)

一些常見的大 O 運(yùn)行時(shí)間

? O(log n)，也叫對(duì)數(shù)時(shí)間，這樣的算法包括二分查找。
? O(n)，也叫線性時(shí)間，這樣的算法包括簡單查找。
? O(n * log n)，這樣的算法包括第4章將介紹的快速排序——一種速度較快的排序算法。
? O(n 2 )，這樣的算法包括第2章將介紹的選擇排序——一種速度較慢的排序算法。
? O(n!)，這樣的算法包括接下來將介紹的旅行商問題的解決方案——一種非常慢的算法。

小結(jié)
? 二分查找的速度比簡單查找快得多。
? O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
? 算法運(yùn)行時(shí)間并不以秒為單位。
? 算法運(yùn)行時(shí)間是從其增速的角度度量的。
? 算法運(yùn)行時(shí)間用大O表示法表示

數(shù)組和鏈表比較

數(shù)組再讀取數(shù)據(jù)時(shí)非常迅速，指哪打哪，而鏈表就要一個(gè)一個(gè)的訪問

但是插入刪除某元素，鏈表快得多

分而治之（divide and conquer，D&C）

使用D&C解決問題的過程包括兩個(gè)步驟。
(1) 找出基線條件，這種條件必須盡可能簡單。
(2) 不斷將問題分解（或者說縮小規(guī)模），直到符合基線條件。

舉個(gè)例子，把1680 m × 640 m的土地分割成若干正方形，要求最大的正方形

首先，找出基線條件。最容易處理的情況是，一條邊的長度是另一條邊的整數(shù)倍。這樣直接就能看出要?jiǎng)澐殖蓭讉€(gè)正方形

然后需要找出遞歸條件，這正是D&C的用武之地。根據(jù)D&C的定義，每次遞歸調(diào)用都必須
縮小問題的規(guī)模。如何縮小前述問題的規(guī)模呢？我們首先找出這塊地可容納的最大方塊。

你可以從這塊地中劃出兩個(gè)640 m×640 m的方塊，同時(shí)余下一小塊地?；腥淮笪?#xff1a;何
不對(duì)余下的那一小塊地使用相同的算法呢

?故，這款土地，適用的最大方塊為80*80

以上就是算法簡單引入，下面就開始舉幾個(gè)具體例子了

1.打印原碼

package class01;public class Code01_PrintBinary {public static void print(int num) {for (int i = 31; i >= 0; i--) {System.out.print((num & (1 << i)) == 0 ? "0" : "1");} //算法分析n&x，x第i位是1，其余是0，結(jié)果：n的第i位為一就保留為0就置0//然后從高位到低位依次打印每一位System.out.println();}public static void main(String[] args) {//整數(shù)都是32位的int num = 4;print(num);00000000...0100int test = 1123123;//演示左移效果print(test);print(test<<1);print(test<<2);print(test<<8);int a = Integer.MAX_VALUE; //a=整數(shù)里的最大值 2^31-1,非負(fù)數(shù)0-2^31-1System.out.println(a);print(-1);int a = Integer.MIN_VALUE; // 負(fù)數(shù)-1- -2^31print(a);int b = 123823138;int c = ~b;print(b);print(c);print(-5);System.out.println(Integer.MIN_VALUE);System.out.println(Integer.MAX_VALUE);int a = 12319283;int b = 3819283;print(a);print(b);System.out.println("============="); //位運(yùn)算等，演示print(a | b);print(a & b);print(a ^ b);int a = Integer.MIN_VALUE;print(a);print(a >> 1); //a右移前面的用0來補(bǔ)齊print(a >>> 1); //a右移前面的用符號(hào)位來補(bǔ)齊int c = Integer.MIN_VALUE;int d = -c ; //最小值取反還是最小值.此外求一個(gè)數(shù)的相反數(shù)可以~x+1也可-xprint(c);print(d);}}

題目：給定一個(gè)參數(shù)N，返回1！+2！+3！+++N!

package class01;public class Code02_SumOfFactorial {//用兩種算法計(jì)算n！的前n項(xiàng)和
//定義一個(gè)第i項(xiàng)階乘函數(shù)public static long factorial(int N) {long ans = 1;for (int i = 1; i <= N; i++) {ans *= i;}return ans;}
//第一種 1！+2！++++public static long f1(int N) {long ans = 0;for (int i = 1; i <= N; i++) {ans += factorial(i);}return ans;}
//第二種 有了5！，×6得到6！，然后在累加public static long f2(int N) {long ans = 0;long cur = 1;for (int i = 1; i <= N; i++) {cur = cur * i;ans += cur;}return ans;}public static void main(String[] args) {int N = 10;System.out.println(f1(N));System.out.println(f2(N));}}

?2.排序算法（選擇，冒泡，插入）&生成隨機(jī)數(shù)

package class01;public class Code03_Sort {public static void swap(int[] arr, int i, int j) {  //交換函數(shù)int tmp = arr[j];arr[j] = arr[i];arr[i] = tmp;}
//選擇排序public static void selectSort(int[] arr) {if (arr == null || arr.length < 2) {  //先判斷合法性，1/沒有數(shù)就不排return;}int N = arr.length;
//思路，比較n次，每一次挑選出一個(gè)最小的值，外層for n次，內(nèi)層“整”
//每一次怎么整，假設(shè)第0個(gè)數(shù)最小，0-1，1-2,1-3,1-4...依次比較，一個(gè)變一個(gè)不變，
//令j，j范圍i+1到N-1
//比較，0-1比較i和j比較，從小到大for (int i = 0; i < N; i++) {int minValueIndex = i;for (int j = i + 1; j < N; j++) {minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;}swap(arr, i, minValueIndex);}}
//冒泡排序，每兩個(gè)相鄰元素比較，大的往后放public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;for (int end = N - 1; end >= 0; end--) {for (int second = 1; second <= end; second++) {if (arr[second - 1] > arr[second]) {swap(arr, second - 1, second);}    //外層for怎么來的，冒第一趟0-n-1，最后一個(gè)數(shù)定住了，下一趟前n-1個(gè)數(shù)，}    //0-n-2，....0-1,令end=n-1，end--外層循環(huán)，每一次循環(huán)整一下}    //每一次怎么整，0-1,1-2，。。。兩兩比較，兩個(gè)數(shù)都在變，設(shè)一個(gè)未知量（右邊的數(shù)）}    令為second，取值1 - n-1那左邊的數(shù)就是second-1，
//冒泡排序法二public static void insertSort1(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;for (int end = 1; end < N; end++) {int newNumIndex = end;while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) {swap(arr, newNumIndex - 1, newNumIndex);newNumIndex--;}}}public static void insertSort2(int[] arr) {if (arr == null || arr.length < 2) {return;}int N = arr.length;for (int end = 1; end < N; end++) {for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {swap(arr, pre, pre + 1);}}}public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = { 7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6 };printArray(arr);insertSort2(arr);printArray(arr);}}

選擇排序

package class01;import java.util.Arrays;public class Code04_SelectionSort {public static void selectionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length - 1; i++) { int minIndex = i;for (int j = i + 1; j < arr.length; j++) {if(arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr, i, minIndex);}}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) {// Math.random() [0,1)// Math.random() * N [0,N)// (int)(Math.random() * N) [0, N-1]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);selectionSort(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);selectionSort(arr);printArray(arr);}}

冒泡排序

package class01;import java.util.Arrays;public class Code05_BubbleSort {public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int end = arr.length - 1; end > 0; end--) {for (int i = 0; i < end; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);}}}}// 交換arr的i和j位置上的值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) {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);bubbleSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);bubbleSort(arr);printArray(arr);}}

插入排序

package class01;import java.util.Arrays;public class Code06_InsertionSort {public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}// i和j,數(shù)交換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) {// Math.random() ->  [0,1) 所有的小數(shù)，等概率返回一個(gè)// Math.random() * N -> [0,N) 所有小數(shù)，等概率返回一個(gè)// (int)(Math.random() * N) -> [0,N-1] 所有的整數(shù)，等概率返回一個(gè)int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 長度隨機(jī) 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; // 隨機(jī)數(shù)組的長度0～100int maxValue = 100;// 值：-100～100boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);insertionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {// 打印arr1// 打印arr2succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);insertionSort(arr);printArray(arr);}}