1.编写程序，分别使用Comparable和Comparator接口对元素冒泡排序。

import java.util.Comparator;public class MySort {public static <E extends Comparable<E>> void bubbleSort(E[] list) {boolean needNextPass = true;for (int i = 1; needNextPass && i < list.length; i++) {needNextPass = false;for (int j = 0; j < list.length - i; j++)if (list[j].compareTo(list[j + 1]) > 0) {E t = list[j];list[j] = list[j + 1];list[j + 1] = t;needNextPass = true;}}}public static <E> void bubbleSort(E[] list, Comparator<? super E> comparator) {boolean needNextPass = true;for (int i = 1; needNextPass && i < list.length; i++) {needNextPass = false;for (int j = 0; j < list.length - i; j++)if (comparator.compare(list[j], list[j + 1]) > 0) {E t = list[j];list[j] = list[j + 1];list[j + 1] = t;needNextPass = true;}}}
}

2.编写程序，分别使用Comparable和Comparator接口对元素归并排序。

import java.util.Comparator;public class MySort {public static <E extends Comparable<E>> void mergeSort(E[] list) {new MergeSort<>(list, new Comparator<E>() {@Overridepublic int compare(E o1, E o2) {return o1.compareTo(o2);}}).sort();}public static <E> void mergeSort(E[] list, Comparator<? super E> comparator) {new MergeSort<>(list, comparator).sort();}
}class MergeSort<E> {private E[] list;private E[] tmp;private Comparator<? super E> comparator;public MergeSort(E[] list, Comparator<? super E> comparator) {this.list = list;tmp = (E[]) new Object[list.length];this.comparator = comparator;}// 排序范围 [start, end)private void sort(int start, int end) {if (end < start + 2) return;int m = (start + end) >> 1;sort(start, m);sort(m, end);int i = start, j = m, r = 0;while (i < m && j < end)if (comparator.compare(list[i], list[j]) < 0)tmp[r++] = list[i++];elsetmp[r++] = list[j++];while (i < m) tmp[r++] = list[i++];while (j < end) tmp[r++] = list[j++];System.arraycopy(tmp, 0, list, start, r);}public void sort() {sort(0, list.length);}
}

3.编写程序，分别使用Comparable和Comparator接口对元素快速排序。

import java.util.Comparator;public class MySort {public static <E extends Comparable<E>> void quickSort(E[] list) {new QuickSort<>(list, new Comparator<E>() {@Overridepublic int compare(E o1, E o2) {return o1.compareTo(o2);}}).sort(0, list.length);}public static <E> void quickSort(E[] list, Comparator<? super E> comparator) {new QuickSort<>(list, comparator).sort(0, list.length);}
}class QuickSort<E> {private E[] list;private Comparator<? super E> comparator;public QuickSort(E[] list, Comparator<? super E> comparator) {this.list = list;this.comparator = comparator;}// 排序范围 [start, end)public void sort(int start, int end) {if (end < start + 2) return;if (end == start + 2) {if (comparator.compare(list[start], list[start + 1]) > 0) {E e = list[start];list[start] = list[start + 1];list[start + 1] = e;}return;}E e = list[start];int l = start + 1, r = end - 1;for (; ; ) {while (l <= r && comparator.compare(list[l], e) <= 0) ++l;while (l <= r && comparator.compare(list[r], e) > 0) --r;if (r > l) {E t = list[r];list[r] = list[l];list[l] = t;} elsebreak;}while (r > start && comparator.compare(list[r], e) >= 0) --r;if (comparator.compare(e, list[r]) > 0) {list[start] = list[r];list[r] = e;sort(start, r);sort(r + 1, end);} elsesort(start + 1, end);}
}

6.编写下面的重载方法，用于检查数组是按升序还是降序排序的。默认情况下，该方法是检查升序的。为检查降序，则将false传递给方法中的ascending参数。

