Technorati 标记: java,排序算法,通配符
这几天无聊，又重新学起java的排序算法，为DualPivotQuickSort做准备。为了更好地适应各种情况，我们选择使用通用类型T和通配符的上下界来实现，同时这次谈的是对数组对象的排序。如果你对java 通配符的了解不深的，可以点击 这里 。
现在假设有如下排序方法：
public static <T> void sort(T[] a, int n)
因为对象之间可以比较大小，数组对象必须是实现Comparable接口的。因此T所表示的类必须实现接口Comparable。为此需要为T添加一个上界，如下：
public static <T extends Comparable<T>> void sort(T[] a, int n)
如此,便指定了传递给Sort的对象数组必须是可比较的.为了sort()方法可以更加贴近实际的需要,现在再做一点改进.
现在使用sort()方法对10个Integer对象排序如下:
sort(intArray,10);
代码”T extends Comparable<T>“要求Integer必须实现Comparable<Integer>,并且数组内的对象都必须是Integer对象。详细的使用细则，可参考 java 通配符解惑。 T的对象不仅可以与T的其他对象相互比较，也应该可以与T的超类对象相比较。因此，取代”T extends Comparable<T>“的另一种写法是：
public static <T extends Comparable<？ super T>> void sort(T[] a, int n)
“？”代表任意类型，而“？ super T”则意味着T的任意超类。写成Comparable<? super T>，就可以对任意类型使用Comparable。 一、选择排序：
选择排序是最基本的排序算法 ，一般不怎么用，可却是学排序最基本的算法，了解一下总无害。
迭代伪代码：
for i = 0:n-1,k = ifor j = i+1:n-1, if a[j] < a[k], k = j//a[k] 总是a[i..n]最小的那一个swap a[i,k]//排序的最后结果：a[1..i]end
性能：
最坏的情况：О(n2)
最好的情况：О(n2)
平均状况：О(n2)
不稳定
额外需要的空间：O(n)
java 实现:
public static <T extends Comparable<? super T>> void selectionSort(T[] a){int smallestIndex;for(int i = 0;i < a.length; i++){smallestIndex = i;for (int j = i+1; j < a.length; j++) {if (a[j].compareTo(a[smallestIndex]) < 0) {smallestIndex = j;}}swap(a, i, smallestIndex);}}swap(Object[] a, int i, int j) {Object temp = a[i];a[i] = a[j];a[j] = temp;}
二、插入排序
插入排序在最坏情况下的效率是O(n2)。在大部分元素已排好序或者排序的元素数量少的情况下，一般选择使用插入排序(因为它是低开销)。
伪代码：
for i = 1:n,for (k = i; k > 0 and a[k] < a[k-1]; k–)swap a[k,k-1]end
性能（效率）：
最坏的情况：О(n2)比较，О(n2)交换
最好的情况：O(n) 比较, O(1) 交换
平均状况：О(n2)比较，О(n2)交换
稳定
额外需要的空间：O(n)
java 实现：
public static <T extends Comparable<? super T>> void insertionSort(T[] a) {int len = a.length;for (int i = 1; i < len; i++) {for (int k = i; (k > 0) && (a[k].compareTo(a[k – 1]) < 0); k–) {swap(a, k, k – 1);}}}
三、冒泡排序
冒泡排序与插入排序有很多相似的地方，只不过是冒泡排序的开销稍高。
伪代码：
for i = 0:n-1,swapped = falsefor j = n-1:i+1,if a[j] < a[j-1],swap a[j,j-1]swapped = not swappedend
性能：
最坏的情况：О(n2)
最好的情况：
平均状况：О(n2)
稳定
额外需要的空间：O(n)
java实现：
public static <T extends Comparable<? super T>> void bubbleSort(T[] a) {boolean swapped;for (int i = 0; i < a.length; i++) {swapped = false;for (int j = a.length – 1; j > i; j–) {if (a[j].compareTo(a[j – 1]) < 0) {swap(a, j, j – 1);swapped = true;}}if (!swapped) { break; }}}
四、希尔排序
希尔排序属于插入类排序，，是将整个无序列分割成若干小的子序列分别进行插入排序。将要排序的一组数按某个增量 gap 分成 gap 组，每组中记录的下标相差 gap.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
性能：
最坏的情况：取决于增量（在这里的基底是3）
最好的情况：取决于增量
平均状况：取决于增量
不稳定
额外需要的空间：O(n)
java实现：
看自家总在期待,不知将来好歹,新乐吧总在不断等待,
