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

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

[html]

1. package com.andyidea.algorithms;
3. /**
4. * 排序抽象基礎類
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public abstract class Sorter<T extends Comparable<T>> {
11. public abstract void sort(T[] array,int from,int len);
13. public final void sort(T[] array){
14. sort(array,0,array.length);
15. }
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. }
23. }

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

選擇排序算法源碼如下：

[html]

1. package com.andyidea.algorithms;
3. /**
4. * 選擇排序法
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public class SelectionSort<T extends Comparable<T>> extends Sorter<T> {
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. }
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;
3. /**
4. * 快速排序法
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public class QuickSort<T extends Comparable<T>> extends Sorter<T> {
11. @Override
12. public void sort(T[] array, int from, int len) {
13. quick_sort(array, from, from+len-1);
14. }
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);
22. quick_sort(array, from, pivot-1);
23. quick_sort(array, pivot+1, to);
24. }
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. }
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. }
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. }
67. }