JavaScript中几种排序算法的简单实现

这篇文章主要介绍了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方法，感觉萌萌大。