java各种算法实现

 

java 算法学习记录

二分法

/** * @param key 需要找的数字 * @param array 排序好的数组 * @return int 返回-1表示未找到，若找到返回数组下标 */ public static int rank(int key, int [] array){ if(array == null){ return -1; } //array必须为有序的 int left = 0; //array.length 返回的是数组的个数 int right = array.length - 1; while(right >= left){ //每次循环更新mid的值 int mid = left + (right - left) / 2; // System.out.print(mid); if(array[mid] == key){ return mid; }else if(array[mid] > key){ right = mid -1; }else{ left = mid + 1; } } return -1; }

10进制整型转其他进制数

/** * @param number 需要转换的整型数 * @param other 需要转换的进制 */ public static String transfer(int number, int other){ int number2 = Math.abs(number); String res = ""; //倒取余数法 for(int i = number2; i > 0; i /= other){ res = i % other + res; } return number >= 0 ? res : '-' + res; }

判断回文字符串

/** * @param s 需要判断的字符串 */ public static Boolean isPlaindrome(String s){ if(s == null){ return false; } int length = s.length(); for(int i = 0; i < (length -1) / 2; i++ ){ if(s.charAt(i) != s.charAt(length -1 - i)){ return false; } } return true; }

算术表达式求值

//形如（1+（12*12））子表达式要带括号，双栈法 public static double caculateEqual(String str){ if(str.isEmpty()) return 0; Stack<Double> nums = new Stack<>(); Stack<Character> oprs = new Stack<>(); int flag = 0; for(int i = 0 ; i< str.length(); i++){ Character value = str.charAt(i); switch (value){ case '+': case '-': case '%': case '/': case '*': flag = 0; oprs.push(value); break; case ')': char opr = oprs.pop(); double num1 = nums.pop(); double num2 = nums.pop(); if(opr == '+'){ nums.push(num1 + num2); } if(opr == '-'){ nums.push(num1 - num2); } if(opr == '*'){ nums.push(num1 * num2); } if(opr == '/'){ nums.push(num1 / num2); } if(opr == '%'){ nums.push(num1 % num2); } flag = 0; break; case ' ': case '(': flag = 0; break; default: String numStr = str.substring( i - flag ,i+1); if(flag > 0 ){ nums.pop(); } nums.push(Double.parseDouble(numStr)); flag++; } } return nums.pop(); }  

 

单链表反转

package chapter2; public class ReverseLinkNode<T>{ private Node<T> first; private int size; public ReverseLinkNode(){ first = null; size = 0; } private class Node<T>{ private Node<T> next; private T value; public Node(){ next = null; value = null; } public Node(T value){ next = null; this.value = value; } } public void addNode(T nodeValue){ if(first == null){ first = new Node<T>(nodeValue); return; } Node<T> curNode = first; while(curNode.next != null){ curNode = curNode.next; } curNode.next = new Node<T>(nodeValue); size++; } public void reverse(){ if(first == null || first.next == null) return ; Node<T> curNode = first; Node<T> preNode = null; while(curNode != null){ Node<T> nexNode = curNode.next; curNode.next = preNode; preNode = curNode; curNode = nexNode; } this.first = preNode; } public void reverse2(Node<T> curNode, Node<T> preNode){ if(curNode == null ){ this.first = preNode; return ; } Node<T> nexNode = curNode.next; curNode.next = preNode; reverse2(nexNode, curNode); } public Node<T> getFirst(){ return first; } public String toString(){ if(first == null) return null; Node<T> curNode = first; StringBuilder res = new StringBuilder(); res.append("linkedValues:"); while(curNode != null){ res.append(curNode.value); res.append(" "); curNode = curNode.next; } return res.toString(); } }

冒泡、选择、插入、归并和快排排序

package chapter3; import chapter2.ReverseLinkNode; public class SelectionSort { //can not be instanced private SelectionSort(){ } //sort with comparable interface public static void selectionsSort(Comparable[] a){ int length = a.length; for(int i = 0; i < length; i++){ int index = i; System.out.println(index); for(int j = i + 1 ; j < length; j++ ){ if(a[j].compareTo(a[index]) < 0){ index = j; }else { break; } } exchange(a, i , index); } } //sort with comparable interface public static void insertSort(Comparable[] a){ int length = a.length; for(int i = 1; i < length; i++){ for(int j = i ; j >= 1; j-- ){ if(a[j].compareTo(a[j - 1]) > 0){ exchange(a, j , j - 1); } } } } //sort with comparable interface public static void maoPaoSort(Comparable[] a){ int length = a.length; for(int i = 0; i < length; i++){ for(int j = 0 ; j < length - i - 1; j++ ){ if(a[j].compareTo(a[j + 1]) > 0){ exchange(a, j , j + 1); } } } } public static void mergeSort(Comparable[] a){ Comparable[] b = new Comparable[a.length]; sort(a, b, 0, a.length - 1 ); } private static void sort(Comparable[] a, Comparable[] b, int low, int high){ if(low == high) return; int mid = low + (high - low) / 2; //left sort sort(a, b, low, mid); //right sort sort(a, b, mid + 1, high); merge(a, b, low, mid, high); } public static void merge(Comparable[] a, Comparable[] b, int low, int mid, int high){ if(a[mid].compareTo(a[mid + 1]) <= 0) return; for(int i = low; i <= high; i++) b[i] = a[i]; int lowIndex = low; int highIndex = mid +1; for(int i = low; i <= high; i++){ if (lowIndex > mid ) a[i] = b[highIndex++]; else if(highIndex > high) a[i] = b[lowIndex++]; else if(b[lowIndex].compareTo(b[highIndex]) > 0) a[i] = b[highIndex++]; else a[i] = b[lowIndex++]; } } //exchange value public static void exchange(Object[] a, int i, int j){ Object swap = a[i]; a[i] = a[j]; a[j] = swap; } //compare, defined by comparable function public static boolean compareBig (Comparable[] a, int i, int j){ return a[i].compareTo(a[j]) > 0; } public static void sortPrint(Object[] a){ StringBuilder s = new StringBuilder(); for (Object o : a) { s.append(o); s.append(" "); } System.out.println(s.toString()); } public static void quickSort(Comparable[] a){ qSort(a, 0, a.length -1); } private static void qSort(Comparable[] a, int low, int high){ if(low >= high) return; int quickPoint = qMerge(a, low, high); qSort(a, low, quickPoint -1); qSort(a, quickPoint +1, high); } private static int qMerge(Comparable[] a, int left, int right ){ int li = left; int ri = right + 1; while(true){ while(a[++li].compareTo(a[left]) < 0){ if(li == right){ break; } } while(a[--ri].compareTo(a[left]) > 0){ if(ri == left){ break; } } if(li >= ri){ break; }else{ exchange(a, li, ri); } } exchange(a, left, ri); return ri; } public static void main(String[] args) { Integer[] a = {6, 2, 3, 4, 9, 11, 15, 16, 1, 6}; quickSort(a); sortPrint(a); } }