（泛型冒泡排序）使用冒泡排序编写下面两个泛型方法。第一个方法使用Comparable接口对元素排序，第二个方法使用Comparator接口对元素排序。
public static <E extends Comparable<E>> void bubbleSort(E[] list) public static <E> void bubbleSort(E[] list, Comparator<? super E> comparator)
答案
import java.util.Comparator;
public class Exercise {
/** Generic bubble sort method using comparable */
public static <E extends Comparable<E>> void bubbleSort(E[] list) {
boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
// Array may be sorted and next pass not needed
needNextPass = false;
for (int i = 0; i < list.length - k; i++) {
if (list[i].compareTo(list[i + 1]) > 0) {
// Swap list[i] with list[i + 1]
E temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
needNextPass = true; // Next pass still needed
}
}
}
}
/** Generic bubble sort method using comparator */
public static <E> void bubbleSort(E[] list, Comparator<? super E> comparator) {
boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
// Array may be sorted and next pass not needed
needNextPass = false;
for (int i = 0; i < list.length - k; i++) {
if (comparator.compare(list[i], list[i + 1]) > 0) {
// Swap list[i] with list[i + 1]
E temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
needNextPass = true; // Next pass still needed
}
}
}
}
/** A test method */
public static void main(String[] args) {
// Create an Integer array
Integer[] listArray = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
// Carate a Double array
Double[] doubleArray = {3.4, 1.3, -22.1, 14.8, 6.0, 2.3, 12.2};
// Create a Character array
Character[] charArray = {'a', 'J', 'r'};
// Create a String array
String[] stringArray = {"Tom", "Susan", "Kim"};
// Sort the arrays
bubbleSort(listArray);
bubbleSort(doubleArray);
bubbleSort(charArray);
bubbleSort(stringArray);
printList(listArray);
printList(charArray);
printList(stringArray);
printList(doubleArray);
// Create an array of 10 GeometricObjects
GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5),
new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
new Circle(6.5), new Rectangle(4, 5)};
// Invoke bubble sort using GeometricObjectComparator
bubbleSort(list, new GeometricObjectComparator());
// Display the sorted elements
printList(list);
}
/** Print an array of objects */
public static void printList(Object[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
/** Print the sorted elements */
public static void printList(GeometricObject[] list) {
System.out.print("Sorted elements: ");
for (GeometricObject e: list) {
System.out.printf("%.2f ", e.getArea());
}
System.out.println();
}
}
（泛型归并排序）使用归并排序编写下面两个泛型方法。第一个方法使用Comparable接口对元素排序，第二个方法使用Comparator接口对元素排序。
public static <E extends Comparable<E>> void mergeSort(E[] list) public static <E> void mergeSort(E[] list, Comparator<? super E> comparator)
答案
import java.util.Comparator;
import java.util.Arrays;
public class Exercise {
/** Generic merge sort using Comparable */
public static <E extends Comparable<E>> void mergeSort(E[] list) {
if (list.length > 1) {
// Merge sort the first half
E[] firstHalf = (E[])new Comparable[list.length / 2];
System.arraycopy(list, 0 , firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
E[] secondHalf = (E[])(new Comparable[secondHalfLength]);
System.arraycopy(list, list.length / 2,
secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list);
}
}
/** Merge two sorted lists */
public static <E extends Comparable<E>> void merge(E[] list1, E[] list2, E[] temp) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while (current1 < list1.length && current2 < list2.length) {
if (list1[current1].compareTo(list2[current2]) < 0)
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
}
public static <E> void mergeSort(E[] list, Comparator<? super E> comparator) {
/** Generic mergeSort using Comparator */
if (list.length > 1) {
// Merge sort the first half
E[] firstHalf = Arrays.copyOf(list, list.length / 2);
mergeSort(firstHalf, comparator);
// Merge sort the second half
E[] secondHalf = Arrays.copyOfRange(list, list.length / 2, list.length);
mergeSort(secondHalf, comparator);
// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list, comparator);
}
}
/** Merge two sorted lists */
public static <E> void merge(E[] list1, E[] list2, E[] temp,
Comparator<? super E> comparator) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while (current1 < list1.length && current2 < list2.length) {
if (comparator.compare(list1[current1], list2[current2]) < 0)
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}
while (current1 < list1.length)
temp[current3++] = list1[current1++];
while (current2 < list2.length)
temp[current3++] = list2[current2++];
}
/** A test method */
public static void main(String[] args) {
Integer[] intArray = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
// Create a Double array
Double[] doubleArray = {3.4, 1.3, -22.1, 14.8, 6.0, 2.3, 12.2};
// Create a Character array
Character[] charArray = {'a', 'J', 'r'};
// Create a String array
String[] stringArray = {"Tom", "Susan", "Kim"};
// Sort the arrays
mergeSort(intArray);
mergeSort(doubleArray);
mergeSort(charArray);
mergeSort(stringArray);
// Display the arrays
printList(intArray);
printList(charArray);
printList(stringArray);
printList(doubleArray);
// Create an array of 10 GeometricObjects
GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5),
new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
new Circle(6.5), new Rectangle(4, 5)};
// Invoke merge sort using GeometricObjectComparator
mergeSort(list, new GeometricObjectComparator());
// Display the sorted elements
printList(list);
}
/** Print an array of Objects */
public static void printList(Object[] list) {
for (int i = 0; i < list.length; i ++)
System.out.print(list[i] + " ");
System.out.println();
}
/** Print the sorted elements */
public static void printList(GeometricObject[] list) {
System.out.print("Sorted elements: ");
for (GeometricObject e: list) {
System.out.printf("%.2f ", e.getArea());
}
System.out.println();
}
}
（泛型快速排序）使用快速排序编写下面两个泛型方法。第一个方法使用Comparable接口对元素排序，第二个方法使用Comparator接口对元素排序。
public static <E extends Comparable<E>> void quickSort(E[] list) public static <E> void quickSort(E[] list, Comparator<? super E> comparator)
答案
import java.util.Comparator;
public class Exercise {
/** Generic quick sort using Comparable */
public static <E extends Comparable<E>> void quickSort(E[] list) {
quickSort(list, 0, list.length - 1);
}
public static <E extends Comparable<E>>
void quickSort(E[] list, int first, int last) {
if (last > first) {
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
/** Partition the array list[first..last] */
public static <E extends Comparable<E>>
int partition(E[] list, int first, int last) {
E pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
while (high > low) {
// Search forward from left
while (low <= high && list[low].compareTo(pivot) <= 0)
low++;
// Search backward from right
while (low <= high && list[high].compareTo(pivot) > 0)
high--;
// Swap two elements in the list
if (high > low) {
E temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high].compareTo(pivot) >= 0)
high--;
// Swap pivot with list[high]
if (pivot.compareTo(list[high]) > 0) {
list[first] = list[high];
list[high] = pivot;
return high;
}
else {
return first;
}
}
public static <E> void quickSort(E[] list, Comparator<? super E> comparator) {
quickSort(list, 0, list.length - 1, comparator);
}
public static <E> void quickSort(
E[] list, int first, int last, Comparator<? super E> comparator) {
if (last > first) {
int pivotIndex = partition(list, first, last, comparator);
quickSort(list, first, pivotIndex - 1, comparator);
quickSort(list, pivotIndex + 1, last, comparator);
}
}
/** Partition the array list[first.. last] */
public static <E> int partition(
E[] list, int first, int last, Comparator<? super E> comparator) {
E pivot = list[first]; // Choose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
while (high > low) {
// Search forward from left
while (low <= high && comparator.compare(list[low], pivot) <= 0)
low++;
// Search backward from right
while (low <= high && comparator.compare(list[high], pivot) > 0)
high--;
// Swap two elements in the list
if (high > low) {
E temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && comparator.compare(list[high], pivot) >= 0)
high--;
// Swap pivot with list[high]
if (comparator.compare(pivot, list[high]) > 0) {
list[first] = list[high];
list[high] = pivot;
return high;
}
else {
return first;
}
}
/** A test method */
public static void main(String[] args) {
// Create an Integer array
Integer[] intArray = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
// Create a Double array
Double[] doubleArray = {3.4, 1.3, -22.1, 14.8, 6.0, 2.3, 12.2};
// Create a Character array
Character[] charArray = {'a', 'J', 'r'};
// Create a String array
String[] stringArray = {"Tom", "Susan", "Kim"};
// Sort the arrays
quickSort(intArray);
quickSort(doubleArray);
quickSort(charArray);
quickSort(stringArray);
// Display the sorted arrays
printList(intArray);
printList(doubleArray);
printList(charArray);
printList(stringArray);
// Create an array of 10 GeometricObjects
GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5),
new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
new Circle(6.5), new Rectangle(4, 5)};
// Invoke quick sort using GeometricObjectComparator
quickSort(list, new GeometricObjectComparator());
// Display the sorted elements
printList(list);
}
/** Print an array elements */
public static void printList(Object[] list) {
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
System.out.println();
}
/** Print an array of elements */
public static void printList(GeometricObject[] list) {
System.out.print("Sorted elements: ");
for (GeometricObject e: list) {
System.out.printf("%.2f ", e.getArea());
}
System.out.println();
}
}
（改进快速排序）本章节提供的快速排序算法选择线性表中的第一个元素作为主元。修改该算法，在线性表中的第一个元素、中间元素和最后一个元素中选择一个中位数作为主元。
答案
public class Exercise {
public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}
public static void quickSort(int[] list, int first, int last) {
if (last > first) {
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
/** Partition the aray list[first..last] */
public static int partition(int[] list, int first, int last) {
int middle = list[(list.length - 1) / 2];
// choose the median element as the pivot
int pivot = median(first, middle, last);
int low = first + 1; // Index for forward search
int high = last; // Index for backward search
while (high > low) {
// Search forward from left
while (low <= high && list[low] <= pivot)
low++;
// Search backward from right
while (low <= high && list[high] > pivot)
high--;
// Swap two elements in the list
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot)
high--;
// Swap pivot with list[high]
if (pivot > list[high]) {
list[first] = list[high];
list[high] = pivot;
return high;
}
else {
return first;
}
}
/** A test method */
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
quickSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
/** Returns the median of three integers */
public static int median(int first, int middle, int last) {
return Math.max(Math.min(first, middle),
Math.min(Math.max(first, middle), last));
}
}
（泛型堆排序）使用堆排序编写下面两个泛型方法。第一个方法使用Comparable接口对元素排序，第二个方法使用Comparator接口对元素排序。
class HeapWithComparator<E> {
private Comparator<? super E> comparator; // For comparing elements
public HeapWithComparator() {
// Implement no−arg constructor by creating a comparator for
natural order
}
public HeapWithComparator(Comparator<? super E> comparator) {
this.comparator = comparator;
}
// Implement all add, remove, and getSize method
}
答案
import java.util.Comparator;
public class Exercise {
public static <E extends Comparable<E>> void heapSort(E[] list) {
// Create a Heap
Heap<E> heap = new Heap<>();
// Add elements to the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);
// Remove elements form the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();
}
public static <E> void heapSort(E[] list, Comparator<? super E> comparator) {
// Create a Heap
HeapA<E> heap = new HeapA<>(comparator);
// Add elements to the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);
// Remove elements from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();
}
/** A test method */
public static void main(String[] args) {
/** Create an Array of Integers */
Integer[] intArray = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53};
/** Create an Array of Doubles */
Double[] doubleArray = {3.4, 1.3, -22.1, 14.8, 6.0, 2.3, 12.2};
/** Create an Array of Characters */
Character[] charArray = {'a', 'J', 'r'};
/** Create an Array of String */
String[] stringArray = {"Tom", "Susan", "Kim"};
/** Heapsort the arrays */
heapSort(intArray);
heapSort(doubleArray);
heapSort(charArray);
heapSort(stringArray);
/** Display the array */
System.out.print("Sorted Integers: ");
printList(intArray);
System.out.print("Sorted Doubles: ");
printList(doubleArray);
System.out.print("Sorted Characters: ");
printList(charArray);
System.out.print("Sorted Strings: ");
printList(stringArray);
// Create an array of 10 GeometricObjects
GeometricObject[] list = {new Circle(5), new Rectangle(4, 5),
new Circle(5.5), new Rectangle(2.4, 5), new Circle(0.5),
new Rectangle(4, 65), new Circle(4.5), new Rectangle(4.4, 1),
new Circle(6.5), new Rectangle(4, 5)};
heapSort(list, new GeometricObjectComparator());
System.out.print("Sorted elements: ");
for (GeometricObject e: list) {
System.out.printf("%.2f ", e.getArea());
}
System.out.println();
}
/** Display elements in an Array */
public static void printList(Object[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
}
（最小堆）本章节中介绍的堆也称为最大堆，其中的每个节点都大于或者等与它的任何一个子节点。最小堆是指每个节点都小于或者等与它的任何一个子节点的堆。修改之前课程中的Heap类，实现最小堆。
答案
public class Exercise {
/** Heap sort method */
public static <E extends Comparable<E>> void heapSort(E[] list) {
// Create a Heap of integers
Heap<E> heap = new Heap<>();
// Add elements to the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);
// Remove elements from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();
}
/** A test method */
public static void main(String[] args) {
Integer[] list = {-44, -5, -3, 3, 3, 1, -4, 0, 1, 2, 4, 5, 53};
heapSort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println();
}
}