public static int f(int x){
	// 处理基准情况
	if(X == 0){
		return 0;
	}
	else{
		// 递归调用
		return 2 * f(x - 1) + x * x;
	}
}

Person[] arr = new Employee[5]; //编译： arrays are compatible
arr[O] =new Student(...); //编译： Student IS-A Person

public void findMax(Comparable[] arr){...};
public static void main(String [] args) {
	Shape [] shl = { new Circle(2.0),
					 new Square(3.0),
					 new Rectangle(3.0, 4.0) } ;
	String [] stl = { "Joe", "Bob", "Bill", "Zeke" } ;
	System.out.println(findMax(shl));
	System.out.println(findMax(stl));
}

Collection<? extends Shape> arr)

T obj = new T(); // 右边是非法的

T[] arr = new T[10]; // 右边是非法的

// Type safety: The expression of type MyClass[] needs unchecked conversion to conform to MyClass<T>[]
MyClass<T>[] array = new MyClass<T>[]; 

/**
 * Linear-time maximum contiguous subsequence sum algorithm.
 * seqStart and seqEnd represent the actual best sequence.
 */
public static int maxSubSum4(int[] a) {
	int maxSum = 0;
	int thisSum = 0;
	for (int j = 0, j = 0; j < a.length; j++) {
		thisSum += a[j];
		if (thisSum > maxSum) {
			maxSum = thisSum;
		} else if (thisSum < 0) {
			thisSum = 0;
		}
	}
	return maxSum;
}

public static void removeEvensVer1(List<Integer> lst) {
	int i = 0;
	while (i < lst.size()) {
		// 对于LinkedList，get调用效率不高
		if (lst.get(i) % 2 == 0) {
			// remove效率同样低
			lst.remove(i);
		} else {
			i++;
		}
	}
}

public static void removeEvensVer2(List<Integer> lst) {
	for (Integer x : lst) {
		if (x % 2 == 0) {
			// remove不高效，而且会报错
			lst.remove(x);
		}
	}
}

public static void removeEvensVer3(List<Integer> lst) {
	Iterator<Integer> itr = lst.iterator();
	while (itr.hasNext()) {
		if (itr.next() % 2 == 0) {
			// 常数时间
			itr.remove();
		}
	}
}

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
	void remove();
	// set方法解决LinkedList对值的变更问题
    void set(E e);
    void add(E e);
}

/**
 * Insert into the priority queue, maintaining heap order.
 * Duplicates are allowed.
 *
 * @param x the item to insert.
 */
public void insert(AnyType x) {
	if (currentSize == array.length - 1) {
		enlargeArray(array.length * 2 + 1);
	}
	// Percolate up
	int hole = ++currentSize;
	for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
		array[hole] = array[hole / 2];
	}
	array[hole] = x;
}

/**
 * Remove the smallest item from the priority queue.
 *
 * @return the smallest item, or throw an com.songxp.algorithm.UnderflowException if empty.
 */
public AnyType deleteMin() {
	if (isEmpty()){
		throw new UnderflowException();
	}
	AnyType minItem = findMin();
	array[1] = array[currentSize--];
	percolateDown(1);
	return minItem;
}

/**
 * Internal method to percolate down in the heap.
 *
 * @param hole the index at which the percolate begins.
 */
private void percolateDown(int hole) {
	int child;
	AnyType tmp = array[hole];
	for (; hole * 2 <= currentSize; hole = child) {
		child = hole * 2;
		if (child != currentSize &&
				array[child + 1].compareTo(array[child]) < 0) {
			child++;
		}
		if (array[child].compareTo(tmp) < 0) {
			array[hole] = array[child];
		} else {
			break;
		}
	}
	array[hole] = tmp;
}

/**
 * Construct the binary heap given an array of items.
 */
public BinaryHeap(AnyType[] items) {
	currentSize = items.length;
	array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
	int i = 1;
	for (AnyType item : items) {
		array[i++] = item;
	}
	buildHeap();
}
/**
 * Establish heap order property from an arbitrary
 * arrangement of items. Runs in linear time.
 */
private void buildHeap() {
	for (int i = currentSize / 2; i > 0; i--) {
		percolateDown(i);
	}
}

public static <AnyType extends Comparable<? super AnyType>>
void insertionSort(AnyType[] a) {
	int j;
	for (int p = 1; p < a.length; p++) {
		AnyType tmp = a[p];
		for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
			a[j] = a[j - 1];
		}
		a[j] = tmp;
	}
}

/**
 * Shellsort, using Shell's (poor) increments.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void shellsort(AnyType[] a) {
	int j;

	for (int gap = a.length / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < a.length; i++) {
			AnyType tmp = a[i];
			for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
				a[j] = a[j - gap];
			}
			a[j] = tmp;
		}
	}
}

/**
 * Internal method for heapsort.
 *
 * @param i the index of an item in the heap.
 * @return the index of the left child.
 */
private static int leftChild(int i) {
	return 2 * i + 1;
}

