常见的几种数组排序算法JS实现 常见的几种数组排序算法JS实现

常见的几种数组排序算法JS实现
常见的几种数组排序算法JS实现

网上找到一些算法思想,然后自己用JS表现出来(小菜一只,大神勿喷)
思想到是很简单,打代码,调试代码,细节可以让人抓狂,好了不说了,下面是我的劳动成果

常见的排序算法思想

快速排序

 从给定的数据中,随机抽出一项,这项的左边放所有比它小的,右边放比它大的,然后再分别这两边执行上述操作,采用的是递归的思想,总结出来就是 实现一层,分别给两边递归,设置好出口

function fastSort(array,head,tail){
    //考虑到给每个分区操作的时候都是在原有的数组中进行操作的,所以这里head,tail来确定分片的位置
    /*生成随机项*/
    var randomnum = Math.floor(ranDom(head,tail));
    var random = array[randomnum];
    /*将小于random的项放置在其左边  策略就是通过一个临时的数组来储存分好区的结果,再到原数组中替换*/
    var arrayTemp = [];
    var unshiftHead = 0;
    for(var i = head;i <= tail;i++){
      if(array[i]<random){
        arrayTemp.unshift(array[i]);
        unshiftHead++;
      }else if(array[i]>random){
        arrayTemp.push(array[i]);
      }
      /*当它等于的时候放哪,这里我想选择放到队列的前面,也就是从unshift后的第一个位置放置*/
      if(array[i]===random){
        arrayTemp.splice(unshiftHead,0,array[i]);
      }
    }
    /*将对应项覆盖原来的记录*/
    for(var j = head , u=0;j <= tail;j++,u++){
      array.splice(j,1,arrayTemp[u]);
    }
    /*寻找中间项所在的index*/
    var nowIndex = array.indexOf(random);

    /*设置出口,当要放进去的片段只有2项的时候就可以收工了*/
    if(arrayTemp.length <= 2){
      return;
    }
    /*递归,同时应用其左右两个区域*/
    fastSort(array,head,nowIndex);
    fastSort(array,nowIndex+1,tail);
  }

插入排序

思想就是在已经排好序的数组中插入到相应的位置,以从小到大排序为例,扫描已经排好序的片段的每一项,如大于,则继续往后,直到他小于一项时,将其插入到这项的前面

function insertSort(array){
    /*start根据已排列好的项数决定*/
    var start=1;
    /*按顺序,每一项检查已排列好的序列*/
    for(var i=start; i<array.length; start++,i++){
      /*跟已排好序的序列做对比,并插入到合适的位置*/
      for(var j=0; j<start; j++){
        /*小于或者等于时(我们是升序)插入到该项前面*/
        if(array[i]<=array[j]){
          console.log(array[i]+' '+array[j]);
          array.splice(j,0,array[i]);
          /*删除原有项*/
          array.splice(i+1,1);
          break;
        }
      }

    }
  }

冒泡排序

故名思意 ,就是一个个冒泡到最前端或者最后端,主要是通过两两依次比较,以升序为例,如果前一项比后一项大则交换顺序,一直比到最后一对

function bubbleSort(array){
    /*给每个未确定的位置做循环*/
    for(var unfix=array.length-1; unfix>0; unfix--){
      /*给进度做个记录,比到未确定位置*/
      for(var i=0; i<unfix;i++){
        if(array[i]>array[i+1]){
          var temp = array[i];
          array.splice(i,1,array[i+1]);
          array.splice(i+1,1,temp);
        }
      }
    }
  }

选择排序

将当前未确定块的min或者max取出来插到最前面或者后面

function selectSort(array){
    /*给每个插入后的未确定的范围循环,初始是从0开始*/
    for(var unfixed=0; unfixed<array.length; unfixed++){
      /*设置当前范围的最小值和其索引*/
      var min = array[unfixed];
      var minIndex = unfixed;
      /*在该范围内选出最小值*/
      for(var j=unfixed+1; j<array.length; j++){
        if(min>array[j]){
          min = array[j];
          minIndex = j;
        }
      }
      /*将最小值插入到unfixed,并且把它所在的原有项替换成*/
      array.splice(unfixed,0,min);
      array.splice(minIndex+1,1);
    }
  }

总结一下,实现思想是很简单的,难点在于如何创造思想,还有就是个人的测试能力,和编程习惯,做注释其实不是仅仅为了别人看得更方便,而是自己思路的记录,有些人编着编着容易断片,注释起到了很好的引导作用