import java.util.Comparator;public class OrderChecker {public static boolean ordered(int[] list) {int n = list.length - 1;for (int i = 0; i < n; i++)if (list[i] > list[i + 1])return false;return true;}public static boolean ordered(int[] list, boolean ascending) {int n = list.length - 1;if (ascending) {for (int i = 0; i < n; i++)if (list[i] > list[i + 1])return false;} elsefor (int i = 0; i < n; i++)if (list[i] < list[i + 1])return false;return true;}public static boolean ordered(double[] list) {int n = list.length - 1;for (int i = 0; i < n; i++)if (list[i] > list[i + 1])return false;return true;}public static boolean ordered(double[] list, boolean ascending) {int n = list.length - 1;if (ascending) {for (int i = 0; i < n; i++)if (list[i] > list[i + 1])return false;} elsefor (int i = 0; i < n; i++)if (list[i] < list[i + 1])return false;return true;}public static <E extends Comparable<E>> boolean ordered(E[] list) {int n = list.length - 1;for (int i = 0; i < n; i++)if (list[i].compareTo(list[i + 1]) > 0)return false;return true;}public static <E extends Comparable<E>> boolean ordered(E[] list, boolean ascending) {int n = list.length - 1;if (ascending) {for (int i = 0; i < n; i++)if (list[i].compareTo(list[i + 1]) > 0)return false;} elsefor (int i = 0; i < n; i++)if (list[i].compareTo(list[i + 1]) < 0)return false;return true;}public static <E> boolean ordered(E[] list, Comparator<? super E> comparator) {int n = list.length - 1;for (int i = 0; i < n; i++)if (comparator.compare(list[i], list[i + 1]) > 0)return false;return true;}public static <E> boolean ordered(E[] list, Comparator<? super E> comparator, boolean ascending) {int n = list.length - 1;if (ascending) {for (int i = 0; i < n; i++)if (comparator.compare(list[i], list[i + 1]) > 0)return false;} elsefor (int i = 0; i < n; i++)if (comparator.compare(list[i], list[i + 1]) < 0)return false;return true;}
}

7.修改程序清单23-9中的Heap类以实现最小堆(每个节点都小于等于它的任何一个子节点)。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class Heap<E> {private ArrayList<E> list;private Comparator<? super E> comparator;public Heap(Comparator<? super E> comparator) {this.comparator = comparator;list = new ArrayList<>();}public Heap() {comparator = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);list = new ArrayList<>();}public Heap(E[] objects) {comparator = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);list = new ArrayList<>(List.of(objects));}public void add(E newObject) {int currentIndex = list.size();list.add(newObject);while (currentIndex > 0) {int parentIndex = (currentIndex - 1) >> 1;if (comparator.compare(list.get(currentIndex), list.get(parentIndex)) < 0) {E t = list.get(currentIndex);list.set(currentIndex, list.get(parentIndex));list.set(parentIndex, t);} elsebreak;currentIndex = parentIndex;}}public E remove() {if (list.isEmpty()) return null;E removedObject = list.getFirst();list.set(0, list.getLast()); // 这里不能写成list.set(0, list.removeLast());list.removeLast();int currentIndex = 0, n = list.size();while (currentIndex < n) {int leftChildIndex = (currentIndex << 1) + 1, rightChildIndex = leftChildIndex + 1;if (leftChildIndex >= n) break;int minIndex = leftChildIndex;if (rightChildIndex < n && comparator.compare(list.get(minIndex), list.get(rightChildIndex)) > 0)minIndex = rightChildIndex;if (comparator.compare(list.get(currentIndex), list.get(minIndex)) > 0) {E t = list.get(minIndex);list.set(minIndex, list.get(currentIndex));list.set(currentIndex, t);currentIndex = minIndex;} elsebreak;}return removedObject;}public int size() {return list.size();}public boolean isEmpty() {return list.isEmpty();}
}

8.编写程序，分别使用Comparable和Comparator接口对元素插入排序。

import java.util.Comparator;public class MySort {public static <E extends Comparable<E>> void insertionSort(E[] list) {for (int i = 1; i < list.length; i++) {E currentElement = list[i];int k = i;while (--k >= 0 && list[k].compareTo(currentElement) > 0) list[k + 1] = list[k];list[k + 1] = currentElement;}}public static <E> void insertionSort(E[] list, Comparator<E> comparator) {for (int i = 1; i < list.length; i++) {E currentElement = list[i];int k = i;while (--k >= 0 && comparator.compare(list[k], currentElement) > 0) list[k + 1] = list[k];list[k + 1] = currentElement;}}
}

9.编写程序，分别使用Comparable和Comparator接口对元素堆排序。

import java.util.Comparator;// 这里的Heap类是第7题中的
public class MySort {public static <E extends Comparable<E>> void heapSort(E[] list) {Heap<E> heap = new Heap<>();for (E e : list) heap.add(e);for (int i = 0; i < list.length; i++) list[i] = heap.remove();}public static <E> void heapSort(E[] list, Comparator<E> comparator) {Heap<E> heap = new Heap<>(comparator);for (E e : list) heap.add(e);for (int i = 0; i < list.length; i++) list[i] = heap.remove();}
}