以下是數(shù)組排序?qū)崿F(xiàn)的框架。這段代碼是我們的排序方法適用于任意實(shí)現(xiàn)了 Comparable 接口的數(shù)據(jù)類(lèi)型。
先說(shuō)說(shuō)幾個(gè)對(duì)于所有排序算法都很重要的問(wèn)題：
①、驗(yàn)證： 推薦在測(cè)試代碼中添加一條語(yǔ)句 assert isSort(arr); 來(lái)確認(rèn)排序后數(shù)組元素都是有序的。
②、運(yùn)行時(shí)間： 要評(píng)估算法的性能。首先，要計(jì)算各個(gè)排序算法在不同的隨機(jī)輸入下的基本操作的次數(shù)（包括比較和交換，或者是讀寫(xiě)數(shù)組的次數(shù)）；然后，我們用這些數(shù)據(jù)來(lái)估計(jì)算法的相對(duì)性能
③、額外的內(nèi)存使用： 排序算法的額外內(nèi)存開(kāi)銷(xiāo)和運(yùn)行時(shí)間是同等重要的。
④、數(shù)據(jù)類(lèi)型： 我們的排序算法模板適用于任何實(shí)現(xiàn)了 Comparable 接口的數(shù)據(jù)類(lèi)型。
/**
* 排序算法類(lèi)的模板
*
* @author TinyDolphin
* 2017/11/1 14:20.
*/
public class Example {
/**
* 排序?qū)崿F(xiàn)
*
* @param arr 待排序數(shù)組
*/
public static void sort(Comparable[] arr) {
// 各種各樣的排序代碼，后續(xù)實(shí)現(xiàn)
// ......
}
/**
* 比較兩個(gè)元素的大小
*
* @param comparableA 待比較元素A
* @param comparableB 待比較元素B
* @return 若 A < B,返回 true,否則返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 將兩個(gè)元素交換位置
*
* @param arr 待交換元素所在的數(shù)組
* @param indexI 第一個(gè)元素索引
* @param indexJ 第二個(gè)元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印數(shù)組的內(nèi)容
*
* @param arr 待打印的數(shù)組
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判斷數(shù)組是否有序
*
* @param arr 待判斷數(shù)組
* @return 若數(shù)組有序，返回 true，否則返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[]{1, 2, 3, 4, 5};
sort(arr);
assert isSort(arr);
show(arr);
}
}
注意：編譯器默認(rèn)不適用 assert 檢測(cè)（但是junit測(cè)試中適用），所以要使用時(shí)要添加參數(shù)虛擬機(jī)啟動(dòng)參數(shù) -ea 具體添加過(guò)程，請(qǐng)參照 eclipse 和 IDEA 設(shè)置虛擬機(jī)啟動(dòng)參數(shù)
