(泛型冒泡排序)使用冒泡排序编写下面两个泛型方法。第一个方法使用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(); } }