java学习必精通算法（手写）-上篇

算法流

1.欧几里得算法（辗转相除法）：2.冒泡排序：3. 选择排序：4.插入排序：5.希尔排序：6.快速排序：7.二分查找：8.karatsuba算法：

1.欧几里得算法（辗转相除法）：

public class HelloWorld { public static int gcd(int a , int b){ if (b == 0) return a; int r = a % b; return gcd(b ,r); } public static void main(String []args) { int a = 10; int b = 2; System.out.println(gcd(a , b)); } }

2.冒泡排序：

从下标为0的元素开始，左右两两比较（以升序为例子），即句柄0的元素云句柄1的元素比较，小的在左大的在右，句柄1的元素云句柄2的元素比较，小的在左大的在右，句柄2的元素云句柄3的元素比较，小的在左大的在右…如此下去，直到倒数第二个与最后一个比较完，这番视为第一趟；其实不难发现，趟数=数组大小-1。

public class HelloWorld { public static void main(String []args) { int[] array = {2 ,1 , 6 , 5 ,11 ,7 ,10}; for(int i =0; i<array.length-1 ;i++) //趟数 for(int j=0 ; j< array.length-1 ;j++)//每趟j从第一个元素开始直到倒数第二个 if(array[j]>array[j+1]) { int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } for(int a : array) System.out.print(a+" "); } }

3. 选择排序：

思路，第0趟，从句柄为0的元素开始，遍历句柄0、1、2…length-1，与句柄为0的元素比较；第1趟，从句柄为1的元素开始，遍历句柄1、2…length-1，与句柄为1的元素比较；第二趟，从句柄为2的元素开始，遍历句柄2…length-1，与句柄为2的元素比较；…直到倒数第2趟从句柄为array.length-1的元素开始，遍历句柄array.length-1…length-1，与句柄为array.length-1的元素比较；倒数第二趟排好了，最后一个元素自然是排好序了。

public class HelloWorld { public static void main(String []args) { int[] array = {2 ,1 , 6 , 5 ,11 ,7 ,10 , 4}; for(int i =0; i<array.length-1 ;i++){ int index = i; for(int j=i ; j< array.length ;j++) { if(array[j]<array[index]) { int temp = array[j]; array[j] = array[index]; array[index] = temp; } } } for(int a : array) System.out.print(a+" "); } }

4.插入排序：

将一个数组分为两部分，一部分为有序，另一部分为无序，每次从无序中去第一个放进有序中排序；注意，第一个元素视为有序部分中的第一个元素，故第一趟从第二个元素开始，第三趟从第三个元素开始，依次下去；取无序中元素在有序元素中排序是一个前移的过程，故要在有序部分中维持一个尾部索引j不变，同时维持一个指向前移元素的索引i（元素位置变，即产生交换是位置会变，索引也要变）；指向前移元素的索引i=有序部分尾部索引j+1；

public class HelloWorld { public static void main(String []args) { int[] array = {2 ,1 , 6 , 5 ,11 ,7 ,10 , 4}; for(int i = 1; i<array.length ; i++) { int temp_i = i; for(int j=i-1 ; j>= 0 && array[j]>array[temp_i] ;j--) { int temp = array[j]; array[j] = array[temp_i]; array[temp_i] = temp; temp_i--; } } for(int a : array) System.out.print(a+" "); } }

5.希尔排序：

增量相同的元素为一组；每次的增量中，从第一组的第二元素开始，即for(int i = rise ; i < array.length ;i++)，每组中从第二个元素开始执行快速排序，因此只要将快速排序算法的间隔调好即可。

public class HelloWorld { public static void inserted(int[] array ,int rise , int i) { for(; i<array.length ; i++) { int temp_i = i; for(int j = i - rise; j>= 0 && array[j]>array[temp_i] ;j -= rise)//转换成同组元素的有序部分进行快速排序 { int temp = array[j]; array[j] = array[temp_i]; array[temp_i] = temp; temp_i -= rise; } } } public static void main(String []args) { int[] array = {2 ,1 , 6 , 5 ,11 ,7 ,10 , 4}; int rise = array.length/2; for( ; rise > 0 ; rise/=2) for(int i = rise ; i < array.length ;i++) inserted(array , rise , i); for(int a : array) System.out.print(a+" "); } }

6.快速排序：

以数组中第一个数为基准数，维持极左和极右两个索引，从基准数开始遍历，在左指针与右指针相遇之前，右指针向左遍历直至找到一个比基准数小的数，左指针向左遍历直至找到一个比基准数大的数，交换…直至左指针与右指针相遇，再把基准数放到指针相遇的地方，这是一趟过程，得到的结果是基准数在中间，基准数左边的数比基准数小，基准数右边的数比基准数大，最后基准数左右两边自成数组，改变双指针指向继续递归分治。

public class HelloWorld { public static void FindMiddle(int[] array ,int left ,int right ) { if(left>right) return; int i =left; int j = right; int temp = array[left]; while(i < j) { while(array[j]>=temp&&i<j) { j--; } while(array[i]<=temp&&i<j) { i++; } if(i<j) swap(array , i ,j); } int temp1 = array[i]; array[i] = temp; array[left] = temp1; FindMiddle(array ,left,i-1 ); FindMiddle(array , i+1 ,right ); } public static void swap(int[] array , int index1 , int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } public static void main(String []args) { int[] array = {2 ,1 , 6 , 5 ,11 ,7 ,10 , 4}; int left = 0; int right = array.length-1; FindMiddle(array ,left , right ); for(int a : array) System.out.print(a+" "); } }

7.二分查找：

public class HelloWorld { public static int bin(int[] array , int num , int low ,int high) { int middle = (low + high)/2; if(array[middle] == num) return middle; else if(array[middle] > num) return bin(array , num , low ,middle - 1); else if(array[middle] < num) return bin(array , num , middle+1 ,high); else return -1; } public static void main(String []args) { int[] array ={5,7,10,15,19,20,89,100,150}; int low = 0 ; int high = array.length-1; int num = 100; //sort(array); System.out.print(bin(array , num , low , high)); } }

8.karatsuba算法：

大数相乘，将num1和num2切分成长度相同的两部分，如num1切分成a,b两部分，num2切分成c,d两部分，然后以ac，bd，(a+b)*(c+d)-ac-bd分别作为参数递归karatsuba算法，返回ac*10*2half+bd+((a+b)*(c+d)-ac-bd)*10*half。 领悟

public class HelloWorld { public static long karatsuba(long num1, long num2) { if(num1 <10 || num2 < 10) return num1*num2; int size1 = String.valueOf(num1).length(); int size2 = String.valueOf(num2).length(); int half = Math.max(size1 , size2)/2; long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - half)); long b = Long.valueOf(String.valueOf(num1).substring(size1 - half)); long c = Long.valueOf(String.valueOf(num2).substring(0, size1 - half)); long d = Long.valueOf(String.valueOf(num2).substring(size1 - half)); long x = karatsuba(a, c); long y = karatsuba(b, d); long z = karatsuba(a+b, c+d) - x - y; return (long)(x*Math.pow(10 , 2*half) + y + z*Math.pow(10 , half)); } public static void main(String []args) { System.out.println(karatsuba(100, 100)); } }