這篇文章主要介紹了JavaScript中幾種排序算法的簡單實現,排序是各種編程語言學習中都是共通的必會的基礎,需要的朋友可以參考下

排序算法的實現

我的JS水平就是渣渣，所以我就用類似于JAVA和C的方式來寫JavaScript的排序算法了。

而且這里我不講算法原理，僅僅只是代碼實現，可能會有Bug，歡迎大家博客評論指導。

插入排序

插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序(即只需用到O(1)的額外空間的排序)，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

實現代碼如下：

1. function insertSort(arr) { 
2. if (!arr) return; 
3. var len = arr.length; 
4. if (len == 0 || len == 1) return; 
5.  
6. for (var i = 1, len = arr.length; i < len; i ++) { 
7. var stand = arr[i]; 
8. for (var j = i - 1; j >= 0; j --) { 
9. if (arr[j] > stand) { 
10. arr[j + 1] = arr[j]; 
11. } else { 
12. arr[j + 1] = stand; 
13. break; 
14. } 
15. } 
16. } 
17.  
18. return arr; 
19. } 

時間復雜度為：O(n^2)

當然，該算法是有優化余地的，例如將搜索替換的位置算法改為二分查找。

冒泡排序

經典的排序算法，提到冒泡排序我就心痛。本科時候的必須論文的冒泡排序算法的改進，結果寫完論文之后都不能完整的實現冒泡排序算法，好尷尬。

1. if (!arr) return; 
2. var len = arr.length; 
3. if (len == 0 || len == 1) return; 
4.  
5. for (var i = 0; i < len; i ++) { 
6. for (var j = 0; j < len - i - 1; j ++) { 
7. if (arr[j] > arr[j + 1]) { 
8. var tmp = arr[j + 1]; 
9. arr[j + 1] = arr[j]; 
10. arr[j] = tmp; 
11. } 
12. } 
13. } 
14.  
15. return arr; 
16. } 

時間復雜度為：O(n^2)

快速排序

非常經典的排序算法，排序過程主要i分為三步：

從數列中挑出一個元素，稱為 “基準”(pivot);

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區(partition)操作;

遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。

實現代碼如下：

1. function quickSort(arr, bt, ed) { 
2. if (bt < ed) { 
3. var pivot = findPartition(arr, bt, ed); 
4. quickSort(arr, bt, pivot - 1); 
5. quickSort(arr, pivot + 1, ed); 
6. } 
7. } 
8.  
9. function findPartition(arr, bt, ed) { 
10. var stand = arr[bt]; 
11.  
12. while (bt < ed) { 
13. while (bt < ed && arr[ed] >= stand) { 
14. ed --; 
15. } 
16. if (bt < ed) { 
17. arr[bt ++] = arr[ed]; 
18. } 
19. while (bt < ed && arr[bt] <= stand) { 
20. bt ++; 
21. } 
22. if (bt < ed) { 
23. arr[ed --] = arr[bt];  
24. } 
25. } 
26.  
27. arr[bt] = stand; 
28. return bt; 
29. } 

時間復雜度為：O(nlogn)。

歸并排序

也是非常經典的排序算法，我就是借著學習js的機會復習經典的排序算法了。歸并排序的思想可以參考我的這篇博客：歸并排序。我這里只寫js實現。

1. function mergeSort(arr, bt, ed) { 
2. if (bt < ed) { 
3. var mid = bt + parseInt((ed - bt) / 2); 
4. mergeSort(arr, bt, mid); 
5. mergeSort(arr, mid + 1, ed); 
6. mergeArray(arr, bt, mid, ed);  
7. } 
8. } 
9.  
10. function mergeArray(arr, bt, mid, ed) { 
11. var mArr = []; 
12. var i = bt, j = mid + 1; 
13. while (i <= mid && j <= ed) { 
14. if (arr[i] <= arr[j]) { 
15. mArr.push(arr[i++]); 
16. } else { 
17. mArr.push(arr[j ++]); 
18. } 
19. } 
20.  
21. if (i <= mid) { 
22. mArr = mArr.concat(arr.slice(i, mid + 1)); 
23. } 
24.  
25. if (j <= ed) { 
26. mArr = mArr.concat(arr.slice(j, ed + 1)); 
27. } 
28.  
29. for (var h = 0; h < mArr.length; h ++) { 
30. arr[bt + h] = mArr[h]; 
31. } 
32. } 

寫歸并排序的時候還有一個小插曲：就是js不能自動取整，后來用了parseInt方法，感覺萌萌大。