一、 大O表示法
在進行排序算法之前，我們得先掌握一種對算法效率的表示方法，大O表示法。
我們使用大O表示法來表示算法的時間復雜度，是用來表示算法的速度隨著數據量的變化而如何變化的。
常見的大O表示函數：
- O(1)：常數的
- O(log n)：對數的
- O(n)：線性的
- O(n*log(n))：線性和對數乘積
- O(n2)：平方
- O(2n)：指數
推導大O表示法的方式：
- 用 常量1取代運行時間中所有的加法常量
- 在修改后的運行次數函數中，只保留最高階項
- 如果最高存在且不為1，則去除與這個項相乘的常數
二、排序算法
排序算法有很多很多，這里就不全部實現，只實現一些比較常見的排序算法。
簡單排序：冒泡排序、選擇排序、插入排序
高級排序：希爾排序、快速排序
1.冒泡排序
冒泡排序算法相對其他排序運行效率較低，但是它是最簡單的一種排序。
原理：冒泡排序的原理（以遞增序為例）是每次從頭開始依次比較相鄰的兩個元素，如果后面一個元素比前一個要小，說明順序不對，則將它們交換，本次循環完畢之后再次從頭開始掃描，直到某次掃描中沒有元素交換，說明每個元素都不比它后面的元素大，至此排序完成。
過程：
代碼：
// 冒泡排序 function bubbleSort (array) { for(var i = 0; i < array.length - 1; i++) { // 表示比較的趟數 for(var j = 0; j < array.length - i - 1; j++) { // 表示比較的次數 if(array[j] > array[j+1]) { var temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } } } // 測試 var array = [3,24,7,1,2,10,6,12]; bubbleSort(array); console.log(array.toString()); // 結果為：1,2,3,6,7,10,12,24
效率：
- 冒泡排序的比較次數：
通過大O表示法來推導過程，n個數字比較時，第一次循環比較n-1次，第二次循環比較n-2次，第三次比較n-3次，…，直到最后一次比較1次。
比較次數：(n-1)+(n-2)+(n-3)+ … +3+2+1
所以比較次數是：n*(n-1)/2
根據大O表示法只保留最高階項，去除常量，只剩n*n - 冒泡排序的交換次數：
交換次數不是確定的，所以以每兩次比較交換一次來進行計算
交換次數：n*(n-1)/4
根據大O表示法只保留最高階項，去除常量，只剩n*n
因此冒泡排序的大O表示法為O(n2)
2.選擇排序
選擇排序可以看作是冒泡排序的改進版本。
思路：選擇排序，從頭至尾掃描序列，找出最小的一個元素，和第一個元素交換，接著從剩下的元素中繼續這種選擇和交換方式，最終得到一個有序序列。
過程：
代碼：
// 選擇排序 function selectionSort(array) { var min; for(var i = 0; i < array.length - 1; i++) { // 外層循環，從0位置開始取數據 min = i; for(var j = i + 1; j < array.length; j++) { // 內層循環，從i+1位置開始選擇出最小的數據 if(array[min] > array[j]) { min = j; // 找到小的數據，并且對min賦值 } } var temp = array[min]; // 此時最小的數據就是第min個位置的數據,min和i位置數據交換 array[min] = array[i]; array[i] = temp; } } // 測試 var array = [4,8,2,7,3,1]; selectionSort(array); console.log(array.toString()); // 結果為：1,2,3,4,7,8
效率：
- 選擇排序的比較次數：
選擇排序和冒泡排序的比較次數都是：n*(n-1)/2
用大O表示法都是O(n2) - 選擇排序的交換次數：
選擇排序每次進行選擇時，最多需要交換1次，一共遍歷n-1次
用大O表示法就是O(n)
所以選擇排序通常認為在執行效率上是高于冒泡排序的
3.插入排序
插入排序是簡單排序中效率最好的一種，而且插入排序也是學習其他高級排序的基礎。
思路：
將待排序序列中第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列，從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。
過程：
代碼①：
// 插入排序 function insertionSort(array) { for(var i = 1; i < array.length; i++) { // 外層循環，從第1個位置開始獲取數據，向前面局部有序進行插入 var temp = array[i]; // 取出要插入的元素 var j = i; while(array[j - 1] > temp && j > 0) { // 內層循環，將要插入的元素和前面的元素依次進行比較，找到合適的插入位置 array[j] = array[j-1]; j--; } // 將temp放置到j位置上 array[j] = temp; } }
代碼②：
function insertSort(arr){ //從第二個數開始，依次插入 for(var i=1; i<arr.length; i++){ //判斷目標元素是否小于前一個元素 if(arr[i]<arr[i-1]){ var current=arr[i]; var j=i-1; //從有序數列從后往前對比，如果目標元素小于與之對比的當前元素，當前元素位置往后挪一位 while(j>=0 && current<arr[j]) { arr[j+1]=arr[j]; j--; } //插入 arr[j+1]=current; } } return arr; }
效率：
- 插入排序的比較次數：
第一次最多需要比較1次，第二次最多需要比較2次，……，最后一次最多需要比較n-1次。
因此插入排序的最多比較次數是1+2+3+…+n-1 = n*(n-1)/2
但是每次插入我們大概只需要進行一半的比較
所以插入排序的比較次數為n*(n-1)/4， 相對于冒泡和選擇排序，比較次數少了一半。 - 插入排序的復制次數：
第一次最多需要復制1次，第二次最多需要復制2次，……，最后一次最多需要復制n-1次。
因此插入排序的最多復制次數是n*(n-1)/2
但是每次復制我們大概只需要進行一半的復制
所以插入排序的復制次數為n*(n-1)/4
4.希爾排序
希爾排序是插入排序的一種高效的改進版，并且效率比插入排序更快。
插入排序的問題：
由于希爾排序基于插入排序，所以我們需要回顧一下插入排序以及它的問題。
插入排序的問題：
假設一個較小的數據項在很靠近右端的位置上，這里本來應該時較大的數據項的位置，要把這個小數據項移動到左邊的正確位置，所有的中間數據項都必須向右移動一位，每個步驟對數據項都進行n次復制，平均下來就是移動n/2次，n個元素就是n*n/2= n2/2，所以插入排序的效率時O(n2)。
如果有某種方式，不需要一個個移動所有中間的數據項，就能把較小的數據項移動到左邊，那么算法的執行效率就會有很大的改進。
思路：
希爾排序就是把無序的數組分割成很多的子序列，子序列不是逐段分割的，而是相隔特定增量的子序列，對各個子序列進行插入排序，然后再選擇一個更小的增量，將之前排序后的數組按這個增量分割成多個子序列，對各個子序列進行插入排序，……，不斷選擇更小的增量，直到增量為1時，再對序列進行一次插入排序，使序列最終成為有序序列，即排序完成。
希爾排序增量的選擇：
初始增量為n/2，下一次的增量為原來的1/2，直到增量為1。
比如對于n = 100的數組，增量間隔序列為：50，25，12，6，3，1
過程：
代碼：
// 希爾排序 function shellSort(array) { // 獲取數組的長度 var length = array.length; // 初始化增量 var gap = Math.floor(length / 2); // 循環讓gap不斷減小，直到為1 while(gap >= 1) { // 以gap為間隔，進行分組，對分組進行插入排序 for(var i = gap; i < length; i++) { var temp = array[i]; var j = i; while(array[j-gap] > temp && j > gap - 1) { array[j] = array[j - gap]; j -= gap; } // 將j位置的元素賦值temp array[j] = temp; } // 增量變化 gap = Math.floor(gap / 2); } } // 測試： var array = [62,88,58,47,61,35,73,51,99,37,93]; shellSort(array); console.log(array.toString()); // 結果為：35,37,47,51,58,61,62,73,88,93,99
效率：
希爾排序的效率和增量是有關系的，但是，它的效率證明非常困難，甚至某些增量的效率至今沒有唄證明出來。但是經過統計，希爾排序使用原始增量，最壞情況下的的時間復雜度為O(n2)，通常都要好于O(n2)。
總之，我們使用希爾排序大多數情況下效率都高于簡單排序。
5.快速排序
快速排序幾乎可以說是目前所有排序算法中，最快的一種排序算法。
快速排序其實是冒泡排序的升級版本，冒泡排序需要經過很多次交換，才能在一次循環中，將最大值放在正確的位置，而快速排序可以在一次循環中，找到某個元素的正確位置，并且該元素之后也不需要任何移動。
快速排序的思想就是分而治之。
思路：
快速排序采用分而治之的思想，將待排序的數中取出一個數作為基準數，將比這個數大的數字全部放在它的右邊，比這個數字小的或者等于的全部放在它的左邊，再對左右區間重復第二步，直到各個區間只有一個數。基準值我選擇數組的第一項。
過程：
代碼①：
// 快排頂層調用函數 function quickSort(arr) { quick(0, arr.length - 1, arr); } // 快排遞歸調用函數 function quick(left, right, arr) { var i = left + 1; // 指針i從left+1向右找比基準值大的，因為基準值是arr[left],基準值自己和自己不做比較 var j = right; // 指針j從right向左找比基準值小的 var base = arr[left]; // 基準值選擇待排序數組的最左一項 if(arr.length <= 1) return; // 如果數組為空或只有一個元素，則直接返回 if(left >= right) return; // 退出判斷，如果left >= right，本次遞歸退出 while(i < j) { while(i < j && arr[j] > base) j--; // 讓j指針一直向左找到小于基準值的 while(i < j && arr[i] < base) i++; // 讓i指針一直向右找到大于基準值的 if(i < j) { // 找到后，讓i，j指向的數據進行交換 var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } arr[left] = arr[i]; // 直到i，j指針相遇，則交換i指向的數據和基準值的數據 arr[i] = base; // 這樣，就讓基準值的左邊數據都小于基準值，右邊數據都大于基準值 quick(left, i-1, arr); // 遞歸快排，left——i-1的數據 quick(i+1, right, arr); // 遞快排，i+1——right的數據 }; var arr = [6, 3, 4, 7, 2, 9, 12, 1,8,22]; quickSort(arr); console.log(arr.toString()); // 結果為：1,2,3,4,6,8,7,9,22,12
代碼②：
function quickSort(arr){ //如果數組<=1,則直接返回 if(arr.length<=1){return arr;} var pivotIndex=Math.floor(arr.length/2); //找基準，并把基準從原數組刪除 var pivot=arr.splice(pivotIndex,1)[0]; //定義左右數組 var left=[], right=[]; //比基準小的放在left，比基準大的放在right for(var i=0;i<arr.length;i++){ if(arr[i]<=pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } } //遞歸 return quickSort(left).concat(pivot, quickSort(right)); }
效率：
快速排序被認為是速度最快的排序算法。
快速排序的平均速率是O(n * log n)
如果以上還是不能理解，那就點擊下方在線動畫演示：
在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys
浙公網安備 33010602011771號