我們都知道，在應屆面試的時候，問到最多的就是快速排序，快速排序是最經典、最常用的排序算法，因為它的平均效率最優，也最穩定。
快速排序使用了分治的算法思想，分治算法本身理解起來很符合人類的思路（遞歸是很容易被理解的），其最關鍵的一步，就是劃分了，算法導論上介紹了一種劃分方法，和我在數據結構課上學的略有不同，昨晚，我把它們全都用java實現了。
這個是算法導論的版本：
1 /**
2 * 快速排序的劃分方法一：算法導論版本 sit的下一個比最後一個大
3 *
4 * @param begin
5 * @param end
6 * @return
7 */
8 private int QuickMergeA(int begin, int end) {
9 System.out.print("初始：" + arr);
10 System.out.print(begin + " " + end);
11 int anchor = (int) arr.get(end);
12 int sit = begin - 1;
13 int temp;
14 for (int i = begin; i < end; i++) {
15 if ((int) arr.get(i) <= anchor) {
16 sit++;
17 temp = (int) arr.get(i);
18 arr.set(i, (int) arr.get(sit));
19 arr.set(sit, temp);
20 }
21 }
22 temp = (int) arr.get(sit + 1);
23 arr.set(sit + 1, anchor);
24 arr.set(end, temp);
25 System.out.print(arr);
26 System.out.println(sit + 1);
27 return sit + 1;
28 }
不難看出，這個版本的劃分思路是，從數組一端往另一端推進，對於比指定元素小的值，均放在左側，比指定元素大的值，放在右側。
然後我們再看我數據結構課本上學過的版本：
/**
* 快速排序的劃分方法二：數據結構課本版本
*
* @param begin
* @param end
* @return
*/
private int QuickMergeB(int begin, int end) {
System.out.print("初始：" + arr);
System.out.print(begin + " " + end);
int anchor = arr.get(end);
int send = end - 1;
int temp;
int tbegin = begin;
while (begin <= send) {
while (arr.get(begin) <= anchor && begin <= end - 1) {
begin++;
}
while (send >= tbegin && arr.get(send) > anchor) {
send--;
}
if (begin < send) {
temp = arr.get(begin);
arr.set(begin, arr.get(send));
arr.set(send, temp);
}
if (begin >= send) {
temp = arr.get(begin);
arr.set(begin, arr.get(end));
arr.set(end, temp);
}
}
System.out.print(arr);
System.out.println(send + 1);
return send + 1;
}
可以看出，這種思路是兩端推進的手段，兩端同時推進，同樣是左邊存放比指定元素小的值，右邊存放比指定元素大的值。
這兩種方法遍歷數組的推進方法雖然不同，但是其效率是一致的，劃分一次都相當於是要遍歷一次子數組。其劃分的包裝入口也是相似的：
/**
* 快速排序入口
*
* @param begin
* @param end
*/
private void QuickSequence(int begin, int end) {
// if (begin < end) {
// int q = QuickMergeA(begin, end);
// this.QuickSequence(begin, q - 1);
// this.QuickSequence(q + 1, end);
// }
if (begin < end) {
int q = QuickMergeB(begin, end);
this.QuickSequence(begin, q - 1);
this.QuickSequence(q + 1, end);
}
}
需要指明的是，測試上面方法的過程中，應該把arr數組設置為靜態的，在java中，實現類似於C++的地址訪問的情況，我經常使用靜態變量。
最古老的排序算法是插入排序，之前學習數據結構的時候，對於各種排序算法總是混淆，比如對於快速排序和插入排序的算法思路都明白，但是總是把快速排序當成插入排序，插入排序當成快速排序。也許是當時兩節課學了冒泡排序、快速排序、插入排序、堆排序等太多的排序算法吧，加上編程經驗少造成的。
其實插入排序很容易和快速排序區分開。因為插入排序是真的“插入”。插入排序的基礎是左側數據已經排序准確，你要做的是把下一個數插入到有序數組的指定位置，你可以腦補撲克牌。
/**
* 插入排序
*/
private void InsertSequence() {
for (int i = 0; i < arr.size(); i++) {
int p = 0;
while (p < i && arr.get(p) < arr.get(i)) {
p++;
}
if (p < i) {
int temp = arr.get(i);
for (int k = i; k > p; k--) {
arr.set(k, arr.get(k - 1));
}
arr.set(p, temp);
}
}
}
插入排序的代碼很短，但是我們的經驗是，短的代碼代表思路簡單，不代表效率高。其實是這樣的，插入排序的效率是N^2,而快速排序的效率則是NlogN。插入排序是最樸素的排序算法，也是相對較慢的排序算法。
學數據結構的課程時，我非常喜歡堆排序。或許是因為它是最形象的排序算法。其實，堆排序利用特有的數據結構，高效的做了這麼一件事，每次找出最小的數，然後從數組中刪掉這個數，繼續查找。
1 private void MaintainHeap(int length) {
2 int temp;
3 for (int i = length / 2 - 1; i >= 0; i--) {
4 if ((arr.get(i) < arr.get((i + 1) * 2 - 1))
5 || ((i + 1) * 2 < length && arr.get(i) < arr
6 .get((i + 1) * 2))) {
7 if ((i + 1) * 2 < length) {
8 if (arr.get((i + 1) * 2) < arr.get((i + 1) * 2 - 1)) {
9 temp = arr.get(i);
10 arr.set(i, arr.get((i + 1) * 2 - 1));
11 arr.set((i + 1) * 2 - 1, temp);
12 } else {
13 temp = arr.get(i);
14 arr.set(i, arr.get((i + 1) * 2));
15 arr.set((i + 1) * 2, temp);
16 }
17
18 } else {
19 temp = arr.get(i);
20 arr.set(i, arr.get((i + 1) * 2 - 1));
21 arr.set((i + 1) * 2 - 1, temp);
22 }
23
24 }
25 }
26
27 System.out.println(arr);
28 }
29
30 private void Heapsequence(int length) {
31 for (int i = length; i > 0; i--) {
32 this.MaintainHeap(i);
33 int temp = arr.get(0);
34 arr.set(0,arr.get(i - 1));
35 arr.set(i - 1, temp);
36 }
37 }
堆排序的重要步驟是堆的維護。對於最大堆而言，要確保特定個元素構建的堆中，每個節點的值都大於其孩子節點，這通常的方法是，從最後一個有子節點的節點開始，遍歷到根節點，對於這其間的每一個結點，如果其子節點存在大於當前節點的節點，則把最大的子節點同當前節點交換，並同時維護交換後的子節點的狀態（這個子節點的子節點可能在交換後比子節點的值大）。
除了上面的排序算法，我們常見的還有冒泡排序之類。同時，我在算法導論上，還接觸過計數排序、基數排序、桶排序等線性排序算法。因為其思路比較簡單，所以這裡只給出一般思路：
計數排序顧名思義，使用了一個計數數組，對於每一個值，初始計數為0，每新增一個，該計數就增加一，最後形成一個排序序列。計數排序的效率一般，但是由於其穩定，常常作為其它排序算法基本過程的算法使用。
基數排序是另外一種比較有意思的排序算法，它先從最低位對數據進行排序，然後再依次上升到最高位，而對每個數位的排序，他通常使用計數排序。
桶排序是效率最高的排序算法，但是它對數據要求較高，同時是一種以空間換時間的排序算法。它的方案是先new一個足夠大的數組，然後對待排序數組遍歷，將新數組鍵等於待排序數組中值的位置置為一（多個則繼續增一），然後遍歷新數組，即可得到待排序數組的順序。這種算法不適合離散性數據，也不適合不知道范圍的數據排序。
以上。
