算法
常见算法
写在这里,以便查阅, 有时间的话在 leetcode 上刷个 100-200 道 easy 和 medium 的题
排序算法
快速排序
快速排序是冒泡排序的改进算法
递归式
左右指针法
void QuickSort(int* array,int left,int right) { assert(array); if(left >= right)//表示已经完成一个组 { return; } int index = PartSort(array,left,right);//枢轴的位置 QuickSort(array,left,index - 1); QuickSort(array,index + 1,right); }
代码
int PartSort(int* array,int left,int right) { int& key = array[right]; while(left < right) { while(left < right && array[left] <= key) { ++left; } while(left < right && array[right] >= key) { --right; } swap(array[left],array[right]); } swap(array[left],key); return left; }
非递归式
递归的算法主要是在划分子区间,如果要非递归实现快排,只要使用一个栈来保存区间就可以了。 一般将递归程序改成非递归首先想到的就是使用栈,因为递归本身就是一个压栈的过程。
void QuickSortNotR(int* array,int left,int right) { assert(array); stack<int> s; s.push(left); s.push(right);// 后入的 right,所以要先拿 right while(!s.empty)// 栈不为空 { int right = s.top(); s.pop(); int left = s.top(); s.pop(); int index = PartSort(array,left,right); if((index - 1) > left) // 左子序列 { s.push(left); s.push(index - 1); } if((index + 1) < right) // 右子序列 { s.push(index + 1); s.push(right); } } }
二分法
public static Integer search(int[] a, int x) { int low = 0, high = a.length - 1; // 0 1 2 4 5 int mid = (low + high) / 2; while (a[mid] != x) { if(a[mid] > x) { high = mid; } else { low = mid; } mid = (low + high) / 2; } // 此时 mid 下标的值对 x, 但还不能保证这是最小的下标 while (a[mid] == x) mid--; // 减过头了得加 1 mid++; return mid; }
堆排序
斐波那数列
0 1 1 2 3 5 8...
使用递归会导致栈溢出,此处使用尾递归,或者称之为迭代
public static int foo(int n, int x, int y){ if(n == 0) { return x; } return foo(n - 1, y, x + y); } public static void main(String[] args) { // F(n) = foo(n, 0, 1); foo(n, 0, 1); }
String 转 double
主要思路是以整数形式分别记录整数部分和小数部分
public static Double toDouble(String s) { if(s == null) { return null; } int len = s.length(); int I = 0; int S = 0; int index = -1; int smallLen = 0; for(int i = 0; i < len; i++) { if(index == -1 && s.charAt(i) != '.') { if(I != 0) { I *= 10; } I += (s.charAt(i)-'0'); } else if(index != -1) { if(S != 0) { S *= 10; } S += (s.charAt(i)-'0'); smallLen++; } else { index = i; } } System.out.println(I); System.out.println(S); return I + S * Math.pow(10, -smallLen); }
发表评论
评论列表, 共 0 条评论