/**
 * Internal method for heapsort that is used in deleteMax and buildHeap.
 *
 * @param a an array of Comparable items.
 * @index i the position from which to percolate down.
 * @int n the logical size of the binary heap.
 */
private static <AnyType extends Comparable<? super AnyType>>
void percDown(AnyType[] a, int i, int n) {
	int child;
	AnyType tmp;

	for (tmp = a[i]; leftChild(i) < n; i = child) {
		child = leftChild(i);
		if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
			child++;
		}
		if (tmp.compareTo(a[child]) < 0) {
			a[i] = a[child];
		} else {
			break;
		}
	}
	a[i] = tmp;
}

/**
 * Standard heapsort.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void heapsort(AnyType[] a) {
	for (int i = a.length / 2 - 1; i >= 0; i--)  /* buildHeap */ {
		percDown(a, i, a.length);
	}
	for (int i = a.length - 1; i > 0; i--) {
		swapReferences(a, 0, i);                /* deleteMax */
		percDown(a, 0, i);
	}
}

/**
 * Method to swap to elements in an array.
 *
 * @param a      an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2) {
	AnyType tmp = a[index1];
	a[index1] = a[index2];
	a[index2] = tmp;
}

/**
 * Mergesort algorithm.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a) {
	AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];

	mergeSort(a, tmpArray, 0, a.length - 1);
}

/**
 * Internal method that makes recursive calls.
 *
 * @param a        an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param left     the left-most index of the subarray.
 * @param right    the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void mergeSort(AnyType[] a, AnyType[] tmpArray,
				int left, int right) {
	if (left < right) {
		int center = (left + right) / 2;
		mergeSort(a, tmpArray, left, center);
		mergeSort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, center + 1, right);
	}
}
/**
 * Internal method that merges two sorted halves of a subarray.
 *
 * @param a        an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param leftPos  the left-most index of the subarray.
 * @param rightPos the index of the start of the second half.
 * @param rightEnd the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd) {
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	// Main loop
	while (leftPos <= leftEnd && rightPos <= rightEnd) {
		if (a[leftPos].compareTo(a[rightPos]) <= 0) {
			tmpArray[tmpPos++] = a[leftPos++];
		} else {
			tmpArray[tmpPos++] = a[rightPos++];
		}
	}

	while (leftPos <= leftEnd)    // Copy rest of first half
	{
		tmpArray[tmpPos++] = a[leftPos++];
	}

	while (rightPos <= rightEnd)  // Copy rest of right half
	{
		tmpArray[tmpPos++] = a[rightPos++];
	}

	// Copy tmpArray back
	for (int i = 0; i < numElements; i++, rightEnd--) {
		a[rightEnd] = tmpArray[rightEnd];
	}
}

public static void sort(List<Integer> items) {
	if (items.size() > 1) {
		List<Integer> smaller = new ArrayList<>();
		List<Integer> same = new ArrayList<>();
		List<Integer> larger = new ArrayList<>();

		Integer chosenItem = items.get(items.size() / 2);
		for (Integer i : items) {
			if (i < chosenItem) {
				smaller.add(i);
			} else if (i > chosenItem) {
				larger.add(i);
			} else {
				same.add(i);
			}
		}
		sort(smaller); // Recursive call!
		sort(larger); // Recursive call!

		items.clear();
		items.addAll(smaller);
		items.addAll(same);
		items.addAll(larger);

	}
}

/**
 * Quicksort algorithm.
 *
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a) {
	quicksort(a, 0, a.length - 1);
}
/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 *
 * @param a     an array of Comparable items.
 * @param left  the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 */
private static <AnyType extends Comparable<? super AnyType>>
void quicksort(AnyType[] a, int left, int right) {
	if (left + CUTOFF <= right) {
		// 获取中值，并做顺序交换，变更起始位置，防止极端数据产生坏的结果
		AnyType pivot = median3(a, left, right);

		// Begin partitioning
		int i = left, j = right - 1;
		for (; ; ) {
			while (a[++i].compareTo(pivot) < 0) {
			}
			while (a[--j].compareTo(pivot) > 0) {
			}
			if (i < j) {
				swapReferences(a, i, j);
			} else {
				break;
			}
		}

		swapReferences(a, i, right - 1);   // Restore pivot

		quicksort(a, left, i - 1);    // com.songxp.algorithm.Sort small elements
		quicksort(a, i + 1, right);   // com.songxp.algorithm.Sort large elements
	} else  // Do an insertion sort on the subarray
	{
		insertionSort(a, left, right);
	}
}
/**
 * Method to swap to elements in an array.
 *
 * @param a      an array of objects.
 * @param index1 the index of the first object.
 * @param index2 the index of the second object.
 */
