BST BST 的特性就是左子树都比本节点小，右子树都比本节点大。 private class Node { private Key key; private Value val; private Node left, right; public Node(Key key, Value val) { this.key = key; this.val = val; } } public class BST<Key extends Comparable<Key>, Value> { private Node root; public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val); int cmp = key....
Selection sort In iteration i, find index min of smallest remaining entry. Swap a[i] and a[min] i 从0开始，找到数组中最小的，与i交换，i++，直到 i 等于数组长度。 Comparable[] a; int N = a.length; for(int i = 0; i < N; i++) { int min = i; for(int j = i + 1; j < N; j++) { if(less(a[j], a[min])) min = j; } exch(a, i, min); } Both best case and worst case: $$ \theta(n^2) $$ not stable...
在比较算法中，快速排序可以算是明星算法了，因为他的常系数小，使得其总体性能比其他比较算法优秀。其性能基本上可以达到$\theta (n\lg n)$ ，但在某些极端情况其时间复杂度却是$\theta ({n}^{2})$。 快速排序的基本思想是遵循分而治之的思想的，其基本思路是： 分：在待排序的数据中选取一个数作为中心点，大于这个数的数统统放到右边，小于这个数的统统放在左边。这样就形成了左右两个子串。 治：两个子串重复1的动作 合并：无 ##分 所以最重要的是分这一步，这一步的伪代码如下 :::c Partition(A,p,q) // A[p,q] x<-A[p] i<-p for j<-p+1 to q do if A[j] <= x // <= 是小于等于的意思 then i<-i+1 exhange A[i]<->A[j] exchange A[p]<->A[i] return i 时间复杂度为$\theta(n)$ 下面给出一个例子，看如何分。 Ex. :::java 6 10 13 5 8 3 2 11 选取 pivot＝6 i=0 j=1 :::java 6 10 13 5 8 3 2 11 pivot=6 i=0 j=3 i=i+1 -> i=1 exchange A[i]<->A[j] so: :::java 6 5 13 10 8 3 2 11 此时 i=1,j=3, 继续 :::java 6 5 13 10 8 3 2 11 i=1,j=5 i=2 exchange A[i]<->A[j] :::java 6 5 3 10 8 13 2 11 i=2,j=5 j继续自增 :::java 6 5 3 10 8 13 2 11 i=2,j=6 i=3 exchange A[i]<->A[j] :::java 6 5 3 2 8 13 10 11 i=3,j=6 直到结束，然后 exchange A[p]<->A[i] : A[0] <-> A[3] , 最后结果为 :::java 2 5 3 6 8 13 10 11 这样以6为轴，比6小的都在左边，比6大的都在右边，分结束。...