怎么做网站地图导航,亿网域名,个人网站必须备案,高端网站设计服务商前言本文主要使用Java 什么#xff0c;是快乐星球##xffe5;%……什么是算法#xff1f;
算法是一组完成任务的指令。任何代码片段都可视为算法#xff0c;但我们主要介绍常见算法
一、引入——二分查找
二分查找是一种算法#xff0c;其输入是一个有序的元素列表。如…前言本文主要使用Java 什么是快乐星球#%……什么是算法
算法是一组完成任务的指令。任何代码片段都可视为算法但我们主要介绍常见算法
一、引入——二分查找
二分查找是一种算法其输入是一个有序的元素列表。如果要查找的元素包含在列表中二分查找返回其位置否则返回 null 。
一个简单的例子你想一个1-100之间的数我去猜我猜50你说大了或者小了如果大了我再猜25…………不管你心里想的是哪个数字我在7次之内都能猜到而一个数一个数的枚举我可能要猜100次
一般而言对于包含n个元素的列表用二分查找最多需要log 2 n步而简单查找最多需要n步。
由此我们先引入运行时间每次介绍算法时我都将讨论其运行时间。一般而言应选择效率最高的算法以最大限度地减少运行时间或占用空间。
我们在引入大O表示法这是一种特殊的表示法指出了算法的速度有多快。
假设列表包含n个元素。简单查找需要检查每个元素因此需要执行n次操作。使用大O表示法 这个运行时间为O(n)。单位秒呢没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数它指出了算法运行时间的增速。 再来看一个例子。为检查长度为n的列表二分查找需要执行log n次操作。使用大O表示法 这个运行时间怎么表示呢O(log n)。
所谓大O表示法就是一个O加上里面放操作数
大 O 表示法指出了最糟情况下的运行时间比如猜1-100的数如果你想的数字是1我用简单查找枚举第一次就把1才出来了运行时间是O(n)而不是O(1)
一些常见的大 O 运行时间
O(log n)也叫对数时间这样的算法包括二分查找。 O(n)也叫线性时间这样的算法包括简单查找。 O(n * log n)这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 O(n 2 )这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 O(n!)这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
小结 二分查找的速度比简单查找快得多。 O(log n)比O(n)快。需要搜索的元素越多前者比后者就快得越多。 算法运行时间并不以秒为单位。 算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示
数组和链表比较 数组再读取数据时非常迅速指哪打哪而链表就要一个一个的访问
但是插入删除某元素链表快得多
分而治之divide and conquerDC
使用DC解决问题的过程包括两个步骤。 (1) 找出基线条件这种条件必须尽可能简单。 (2) 不断将问题分解或者说缩小规模直到符合基线条件。
举个例子把1680 m × 640 m的土地分割成若干正方形要求最大的正方形
首先找出基线条件。最容易处理的情况是一条边的长度是另一条边的整数倍。这样直接就能看出要划分成几个正方形
然后需要找出递归条件这正是DC的用武之地。根据DC的定义每次递归调用都必须 缩小问题的规模。如何缩小前述问题的规模呢我们首先找出这块地可容纳的最大方块。
你可以从这块地中划出两个640 m×640 m的方块同时余下一小块地。恍然大悟何 不对余下的那一小块地使用相同的算法呢 故这款土地适用的最大方块为80*80
以上就是算法简单引入下面就开始举几个具体例子了
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);} //算法分析nxx第i位是1其余是0结果n的第i位为一就保留为0就置0//然后从高位到低位依次打印每一位System.out.println();}public static void main(String[] args) {//整数都是32位的int num 4;print(num);00000000...0100int test 1123123;//演示左移效果print(test);print(test1);print(test2);print(test8);int a Integer.MAX_VALUE; //a整数里的最大值 2^31-1,非负数0-2^31-1System.out.println(a);print(-1);int a Integer.MIN_VALUE; // 负数-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(); //位运算等演示print(a | b);print(a b);print(a ^ b);int a Integer.MIN_VALUE;print(a);print(a 1); //a右移前面的用0来补齐print(a 1); //a右移前面的用符号位来补齐int c Integer.MIN_VALUE;int d -c ; //最小值取反还是最小值.此外求一个数的相反数可以~x1也可-xprint(c);print(d);}}题目给定一个参数N返回123N! package class01;public class Code02_SumOfFactorial {//用两种算法计算n的前n项和
//定义一个第i项阶乘函数public static long factorial(int N) {long ans 1;for (int i 1; i N; i) {ans * i;}return ans;}
//第一种 12public 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.排序算法选择冒泡插入生成随机数
package class01;public class Code03_Sort {public static void swap(int[] arr, int i, int j) { //交换函数int tmp arr[j];arr[j] arr[i];arr[i] tmp;}
//选择排序public static void selectSort(int[] arr) {if (arr null || arr.length 2) { //先判断合法性1/没有数就不排return;}int N arr.length;
//思路比较n次每一次挑选出一个最小的值外层for n次内层“整”
//每一次怎么整假设第0个数最小0-11-2,1-3,1-4...依次比较一个变一个不变
//令jj范围i1到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);}}
//冒泡排序每两个相邻元素比较大的往后放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最后一个数定住了下一趟前n-1个数} //0-n-2....0-1,令endn-1end--外层循环每一次循环整一下} //每一次怎么整0-1,1-2。。。两两比较两个数都在变设一个未知量右边的数} 令为second取值1 - n-1那左边的数就是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,数交换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; // 随机数组的长度0100int maxValue 100;// 值-100100boolean 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);}}
