intpartition(Type a[], int p, int r){ int i = p, j = r+1 Type x = a[p] //第一个元素为基准 while (true) { while (a[++i] < x && i < r) //左标兵向右 while (a[--j] > x) //右标兵向左 if (i >= j) break swap(a[i], a[j]) //交换位置 } a[p] = a[j] //第一个元素和最小数交换位置 a[j] = x return j //返回基准位置 }
int randomizedPartition (Type a[], int p, int r) { int i = random(p, r) swap(a[i], a[p]) //将随机元素作为基准(第一个元素) return partition(a, p, r) }
Type randomizedSelect(Type a[], int p, int r, int k) { //第k小个元素 if (p == r) //只有一个元素 return a[p] int i = randomizedPartition(a, p ,r) //i为随机基准位置 j = i-p+1//计算数组a[p:i]个数(左边) if (k <= j) return randomizedSelect(a, p, i, k) //落在左边 else return randomizedSelect(a, i+1, r, k-j) //落在右边 }
var n = 4 var x = [] functionplace(t) { //判断第t个皇后能否放在第i个位置 var flag = true for (var j = 0; j < t; j++) { if (x[t] === x[j] || t - j === Math.abs(x[t] - x[j])) { //判断与竖、撇捺是否有冲突 flag = false break } } return flag } functionbacktrack(t) { if (t === n) { //当前位置到了叶节点输出一个解 console.log(x) } else { for (var i = 0; i < n; i++) { x[t] = i if (place(t)) { queen(t + 1) //不冲突进行下一行搜索 } } } } backtrack(0)
贪心算法
最小生成树
O(n^2)
MST性质(最小生成树定义):假设G=(V, E)是一个连通网,U 是顶点集V的真子集。若(u, v )是一条具有最小权值的边,其中u∈U, v∈V-U,则必存在一棵包含边(u, v)的最小生成树。
voidprim(int n, Type **c){ Type lowcost[maxint] int closet[maxint] bool s[maxint] s[1] = true for (int i = 2; i <= n; i++) { lowcost[i] = c[1][i] closet[i] = 1 s[i] = false } for (int i = 1; i < n; i++) { Type min = INF int j = 1 for (int k = 2; k <= n; k++) { if ((lowcost[k] < min) && (!s[k])) { min = lowcost[k] j = k } } s[j] = true for (int k = 2; k <= n; k++) { if ((c[j][k] < lowcost(k)) && (!s[k])) { lowcost[k] = c[j][k] closet[k] = j } } } }