JavaScript 排序算法

bluestorm 7年前
   <p>前言:在前端大全中看到这句话,以此共勉。 <strong>基础决定你可能达到的高度, 而业务决定了你的最低瓶颈</strong></p>    <p>其实javascript算法在平时的编码中用处不大,不过不妨碍我们学习它,学习一下这些算法的思想,锻炼一下自己的思维模式。</p>    <p>本文不会每种方法都介绍一下,只介绍一下七种,纯属为了学习而学习,如果觉得代码不是很好理解,可以将数组里面的内容代入函数里面。</p>    <p>不过刚开始理解的时候确实挺头疼的。废话少说,搞起来!!</p>    <h2><strong>冒泡排序</strong></h2>    <p><strong>原理:</strong></p>    <p>从第一个元素开始,往后比较,遇到比自己小的元素就交换位置</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/c33a1651e1f72af822f53a1a369d80a9.gif"></p>    <p><strong>特点:</strong></p>    <p>交换的次数最多,所以它的性能是最差的</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">function bubbleSort(arr){      var len=arr.length;      for(var i=0;i<len;i++){          for(var j=0;j<len-1-i;j++){                if(arr[j]>arr[j+1]){   //相邻元素两两对比                  var temp=arr[j+1];  //交互位置,所以大的都放到了最后面                  arr[j+1]=arr[j];                  arr[j]=temp;                }          }      }      return arr;  }  var arr=[2,3,6,4,2,1,90,100,20,5];  console.log(bubbleSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>插入排序</strong></h2>    <p><strong>原理:</strong></p>    <p>插入排序的基本操作就是将一个数据插入到 <strong>已经排好序的有序数据中</strong> ,从而得到一个新的、个数加一的有序数据</p>    <p>如图所示</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/4985908f26f839edb1583eb26d980462.jpg"></p>    <p>在插入排序中,数组会被划分为两种,“有序数组块”和“无序数组块”,</p>    <p>第一遍的时候从”无序数组块“中提取一个数20作为有序数组块。</p>    <p>第二遍的时候从”无序数组块“中提取一个数60有序的放到”有序数组块中“,也就是20,60。</p>    <p>第三遍的时候同理,不同的是发现10比有序数组的值都小,因此20,60位置后移,腾出一个位置让10插入。</p>    <p>然后按照这种规律就可以全部插入完毕。</p>    <p>下面是一张gif图</p>    <p><img src="https://simg.open-open.com/show/0ddc9dcd070302d9e1242f0f480dbf53.gif"></p>    <p><strong>特点:</strong></p>    <p>插入算法把要排序的数组分成两部分:</p>    <p>第一部分包含了这个数组的所有元素,但将第一个元素除外(让数组多一个空间才有插入的位置).</p>    <p>第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中</p>    <p>比冒泡排序快一点</p>    <p><strong>代码实现</strong>:</p>    <pre>  <code class="language-javascript">//插入排序  //假定当前元素之前的元素已经排好序,先把自己的位置空出来,  //然后前面比自己大的元素依次向后移,直到空出一个"坑",  //然后把目标元素插入"坑"中  function insertSort(arr){      // 从第二个元素开始,因为要留出一个坑      for(var i=1;i<arr.length;i++){          var x=arr[i];           for(var j=i-1;arr[j]>x;j--){  //后挪空出位置 .              arr[j+1]=arr[j];          }          if(arr[j+1]!=x){              arr[j+1]=x;          }      }      return arr;  }  var arr=[2,3,6,4,2,1,90,100,20,5];  console.log(insertSort(arr,2)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>希尔排序</strong></h2>    <p><strong>原理:</strong></p>    <p><strong>   </strong> 希尔排序也叫 <strong>递减增量排序算法</strong> ,是插入排序的一种神龟进化版。</p>    <p>什么叫递减增量呢,就是定义一个间隔序列,例如是5,3,1。第一次处理,会处理所有间隔为5的,</p>    <p>下一次会处理间隔为3的,最后一次处理间隔为1的元素。也就是相邻元素执行标准插入排序。</p>    <p>步骤如下:</p>    <p>1、先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。</p>    <p>2、所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序。</p>    <p>3、取第二个增量d2<d1重复上述的分组和排序,</p>    <p>4、直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/d6eb66889df7846162c25d39b50d0d7b.jpg"></p>    <p>这里增量的取法如下:</p>    <p>第一次增量的取法为: d=count/2;</p>    <p>第二次增量的取法为:  d=(count/2)/2;</p>    <p>最后一直到: d=1;</p>    <p>看上图观测的现象为:</p>    <p>d=3时:将40跟50比,因50大,不交换。</p>    <p>将20跟30比,因30大,不交换。</p>    <p>将80跟60比,因60小,交换。</p>    <p>d=2时:将40跟60比,不交换,拿60跟30比交换,此时交换后的30又比前面的40小,又要将40和30交换,如上图。</p>    <p>将20跟50比,不交换,继续将50跟80比,不交换。</p>    <p>d=1时:这时就是前面讲的插入排序了,不过此时的序列已经差不多有序了,所以给插入排序带来了很大的性能提高。</p>    <p><strong>特点:</strong></p>    <p>由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,</p>    <p>相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。</p>    <p>打个比方,我原来的数组是[5,4,3,2,1]的,这样一打乱就全部重新排了。</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">function shellSort(arr){      var gap=Math.floor(arr.length/2);      while(gap>0){          for(var i=gap;i<arr.length;i++){              temp=arr[i];              for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){                  arr[j]=arr[j-gap];              }              arr[j]=temp;          }          gap=Math.floor(gap/2);      }      return arr;  }  var arr = [2,3,6,4,2,1,90,100,20,5];  console.log(shellSort(arr));  //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>归并排序</strong></h2>    <p><strong>原理:</strong></p>    <p> 归并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。</p>    <p>有以下几个步骤:</p>    <p>1、把长度为n的输入序列分成两个长度为n/2的子序列;</p>    <p>2、对这两个子序列继续分为m/2的子序列,一直分下去</p>    <p>3、将两个排序好的子序列合并成一个最终的排序序列。</p>    <p><img src="https://simg.open-open.com/show/bc5212b7ff693be784265d779ce02c32.gif"></p>    <p>再来一张静态图,比较好理解</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/c4b735f32509411f32705de50d716e94.png"></p>    <p>这里需要补充是,归并中对数组的分割是从上往下的,归并中数组的比较是从下往上的。</p>    <p><strong>特点:</strong></p>    <p>速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列.</p>    <p>属于分治思想,递归归并</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">/* 排序并合并*/  function merge(left, right) {     var re = [];     while(left.length > 0 && right.length > 0) {         if(left[0] < right[0]) {                          // 如果左边的数据小于右边的数据,将左边的数据取出,放到新数组那里             re.push(left.shift());         } else {             re.push(right.shift());         }     }     /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */     return re.concat(left).concat(right);  }     function mergeSort(arr) {     if(arr.length == 1){        return arr;     }     /* 首先将无序数组划分为两个数组 */     var mid = Math.floor(arr.length / 2);     var left = arr.slice(0, mid);     var right = arr.slice(mid);     /* 递归分别对左右两部分数组进行排序合并 */     return merge(mergeSort(left), mergeSort(right));  }    var arr=[2,3,6,4,2,1,90,100,20,5];  console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>快速排序</strong></h2>    <p><strong>原理:</strong></p>    <p>1、在数据集之中,选择一个元素作为"基准"(pivot)。比如选择下面数字45</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/f8f8be1d3f364e2084764491522a4da9.png"></p>    <p>2、所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/697a99bc57165854870e5f708293050c.png"></p>    <p>3、对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/d4e5d0a778dba725091d8317e6bac939.gif"></p>    <p>特点:速度 <strong>最快</strong> 。和归并排序不同的是,归并排序是先分为两组再继续排,而快速排序是边分边排</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">// 大致分三步:      // 1、找基准(一般是以中间项为基准)      // 2、遍历数组,小于基准的放在left,大于基准的放在right      // 3、递归      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=[];          var 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));      }      var arr=[2,3,6,4,2,1,90,100,20,5];      console.log(quickSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>选择排序</strong></h2>    <p>原理:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后剩下的数当中找出最小的与第二个位置的数交换,如此循环直到倒数第二个数和最后一个数为止。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/2bdd6b162c403d376c56c02e8a5560af.gif"></p>    <p>静态图:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/db6d23e1ab1b146d81ec73c60d6566f6.jpg"></p>    <p><strong>特点:</strong>可以说是冒泡排序的衍生品,效率比较一般般</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">// 在无序区中选出最小的元素,然后将它和无序区的第一个元素交换位置。  function selectSort(arr){     length = arr.length;     for (var i = 0; i < length; i++){   // 循环数组          var _min = arr[i];       // 把每一次的 数组里面的数字记录下来          var k = i;                  // 记录下来索引          for (var j = i + 1; j < length; j++){   // 当前的数字与后一个数字相比较             if (_min > arr[j]){   //当前的数 大于 后面一个数的话                 _min = arr[j];    //  就讲后面 的数值 保存下来                 k = j;             /// 保存索引             }         }         arr[k] = arr[i];   // 进行交换位置         arr[i] = _min;     }     return arr;  }       var arr=[2,3,6,4,2,1,90,100,20,5];  console.log(selectSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>奇偶排序</strong></h2>    <p><strong>原理:</strong></p>    <p>选取所有奇数列的元素与其 <strong>右侧</strong> 相邻的元素进行比较,将较小的元素排序在前面;</p>    <p>选取所有偶数列的元素与其 <strong>右侧</strong> 相邻的元素进行比较,将较小的元素排序在前面;</p>    <p>重复前面两步,直到所有序列有序为止。</p>    <p>如下图所示:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/2b416d6518ef2a5daf31572516bc8cf1.png"></p>    <p>gif图:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/3b5f51d11d0a086d88fb7fc54970a56f.gif"></p>    <p><strong>特点:</strong>奇数和偶数序列交替比较</p>    <p><strong>代码实现:</strong></p>    <pre>  <code class="language-javascript">function oddEvenSort(arr){      //swaped用来控制循环是否要继续,如果左边的都比右边的小,则退出循环,返回排好的数组      var swaped=true;        var k=0;      while(swaped){          if(k>0){              swaped=false;            }          for(var i=k;i<arr.length-1;i+=2){              if(arr[i]>arr[i+1]){                  // 如果左边的数字比右边的大,两者交换位置                  arr[i]=[ arr[i+1], arr[i+1]=arr[i] ][0];                    swaped=true;              }            }          k=[1,0][k]; //奇数和偶数之间的转行      }      return arr;  }       var arr=[2,3,6,4,2,1,90,100,20,5];  console.log(oddEvenSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]  </code></pre>    <h2><strong>总结</strong></h2>    <p>本文只是总结了算法中的一部分,算法的精髓就在于他们的思想,在js中用处应该不是很大。如果第一遍看不太懂那些代码,可以试着自己敲一遍,我在总结的时候,遇到理解不了的代码,自己敲完理解程度就会加深一些。</p>    <p>理解完,确实这些算法的实现思想博大精深,不得不感慨一下前辈们思想的深度。</p>    <p> </p>    <p>来自:http://www.cnblogs.com/xianyulaodi/p/6001122.html</p>    <p> </p>