publicclassQuickSort{ privatestaticvoidswap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
privatestaticintpartition(int[] arr, int left, int right){ int j = left - 1; for(int i = left; i < right; i++) if (arr[i] < arr[right]) swap(arr, i, ++j); swap(arr, right, ++j); return j; }
publicstaticvoidsort(int[] arr, int left, int right){ if(left < right){ int index = partition(arr, left, right); sort(arr, left, index - 1); sort(arr, index + 1, right); } }
publicclassQuickSort2{ privatestaticvoidswap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
privatestaticintpartition(int[] arr, int left, int right){ int j = left - 1; for(int i = left; i < right; i++) if(arr[i] < arr[right]) swap(arr, i, ++j); swap(arr, right, ++j); return j; }
publicstaticvoidsort(int[] arr, int left, int right){ if (left >= right) return; LinkedList<Integer> stack = new LinkedList<>(); stack.push(left); stack.push(right); while (!stack.isEmpty()){ int end = stack.pop(); int begin = stack.pop(); if (begin < end){ int index = partition(arr, begin, end); stack.push(begin); stack.push(index - 1); stack.push(index + 1); stack.push(end); } } }
voidbubble_sort(int* a, int left, int right){ int tmp; for(int i = left; i < right; i++){ for(int j = right; j > i; j--){ if(a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp; } } }
intpartition(int* a, int left, int right, int baseIdx){ int j = left - 1, tmp; // 将基准放于数组尾部 tmp = a[right], a[right] = a[baseIdx], a[baseIdx] = tmp; for(int i = left; i < right; i++){ if(a[i] <= a[right]) tmp = a[i], a[i] = a[++j], a[j] = tmp; } tmp = a[right], a[right] = a[++j], a[j] = tmp; return j; }
intbfprt(int* a, int left, int right, int k){ if(right - left + 1 <= 5){ // 小于等于5个数,直接排序得到结果 bubble_sort(a, left, right); return a[left + k - 1]; } int t = left - 1, tmp; // t:当前替换到前面的中位数的下标 for(int st = left, ed; (ed = st + 4) <= right; st += 5){ bubble_sort(a, st, ed); // 将中位数替换到数组前面,便于递归求取中位数的中位数 tmp = a[++t], a[t] = a[st+2], a[st+2] = tmp; } int baseIdx = (left + t) >> 1; // left到t的中位数的下标,作为主元的下标 bfprt(a, left, t, baseIdx - left + 1); // 不关心中位数的值,保证中位数在正确的位置 int idx = partition(a, left, right, baseIdx), cur = idx - left + 1; if(k == cur) return a[idx]; elseif(k < cur) return bfprt(a, left, idx - 1, k); elsereturn bfprt(a, idx + 1, right, k - cur); }
动态规划
基本步骤
找出最优解的性质,并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息,构造最优解。
矩阵连乘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicstaticvoidmatrixChain(int[] p, int[][] m, int[][] s){ int n = p.length - 1; for (int i = 1; i <= n; i++) m[i][i] = 0; for (int r = 2; r <= n; r++) for (int i = 1; i <= n - r + 1; i++) { int j = i + r - 1; m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; s[i][j] = i; for (int k = i + 1; k < j; k++) { int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if (t < m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } }
publicstaticfloatknapsack(float c, float[] w, float[] v,float[] x){ int n = v.length; Element [] d = new Element [n]; for (int i = 0; i < n; i++) d[i] = new Element(w[i], v[i], i); MergeSort.mergeSort(d); int i; float opt = 0; for (i = 0; i < n; i++) x[i] = 0; for (i = 0; i < n; i++) { if (d[i].w > c) break; x[d[i].i] = 1; opt += d[i].v; c -= d[i].w; } if (i < n){ x[d[i].i] = c / d[i].w; opt += x[d[i].i] * d[i].v; } return opt; }
publicstaticfloatloading(float c, float[] w, int[] x){ int n = w.length; Element [] d = new Element [n]; for (int i = 0; i < n; i++) d[i] = new Element(w[i], i); MergeSort.mergeSort(d); float opt = 0; for (int i = 0; i < n; i++) x[i] = 0; for (int i = 0; i < n && d[i].w <= c; i++) { x[d[i].i] = 1; opt += d[i].w; c -= d[i].w; } return opt; }
intkrustral(){ sort(es, es + E, comp); // 按照edge.cost的顺序从小到大排列 init_union_find(V); // 并查集初始化 int res = 0; for(int i = 0; i < E; i++){ edge e = es[i]; if(!same(e.u, e.v)){ unite(e.u, e.v); res += e.cost; } } return res; }
voidbacktrack(int t){ if (t > n) output(x); else for (int i = f(n,t); i <= g(n,t); i++) { x[t] = h(i); if (constraint(t) && bound(t)) backtrack(t + 1); } }
迭代回溯
1 2 3 4 5 6 7 8 9 10 11 12 13 14
voiditerativeBacktrack(){ int t = 1; while (t > 0) { if (f(n,t) <= g(n,t)) for (int i = f(n,t); i <= g(n,t); i++) { x[t] = h(i); if (constraint(t) && bound(t)) { if (solution(t)) output(x); else t++; } } else t--; } }
#define n 7 int C = 16; int w[n] = {2,2,3,4,5,5,6}; int v[n] = {3,4,3,4,5,8,7}; int x[n+1], Max = 0; voidoutput(int* x); voidmain(){ backtrack(0); } voidbacktrack(int t){ if (t >= n) process(x); else for (int i = 0; i <= 1; i++) { x[t] = i; if(legal(t)) backtrack(t + 1); } } boollegal(int t){ int sum = 0; for(int i = 0; i <= t; i++){ sum += x[i] * w[i]; } return sum <= C; } voidprocess(x){ for(int i = 0; i < n; i++){ sum += x[i] * v[i]; } if(Max < sum) Max = sum; }
装载问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
voidbacktrack(int i){ // 搜索第i层结点 if (i > n) { //到达叶结点更新最优解bestx return; } r -= w[i]; if (cw + w[i] <= c) { // 搜索左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) { // 搜索右子树 x[i] = 0; backtrack(i + 1); } r += w[i]; }
n皇后问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14
booleanplace(int k){ for (int j = 1; j < k; j++) if (abs(k - j) == abs(x[j] - x[k])) returnfalse; returntrue; } voidbacktrack(int t){ if (t > n) output(x); else for (int i = t; i <= n; i++) { swap(x[t], x[i]); if (place(t)) backtrack(t + 1); swap(x[t], x[i]); } }