查看: 1127|回复: 0

[JavaScript/JQuery] JavaScript的常用排序算法

发表于 2017-5-19 12:00:01

冒泡排序:
每次对比相邻两个数据的大小,升序小的拍前面,若前一个数比后一个数大,则交换两数位置。需要两次for循环遍历.

优点:简单

缺点:时间复杂度高,运行效率低下

  1. function sortArr(arr){
  2. var temp;
  3. for(var i=0;i<arr.length-1;i++){
  4. for(var j=i+1;j<arr.length;j++){
  5. if(arr[i] > arr[j]){
  6. times++;
  7. temp = arr[i];
  8. arr[i] = arr[j];
  9. arr[j] = temp;
  10. }
  11. console.log("第"+(++times)+"次排序后:"+arr);
  12. }
  13. }
  14. return arr;
  15. }
  16. var times = 0;
  17. sortArr([2,5,4,1,7,3,8,6,9,0]);
  18. out :[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码

快速排序:
先找到一个基准点(一般数组中部),数组即被分为两部分,依次与基准点数据比较,比它小的,放左边,比它大的放右边,左右分别用一个空数组去存储比较后的数据,最后执行上述操作,知道数组长度<=1;

优点:快速常用

缺点:需要额外申明两个数组,浪费了内存空间资源

  1. var times = 0;
  2. var quickSort = function(arr){
  3. if(arr.length<=1){//递归结束条件
  4. return arr;
  5. }
  6. var midIndex = Math.floor(arr.length/2);//找基准点
  7. var midIndexVal = arr.splice(midIndex,1);//取基准点的值
  8. var left = [];
  9. var right = [];
  10. for(var i=0;i<arr.length;i++){
  11. if(arr[i]<midIndexVal){
  12. left.push(arr[i]);
  13. }
  14. else{
  15. right.push(arr[i]);
  16. }
  17. console.log("第"+(++times)+"次排序后:"+arr);
  18. }
  19. return quickSort(left).concat(midIndexVal,quickSort(right));//递归执行
  20. }
  21. quickSort([2,5,4,1,7,3,8,6,9,0]);
  22. out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码


回复

使用道具 举报