（九）排序（选择、插入、希尔）

/**
 * Class for sorting an array of Comparable objects from smallest to largest.
 * @author Administrator
 *
 */
public class SortArray {
　　/**
　　 * Sorts the first n objects in an array into ascending order.
　　 * @param a: An array of Comparable objects.
　　 * @param n: An integer > 0.
　　 */
　　public static extends Comparable super T>> void selectionSort(T[] a, int n) {
　　　　for (int index = 0; index ) {
　　　　　　int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
　　　　　　swap(a, index, indexOfNextSmallest);
　　　　　　// Assertion: a[0] 
　　　　} // end for
　　} // end selectionSort

　　// Finds the index of the smallest value in a portion of an array a.
　　// Precondition: a length > last >= first >= 0.
　　// Returns the index of the smallest value among
　　// a[first], a[first+1],...,a[last].
　　private static extends Comparable super T>> int getIndexOfSmallest(T[] a, int first, int last) {
　　　　T min = a[first];
　　　　int indexOfMin = first;
　　　　for (int index = first+1; index ) {
　　　　　　if (a[index].compareTo(min) ) {
　　　　　　　　min = a[index];
　　　　　　　　indexOfMin = index;
　　　　　　} // end if
　　　　　　// Assertion: min is the smallest of a[first] through a[index]
　　　　} // end for
　　　　return indexOfMin;
　　} // end getIndexOfSmallest

　　// Swaps the array entries a[i] and a[j]
　　private static void swap(Object[] a, int i, int j) {
　　　　Object temp = a[i];
　　　　a[i] = a[j];
　　　　a[j] = temp;
　　} // end swap
} // end SortArray

public static extends Comparable super T>> void insertionSort(T[] a, int first, int last) {
　　if (first  last) {
　　　　// Sort all but the last entry
　　　　insertionSort(a, first, last - 1);
　　　　// Insert the last entry in sorted order
　　　　insertInOrder(a[last], a, first, last - 1);
　　} // end if
} // end insertionSort

Algorithm insertInOrder(anEntry, a, begin, end)
// 将anEntry插入到有序数组项a[begin]到a[end]中
if (anEntry >= a[end])
   a[end + 1] = anEntry
else if (begin  end){
   a[end + 1] = a[end];
   insertInOrder(anEntry, a, begin, end - 1);
}
else{  // begin==end and anEntry 
   a[end + 1] = a[end];
   a[end] = anEntry;
}

public class LinkedGroupextends Comparable super T>> {
　　private Node firstNode;
　　int length; // Number of objects in the group
　　...
}

private void insertInOrder(Node nodeToInsert) {
　　T item = nodeToInsert.getData();
　　Node currentNode = firstNode;
　　Node previousNode = null;
　　// Locate insertion point
　　while ((currentNode != null) && (item.compareTo(currentNode.getData()) > 0)) {
　　　　previousNode = currentNode;
　　　　currentNode = currentNode.getNextNode();
　　} // end while
　　// Make the insertion
　　if (previoueNode != null) {
　　　　// Insert between previousNode and currentNode
　　　　previousNode.setNextNode(nodeToInsert);
　　　　nodeToInsert.setNextNode(currentNode);
　　}
　　else {
　　　　// Insert at beginning
　　　　nodeToInsert.setNextNode(firstNode);
　　　　firstNode = nodeToInsert;
　　} // end if
} // end insertInOrder

public void insertionSort() {
　　// If zero or one item is in the chain, there is nothing to do
　　if (length > 1) {
　　　　assert firstNode != null;
　　　　// Break chain into 2 pieces: sorted and unsorted
　　　　Node unsortedPart = firstNode.getNextNode();
　　　　assert unsortedPart != null;
　　　　firstNode.setNextNode(null);
　　　　while (unsortedPart != null) {
　　　　　　Node nodeToInsert = unsortedPart;
　　　　　　unsortedPart = unsortedPart.getNextNode();
　　　　　　insertInOrder(nodeToInsert);
　　　　} // end while
　　} // end if
} // end insertionSort

Algorithm incrementalInsertionSort(a, first, last, space)
// 将a[first…last]中等间距的数组项进行升序排序。
// first >= 0 and = first and // 在要排序的项的下标间，space是不同的。
for (unsorted = first + space 到 last以space为增量){
   nextToInsert = a[unsorted]
   index = unsorted – space
   while ((index >= first) and (nextToInsert.compareTo(a[index]) )){
      a[index + space] = a[index]
      index = index - space
　　}
　　a[index+space] = nextToInsert
}

Algorithm shellSort(a, first, last)
// 将数组a[first…last]中的项进行升序排序。
// first >= 0 and = first and 
n = 数组的项数
space = n/2
while(space > 0){
   for(begin = first through first + space - 1){
     incrementalInsertionSort(a, begin, last, space)
　　}
　　space = space / 2
}