排序算法(Java实现)：选择排序法和快速排序法

排序算法(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. }