實(shí)現(xiàn)兩種初級(jí)的排序算法：
選擇排序思路
首先，找到數(shù)組中最小的那個(gè)元素，其次，將它和數(shù)組的第一個(gè)元素交換位置（如果最小的就是第一個(gè)那就自己跟自己交換）。再次，在剩下的元素中找到最小的元素，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)，直到將整個(gè)數(shù)組排序。
完整代碼
public class Selection {
public static void sort(Comparable[] a){
for (int i = 0; i < a.length; i++){
for (int j = i+1; j < a.length;j++){
if (less(a[j], a[i])) exchange(a,i,j);
}
}
show(a);
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
分析
這種實(shí)現(xiàn)十分簡(jiǎn)單且容易理解的算法有兩個(gè)特點(diǎn)：
1.運(yùn)行時(shí)間和輸入無(wú)關(guān)：即使輸入了一個(gè)已經(jīng)有序的數(shù)組，這個(gè)算法依然會(huì)從頭到尾的比較一遍，也就是說(shuō)，沒(méi)有利用到數(shù)組的初始狀態(tài)。
2.數(shù)據(jù)移動(dòng)較?。鹤疃嘀贿M(jìn)行N次交換。
插入排序思路與分析
從序列的第二個(gè)元素開始，向前進(jìn)行比較，如果第二個(gè)元素比第一個(gè)小，那么將它們對(duì)換，然后從第三個(gè)元素開始，如果第三個(gè)元素比第二個(gè)大，那么直接向后從第四個(gè)開始，如果第三個(gè)元素比第二個(gè)小，那么將它們對(duì)換，然后又比較第二個(gè)和第一個(gè)，完成后向后從第四個(gè)開始，在這種情況下，如果數(shù)組是部分有序的，這種算法就因?yàn)榭梢允÷缘粢恍┫蚯斑M(jìn)行的比較從而加快速度。事實(shí)上，當(dāng)序列中倒置的元素非常少時(shí)，這個(gè)算法可能比其他任何算法都快。
完整代碼
public class Insertion {
public static void sort(Comparable[] a){
for (int i = 1; i < a.length; i++){
for (int j = i; j > 0 && less(a[j], a[j-1]);j--) exchange(a,j,j-1);
}
show(a);
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
比較兩種初級(jí)的排序算法：
在實(shí)際應(yīng)用中插入排序都比選擇排序要快一些，往往是快一倍左右(使用盡量大的數(shù)據(jù)更容易得到這個(gè)結(jié)果，比如大小為一萬(wàn)的數(shù)組重復(fù)一千次)。
測(cè)試代碼
1.用于計(jì)時(shí)的類
public class StopWatch {
private final long start;
public StopWatch(){
start = System.currentTimeMillis();
}
public double elapsedTime(){
long now = System.currentTimeMillis();
return (now-start)/1000.0;
}
}
用于比較兩種排序算法運(yùn)行時(shí)間的測(cè)試代碼
public class Main {
public static void main(String[] args) {
String alg1 = args[0];
String alg2 = args[1];
int N = Integer.parseInt(args[2]);
int T = Integer.parseInt(args[3]);
double t1 = timeRandomInput(alg1,N,T);
double t2 = timeRandomInput(alg2,N,T);
System.out.println(alg1 + " : " + t1);
System.out.println(alg2 + " : " + t2);
}
public static double timeRandomInput(String alg, int N, int T){
double total = 0.0;
Double[] a = new Double[N];
for (int t = 0; t < T; t++){
for (int i = 0; i < N; i++) a[i] = Math.random();
total += time(alg,a);
}
return total;
}
public static double time(String alg, Double[] a){
StopWatch timer = new StopWatch();
if (alg.equals("Insertion")) Insertion.sort(a);
if (alg.equals("Selection")) Selection.sort(a);
if (alg.equals("Shell"))Shell.sort(a);
return timer.elapsedTime();
}
}
運(yùn)行命令
% javac Insertion.java Main.java Selection.java StopWatch.java
% java Main Insertion Selection 10000 1000
代碼比較簡(jiǎn)單，執(zhí)行用例所需的參數(shù)為兩種算法的名稱，數(shù)組大小，循環(huán)次數(shù)（循環(huán)進(jìn)行用戶指定大小的隨機(jī)數(shù)組的生成及排序），輸出結(jié)果是兩種算法各自運(yùn)行的時(shí)間。在筆者的電腦上輸出是這樣的
這驗(yàn)證了插入排序往往比選擇排序快一倍的說(shuō)法。然而，這兩種算法對(duì)于大規(guī)模的亂序數(shù)組都是非常慢的（等上面的輸出等了老半天，不過(guò)滿屏的數(shù)字很有黑客帝國(guó)的感覺(jué)）。
一種改進(jìn)：希爾排序
希爾排序是對(duì)插入排序的一個(gè)改進(jìn)，我認(rèn)為對(duì)于這種算法比較好的一種理解方式就是假裝自己是一臺(tái)計(jì)算機(jī)，然后假裝收到了一條需要為一個(gè)容量為10的亂序數(shù)組排序的命令，再按照下面的代碼在草稿紙上一步一步地去運(yùn)行，自然就明白了，參見(jiàn)維基百科 。
代碼中除了sort方法于上面不同之外其他部分都一樣：
public class Shell {
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1){
for (int i = h; i < N; i++){
for (int j = i; j > h &&less(a[j], a[j-h]); j -= h)exchange(a,j,j-h);
}
h/=3;
}
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exchange(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for (int i = 1; i < a.length; i++){
if (less(a[i],a[i-1])) return false;
}
return true;
}
}
測(cè)試一下改進(jìn)后算法的速度：
運(yùn)行命令
% javac Shell.java
% java Main Insertion Shell 10000 1000
希爾排序比插入排序快的不是一點(diǎn)點(diǎn)。
問(wèn)：我去，這是為什么？為什么多跳了幾遍會(huì)比直接排快？為什么一個(gè)小小的改變會(huì)帶來(lái)這么大的差距？
答：不知道。
算法一書原文：“The study of the performance characteristics of shellsort requires mathematical arguments that are beyond the scope of this book.”（這題超綱了）
維基百科：“希爾排序通過(guò)將比較的全部元素分為幾個(gè)區(qū)域來(lái)提升插入排序的性能。這樣可以讓一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來(lái)越小的步長(zhǎng)進(jìn)行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時(shí)插入排序較快）”。
對(duì)于中等大小的問(wèn)題，希爾排序的運(yùn)行時(shí)間是可以接受的,他的代碼量很小而且不需要額外的存儲(chǔ)空間，磚家推薦一般先用希爾排序?qū)崿F(xiàn)，在發(fā)現(xiàn)性能不行的時(shí)候再考慮改進(jìn)。對(duì)于大型問(wèn)題，就需要接下來(lái)的算法了。
資源以及參考
普林斯頓大學(xué)算法課程以其教材《算法》第四版
維基百科