public static <AnyType> void swapReferences(AnyType[] a, int index1, int index2) {
	AnyType tmp = a[index1];
	a[index1] = a[index2];
	a[index2] = tmp;
}

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
private static <AnyType extends Comparable<? super AnyType>>
AnyType median3(AnyType[] a, int left, int right) {
	int center = (left + right) / 2;
	if (a[center].compareTo(a[left]) < 0) {
		swapReferences(a, left, center);
	}
	if (a[right].compareTo(a[left]) < 0) {
		swapReferences(a, left, right);
	}
	if (a[right].compareTo(a[center]) < 0) {
		swapReferences(a, center, right);
	}
	// Place pivot at position right - 1
	swapReferences(a, center, right - 1);
	return a[right - 1];
}

/**
 * Quick selection algorithm.
 * Places the kth smallest item in a[k-1].
 *
 * @param a an array of Comparable items.
 * @param k the desired rank (1 is minimum) in the entire array.
 */
public static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int k) {
	quickSelect(a, 0, a.length - 1, k);
}

/**
 * Internal selection method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * Places the kth smallest item in a[k-1].
 *
 * @param a     an array of Comparable items.
 * @param left  the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 * @param k     the desired index (1 is minimum) in the entire array.
 */
private static <AnyType extends Comparable<? super AnyType>>
void quickSelect(AnyType[] a, int left, int right, int k) {
	if (left + CUTOFF <= right) {
		AnyType pivot = median3(a, left, right);

		// Begin partitioning
		int i = left, j = right - 1;
		for (; ; ) {
			while (a[++i].compareTo(pivot) < 0) {
			}
			while (a[--j].compareTo(pivot) > 0) {
			}
			if (i < j) {
				swapReferences(a, i, j);
			} else {
				break;
			}
		}

		swapReferences(a, i, right - 1);   // Restore pivot

		if (k <= i) {
			quickSelect(a, left, i - 1, k);
		} else if (k > i + 1) {
			quickSelect(a, i + 1, right, k);
		}
	} else  // Do an insertion sort on the subarray
	{
		insertionSort(a, left, right);
	}
}

/*
 * Radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have same length
 */
public static void radixSortA(String[] arr, int stringLen) {
	final int BUCKETS = 256;
	ArrayList<String>[] buckets = new ArrayList[BUCKETS];
	for (int i = 0; i < BUCKETS; i++) {
		buckets[i] = new ArrayList<>();
	}
	for (int pos = stringLen - 1; pos >= 0; pos--) {
		for (String s : arr) {
			buckets[s.charAt(pos)].add(s);
		}
		int idx = 0;
		for (ArrayList<String> thisBucket : buckets) {
			for (String s : thisBucket) {
				arr[idx++] = s;
			}
			thisBucket.clear();
		}
	}
}

/*
 * Counting radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have same length
 */
public static void countingRadixSort(String[] arr, int stringLen) {
	final int BUCKETS = 256;
	int N = arr.length;
	String[] buffer = new String[N];
	String[] in = arr;
	String[] out = buffer;
	for (int pos = stringLen - 1; pos >= 0; pos--) {
		int[] count = new int[BUCKETS + 1];
		for (int i = 0; i < N; i++) {
			count[in[i].charAt(pos) + 1]++;
		}
		for (int b = 1; b <= BUCKETS; b++) {
			count[b] += count[b - 1];
		}
		for (int i = 0; i < N; i++) {
			out[count[in[i].charAt(pos)]++] = in[i];
		}
		// swap in and out roles
		String[] tmp = in;
		in = out;
		out = tmp;
	}
	// if odd number of passes, in is buffer, out is arr; so copy back
	if (stringLen % 2 == 1) {
		System.arraycopy(in, 0, out, 0, arr.length);
	}
}

/*
 * Radix sort an array of Strings
 * Assume all are all ASCII
 * Assume all have length bounded by maxLen
 */
public static void radixSort(String[] arr, int maxLen) {
	final int BUCKETS = 256;

	ArrayList<String>[] wordsByLength = new ArrayList[maxLen + 1];
	ArrayList<String>[] buckets = new ArrayList[BUCKETS];

	for (int i = 0; i < wordsByLength.length; i++) {
		wordsByLength[i] = new ArrayList<>();
	}

	for (int i = 0; i < BUCKETS; i++) {
		buckets[i] = new ArrayList<>();
	}
	// 长度进行桶排序
	for (String s : arr) {
		wordsByLength[s.length()].add(s);
	}
	// 放回数组
	int idx = 0;
	for (ArrayList<String> wordList : wordsByLength) {
		for (String s : wordList) {
			arr[idx++] = s;
		}
	}

	int startingIndex = arr.length;
	for (int pos = maxLen - 1; pos >= 0; pos--) {
		startingIndex -= wordsByLength[pos + 1].size();
		// 处理pos有字符的情况
		for (int i = startingIndex; i < arr.length; i++) {
			buckets[arr[i].charAt(pos)].add(arr[i]);
		}

		idx = startingIndex;
		for (ArrayList<String> thisBucket : buckets) {
			for (String s : thisBucket) {
				arr[idx++] = s;
			}

			thisBucket.clear();
		}
	}
}