排序算法(Java實現)：選擇排序法和快速排序法

為了方便擴展，先引入一個抽象的基礎類：

[html]

1. package com.andyidea.algorithms;  
2.   
3. /**  
4.  * 排序抽象基礎類  
5.  * @author Andy.Chen  
6.  *  
7.  * @param <T>  
8.  */  
9. public abstract class Sorter<T extends Comparable<T>> {  
10.       
11.     public abstract void sort(T[] array,int from,int len);  
12.       
13.     public final void sort(T[] array){  
14.         sort(array,0,array.length);  
15.     }  
16.       
17.     protected final void swap(T[] array,int from,int to){  
18.         T tmp = array[from];  
19.         array[from] = array[to];  
20.         array[to] = tmp;  
21.     }  
22.   
23. }  

【三】選擇排序：選擇排序(Selection sort)是一種簡單直觀的排序算法，其平均時間復雜度為O(n²)。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小元素，然後放到排序序列末尾。以此類推，直到所有元素均排序完畢。

選擇排序算法源碼如下：

[html]

1. package com.andyidea.algorithms;  
2.   
3. /**  
4.  * 選擇排序法  
5.  * @author Andy.Chen  
6.  *  
7.  * @param <T>  
8.  */  
9. public class SelectionSort<T extends Comparable<T>> extends Sorter<T> {  
10.   
11.     @Override  
12.     public void sort(T[] array, int from, int len) {  
13.         for(int i=from;i<from+len;i++){  
14.             int smallestindex = i;  
15.             int j = i;  
16.             for(; j<from+len; j++){  
17.                 if(array[j].compareTo(array[smallestindex])<0){  
18.                     smallestindex = j;  
19.                 }  
20.             }  
21.             swap(array, i, smallestindex);  
22.         }  
23.     }  
24.   
25. }  

選擇排序的交換操作介於0和(n − 1)次之間。選擇排序的比較操作為n(n − 1) / 2次之間。選擇排序的賦值操作介於0和3(n − 1)次之間。

【四】快速排序：快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序算法的具體操作描述如下：

1. 從數列中挑出一個元素，稱為 "基准"（pivot），
2. 重新排序數列，所有元素比基准值小的擺放在基准前面，所有元素比基准值大的擺在基准的後面（相同的數可以到任一邊）。在這個分區退出之後，該基准就處於數列的中間位置。這個稱為分區（partition）操作。
3. 遞歸地（recursive）把小於基准值元素的子數列和大於基准值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

快速排序算法源碼如下：

[html]

1. package com.andyidea.algorithms;  
2.   
3. /**  
4.  * 快速排序法  
5.  * @author Andy.Chen  
6.  *  
7.  * @param <T>  
8.  */  
9. public class QuickSort<T extends Comparable<T>> extends Sorter<T> {  
10.   
11.     @Override  
12.     public void sort(T[] array, int from, int len) {  
13.         quick_sort(array, from, from+len-1);  
14.     }  
15.       
16.     private void quick_sort(T[] array,int from, int to){  
17.         if(to-from < 1)  
18.             return;  
19.         int pivot = selectPivot(array, from, to);  
20.         pivot = partition(array, from, to, pivot);  
21.           
22.         quick_sort(array, from, pivot-1);  
23.         quick_sort(array, pivot+1, to);  
24.     }  
25.       
26.     /**  
27.      * 選擇基准元素  
28.      * @param array  
29.      * @param from  
30.      * @param to  
31.      * @return  
32.      */  
33.     private int selectPivot(T[] array,int from, int to){  
34.         return (from+to)/2;  
35.     }  
36.       
37.     /**  
38.      * 分區操作  
39.      * @param array  
40.      * @param from  
41.      * @param to  
42.      * @param pivot  
43.      * @return  
44.      */  
45.     private int partition(T[] array, int from, int to, int pivot){  
46.         T tmp = array[pivot];  
47.         array[pivot] = array[to];  
48.         while(from != to){  
49.             while(from<to && array[from].compareTo(tmp)<=0)  
50.                 from++;  
51.             if(from<to){  
52.                 array[to] = array[from];  
53.                 to--;  
54.             }  
55.               
56.             while(from<to && array[to].compareTo(tmp)>=0)  
57.                 to--;  
58.             if(from<to){  
59.                 array[from] = array[to];  
60.                 from++;  
61.             }  
62.         }  
63.         array[from] = tmp;  
64.         return from;  
65.     }  
66.   
67. }