sortablearraylist.java

来自「java版的数据结构的完全代码 免费提供了 学习数据结构的请下载」· Java 代码 · 共 38 行

// Introduced in Chapter 8
/** An array-based List of Comparables. */
public class SortableArrayList<E extends Comparable<E>>
  extends ArrayList<E> {

  public boolean contains(E target) {
    insertionSort();
    int bottom = 0;
    int top = size() - 1;
    while (bottom <= top) {
      int midpoint = (top + bottom) / 2;
      int comparison = target.compareTo(get(midpoint));
      if (comparison < 0) {
        top = midpoint - 1;
      } else if (comparison == 0) {
        return true;
      } else {
        bottom = midpoint + 1;
      }
    }
    return false;
  }

  /** Arrange the elements in this List from smallest to largest. */
  public void insertionSort() {
    for (int i = 1; i < size(); i++) {
      E target = get(i);
      int j;
      for (j = i - 1; (j >= 0) && (get(j).compareTo(target) > 0);
	       j--) {
        set(j + 1, get(j));
      }
      set(j + 1, target);
    }
  }

}