我們都知道，在應屆面試的時候，問到最多的就是快速排序，快速排序是最經典、最常用的排序算法，因為它的平均效率最優，也最穩定。

快速排序使用了分治的算法思想，分治算法本身理解起來很符合人類的思路（遞歸是很容易被理解的），其最關鍵的一步，就是劃分了，算法導論上介紹了一種劃分方法，和我在數據結構課上學的略有不同，昨晚，我把它們全都用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。插入排序是最樸素的排序算法，也是相對較慢的排序算法。

?

學數據結構的課程時，我非常喜歡堆排序?；蛟S是因為它是最形象的排序算法。其實，堆排序利用特有的數據結構，高效的做了這么一件事，每次找出最小的數，然后從數組中刪掉這個數，繼續查找。

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一個足夠大的數組，然后對待排序數組遍歷，將新數組鍵等于待排序數組中值的位置置為一（多個則繼續增一），然后遍歷新數組，即可得到待排序數組的順序。這種算法不適合離散性數據，也不適合不知道范圍的數據排序。

?

對于常規排序算法，冒泡排序適合只有少數數據不在正確位置上的數據，快速排序的平均效率最高，堆排序性能極不穩定，插入排序的效率較差。

?

以上。

?

轉載于:https://www.cnblogs.com/toocooltohavefriends/p/5349375.html

總結

以上是生活随笔為你收集整理的排序算法分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。