计数排序,桶排序与基数排序

HecMattner 2年前
   <p>一般算法能做到O(logn),已经非常不错,如果我们排序的对象是纯数字,还可以做到惊人的O(n)。涉及的算法有计数排序、基数排序、桶排序,它们被归类为非比较排序。</p>    <p>非比较排序只要确定每个元素之前的已有的元素个数即可,遍历一次就能求解。算法时间复杂度O(n)。</p>    <p>非比较排序时间复杂度低,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。</p>    <h2>计数排序</h2>    <p>计数排序需要占用大量空间,它仅适用于数据比较集中的情况。比如 [0~100],[10000~19999] 这样的数据。</p>    <p>我们看一下计数排序是怎么运作,假设我们有[1,2,3,1,0,4]这六个数,这里面最大的值为4,那么我们创建一个长度为4的数组,每个元素默认为0。这相当于选举排序,一共有6个投票箱,1就投1号箱,0就投入0号箱。注意,这些箱本来就是已经排好序,并且箱的编号就是代表原数组的元素。当全部投完时,0号箱有1个,1号箱有2个,2号箱有1个,3号箱有1,4号箱有1个。然后我们从这些箱的所有数依次出来,放到新数组,就神奇地排好序了。</p>    <p>计数排序没有对元素进行比较,只是利用了箱与元素的一一对应关系,根据箱已经排好序的先决条件,解决排序。</p>    <pre>  //by 司徒正美  function countSort(arr){     var max = Math.max.apply(0, arr);     var buckets = []     for(var i = 0; i < n; i++){        var el = arr[i]        if(buckets[el]){//子桶里不实际存在           buckets[el]++         }else{           buckets[el] = 1        }     }     var index = 0     for(var i = 0; i < n; i++){         var m = buckets[i].length;         while(m){            arr[index] = i;            index++            m--         }     }     return arr  }</pre>    <p>但数组有一个问题就是它的索引值是从0开始,但我们的元素也要大于或等于0。我们可以通过一个数学技巧让它支持负数。</p>    <pre>  //by 司徒正美  function countSort(arr){     var max = arr[0]     var min = arr[0]     for(var i = 0; i < n; i++){        if(arr[i] > max){           max = arr[i]        }        if(arr[i] < min){           max = arr[i]        }     }        var buckets = new Array(max-min+1).fill(0);     for(var i = 0; i < n; i++){        buckets[ arr[i]-min ]++     //减去最小值,确保索引大于负数     }     var index = 0, bucketCount = max-min+1     for(var i = 0; i < bucketCount; i++){         var m = buckets[i].length;         while(m){          //将桶的编号加上最小值,变回原来的元素          arr[index] = i+min;          index++          m--         }     }     return arr  }</pre>    <h2>桶排序</h2>    <p>桶排序与计数排序很相似,不过现在的桶不单计数,是实实在在地放入元素。举个例子,学校要对所有老师按年龄进行排序,这么多老师很难操作,那么先让他们按年龄段进行分组,20-30岁的一组,30-40岁一组,50-60岁一组,然后组内再排序。这样效率就大大提高了。桶排序也是于这种思想。</p>    <p>操作步骤:</p>    <ol>     <li>确认范围,亦即求取原数组的最大值与最小值。</li>     <li>确认需要多少个桶(这个通常作为参数传入,不能大于原数组长度),然后最大值减最小值,除以桶的数量,但得每个桶最多能放多个元素,我们称这个数为桶的最大容量。</li>     <li>遍历原数组的所有元素,除以这个最大容量,就能得到它要放入的桶的编号了。在放入时可以使用插入排序,也可以在合并时才使用快速排序。</li>     <li>对所有桶进行遍历,如果桶内的元素已经排好序,直接一个个取出来,放到结果数组就行了。</li>    </ol>    <pre>  //by 司徒正美  var arr = [2,5,3,0,2,8,0,3,4,3]     function bucketSort(array, num){      if(array.length <= 1){        return array      }      var n = array.length;      var min = Math.min.apply(0, array)      var max = Math.max.apply(0, array)      if(max === min){         return array      }      var capacity = (max - min + 1) /num;      var buckets = new Array(max - min + 1)      for(var i = 0; i < n; i++){        var el = array[i];//el可能是负数        var index = Math.floor((el - min) / capacity)        var bucket = buckets[index]        if(bucket){           var jn = bucket.length;           if(el >= bucket[jn-1]){              bucket[jn] = el           }else{              insertSort:               for(var j = 0; j < jn; j++){                  if(bucket[j] > el){                      while(jn > j){ //全部向后挪一位                          bucket[jn] = bucket[jn-1]                          jn--                      }                      bucket[j] = el //让el占据bucket[j]的位置                      break insertSort;                  }              }           }        }else{           buckets[index] = [el]        }      }      var index = 0      for(var i = 0; i < num; i++){          var bucket = buckets[i]          for(var k = 0, kn = bucket.length; k < kn; k++){              array[index++] = bucket[k]          }      }      return array;   }   console.log(  bucketSort(arr,4) )   //[ 0, 0, 2, 2, 3, 3, 3, 4, 5, 8 ]</pre>    <h2>基数排序</h2>    <p>基数排序是一种非比较型的整数排序算法。其基本原理是,按照整数的每个位数分组。在分组过程中,对于不足位的数据用0补位。</p>    <p>基数排序按照对位数分组的顺序的不同,可以分为LSD(Least significant digit)基数排序和MSD(Most significant digit)基数排序。</p>    <p>LSD基数排序,是按照从低位到高位的顺序进行分组排序。MSD基数排序,是按照从高位到低位的顺序进行分组排序。上述两种方式不仅仅是对位数分组顺序不同,其实现原理也是不同的。</p>    <h3>LSD基数排序</h3>    <p>对于序列中的每个整数的每一位都可以看成是一个桶,而该位上的数字就可以认为是这个桶的键值。比如下面数组</p>    <p>[170, 45, 75, 90, 802, 2, 24, 66]</p>    <p>首先我们要确认最大值,一个for循环得最大数,因为最大数的位数最长。</p>    <p>然后,建立10个桶,亦即10个数组。</p>    <p>然后再遍历所有元素,取其个位数,个位数是什么就放进对应编号的数组,1放进1号桶。</p>    <pre>  0号桶: 170,90   1号桶: 无   2号桶: 802,2   3号桶: 无   4号桶: 24   5号桶: 45, 75   6号桶: 66   7-9号桶: 无</pre>    <p>然后再依次将元素从桶里最出来,覆盖原数组,或放到一个新数组,我们把这个经过第一次排序的数组叫sorted。</p>    <p>sorted = [170,90,802,2,24,45,75,66]</p>    <p>然后我们再一次遍历sorted数组的元素,这次取十位的值。这时要注意,2不存在十位,那么默认为0</p>    <pre>  0号桶: 2,802   1号桶: 无   2号桶: 24   3号桶: 无   4号桶: 45   5号桶: 无   6号桶: 66   7号桶: 170, 75   8号桶: 无   9号桶: 90</pre>    <p>再全部取出来</p>    <p>sorted = [2,802,24,45,66,170,75,90]</p>    <p>开始百位上的入桶操作,没有百位就默认为0:</p>    <pre>  0号桶: 2,24,45,66,75,90   1号桶: 170   2-7号桶:无   8号桶: 802   9号桶: 无</pre>    <p>再全部取出来</p>    <p>sorted = [2,24,45,66,75,90,170,802]</p>    <p>没有千位数,那么循环结束,返回结果桶sorted</p>    <p>从程序描述如下:</p>    <p><img src="https://simg.open-open.com/show/28ad7499bbbc6ad55327ebbb51ba3238.png"></p>    <pre>  //by 司徒正美  function radixSort(array) {      var max = Math.max.apply(0, array);      var times = getLoopTimes(max),          len = array.length;      var buckets = [];      for (let i = 0; i < 10; i++) {          buckets[i] = []; //初始化10个桶      }      for (var radix = 1; radix <= times; radix++) {          //个位,十位,百位,千位这样循环          lsdRadixSort(array, buckets, len, radix);      }      return array;  }  // 根据数字某个位数上的值得到桶的编号  function getBucketNumer(num, d) {      return (num + "").reverse()[d];  }  //或者这个  function getBucketNumer(num, i) {      return Math.floor((num / Math.pow(10, i)) % 10);  }  //获取数字的位数  function getLoopTimes(num) {      var digits = 0;      do {          if (num > 1) {              digits++;          } else {              break;          }      } while ((num = num / 10));      return digits;  }  function lsdRadixSort(array, buckets, len, radix) {      //入桶      for (let i = 0; i < len; i++) {          let el = array[i];          let index = getBucketNumer(el, radix);          buckets[index].push(el);      }      var k = 0;      //重写原桶      for (let i = 0; i < 10; i++) {          let bucket = buckets[i];          for (let j = 0; j < bucket.length; j++) {              array[k++] = bucket[j];          }          bucket.length = 0;      }  }  // test  var arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];  console.log(radixSort(arr));</pre>    <h3>MSD基数排序</h3>    <p>接下来讲MSD基数排序.</p>    <p>最开始时也是遍历所有元素,取最大值,得到最大位数,建立10个桶。这时从百位取起。不足三位,对应位置为0.</p>    <pre>  0号桶: 45, 75, 90, 2, 24, 66   1号桶: 107   2-7号桶: 无   8号桶: 802   9号桶: 无</pre>    <p>接下来就与LSD不一样。我们对每个长度大于1的桶进行内部排序。内部排序也是用基数排序。我们需要建立另10个桶,对0号桶的元素进行入桶操作,这时比原来少一位,亦即十位。</p>    <pre>  0号桶: 2   1号桶: 无   2号桶: 24   3号桶: 无   4号桶: 45   5号桶: 无   6号桶: 66   7号桶: 75   8号桶: 无   9号桶: 90</pre>    <p>然后继续递归上一步,因此每个桶的长度,都没有超过1,于是开始0号桶的收集工作:</p>    <pre>  0号桶: 2,24,45,66,75,90   1号桶: 107   2-7号桶: 无   8号桶: 802   9号桶: 无</pre>    <p>将这步骤应用其他桶,最后就排序完毕。</p>    <pre>  //by 司徒正美  function radixSort(array) {      var max = Math.max.apply(0, array),          times = getLoopTimes(max),          len = array.length;      msdRadixSort(array, len, times);      return array;  }    //或者这个  function getBucketNumer(num, i) {      return Math.floor((num / Math.pow(10, i)) % 10);  }  //获取数字的位数  function getLoopTimes(num) {      var digits = 0;      do {          if (num > 1) {              digits++;          } else {              break;          }      } while ((num = num / 10));      return digits;  }  function msdRadixSort(array, len, radix) {      var buckets = [[], [], [], [], [], [], [], [], [], []];      //入桶      for (let i = 0; i < len; i++) {          let el = array[i];          let index = getBucketNumer(el, radix);          buckets[index].push(el);      }      //递归子桶      for (let i = 0; i < 10; i++) {          let el = buckets[i];          if (el.length > 1 && radix - 1) {              msdRadixSort(el, el.length, radix - 1);          }      }      var k = 0;      //重写原桶      for (let i = 0; i < 10; i++) {          let bucket = buckets[i];          for (let j = 0; j < bucket.length; j++) {              array[k++] = bucket[j];          }          bucket.length = 0;      }  }  var arr = radixSort([170, 45, 75, 90, 802, 2, 24, 66]);  console.log(arr);</pre>    <h3>字符串使用基数排序实现字典排序</h3>    <p>此外,基数排序不局限于数字,可以稍作变换,就能应用于字符串的字典排序中。我们先来一个简单的例子,只对都是小写字母的字符串数组进行排序。</p>    <p>小写字母一共26个,考虑到长度不一样的情况,我们需要对够短的字 符串进行补充,这时补上什么好呢?我们不直接被0,然后补空白。然后根据字母与数字的对应关系,弄27个桶,空字符串对应0,a对应1,b对应2.... 字典排序是从左边开始比较, 因此我们需要用到MST基数排序。</p>    <pre>  //by 司徒正美  var character = {};  "abcdefghijklmnopqrstuvwxyz".split("").forEach(function(el, i) {      character[el] = i + 1;  });  function toNum(c, length) {      var arr = [];      arr.c = c;      for (var i = 0; i < length; i++) {          arr[i] = character[c[i]] || 0;      }      return arr;  }  function getBucketNumer(arr, i) {      return arr[i];  }    function radixSort(array) {      var len = array.length;      var loopTimes = 0;        //求出最长的字符串,并得它的长度,那也是最高位      for (let i = 0; i < len; i++) {          let el = array[i];          var charLen = el.length;          if (charLen > loopTimes) {              loopTimes = charLen;          }      }        //将字符串转换为数字数组      var nums = [];      for (let i = 0; i < len; i++) {          nums.push(toNum(array[i], loopTimes));      }      //开始多关键字排序      msdRadixSort(nums, len, 0, loopTimes);      //变回字符串      for (let i = 0; i < len; i++) {          array[i] = nums[i].c;      }      return array;  }    function msdRadixSort(array, len, radix, radixs) {      var buckets = [];      for (var i = 0; i <= 26; i++) {          buckets[i] = [];      }      //入桶      for (let i = 0; i < len; i++) {          let el = array[i];          let index = getBucketNumer(el, radix);          buckets[index].push(el);      }      //递归子桶      for (let i = 0; i <= 26; i++) {          let el = buckets[i];          //el.c是用来识别是桶还是我们临时创建的数字字符串          if (el.length > 1 && !el.c && radix < radixs) {              msdRadixSort(el, el.length, radix + 1, radixs);          }      }      var k = 0;      //重写原桶      for (let i = 0; i <= 26; i++) {          let bucket = buckets[i];          for (let j = 0; j < bucket.length; j++) {              array[k++] = bucket[j];          }          bucket.length = 0;      }  }  var array = ["ac", "ee", "ef", "b", "z", "f", "ep", "gaaa", "azh", "az", "r"];    var a = radixSort(array);  console.log(a);</pre>    <h2>参考链接</h2>    <ul>     <li><a href="/misc/goto?guid=4959756576126055085" rel="nofollow,noindex">https://wenku.baidu.com/view/...</a> (PPT)</li>     <li><a href="/misc/goto?guid=4959756576207902728" rel="nofollow,noindex">https://www.cnblogs.com/kkun/...</a></li>     <li><a href="/misc/goto?guid=4959756576287269872" rel="nofollow,noindex">http://blog.csdn.net/ltyqljhw...</a></li>    </ul>    <p> </p>    <p>来自:https://segmentfault.com/a/1190000012923917</p>    <p> </p>