JavaScript to achieve the ten common sorting algorithm library

  1 ;  2 (function (global, factory) {  3     // 兼容amd和cmd的写法  4     // 基本的新式是 cmd ? cmd : amd ? amd : global || window  5     typeof exports === ‘object‘ && typeof module !== ‘undefined‘ ? module.exports = factory() :  6         typeof define === ‘function‘ && define.amd ? define(factory) :  7         (global.PAS = factory());  8 })(this, (function () {  9     // 判断是否数组 10     function isArray(arr) { 11         return typeof Array.isArray === ‘function‘ ? 12             Array.isArray(arr) : 13             Object.prototype.toString.call(arr) === ‘[object Array]‘; 14     } 15  16     // 交换两个元素 17     function swap(v1, v2, context) { 18         [context[v1], context[v2]] = [context[v2], context[v1]]; 19         return void 0; 20     } 21  22     // 冒泡排序 23     function bubble(arr) { 24         let len = arr.length; 25         for (let i = 0; i < len; i++) { 26             for (let j = 0; j < len - 1 - i; j++) { 27                 if (arr[j] > arr[j + 1]) { 28                     swap(j, j + 1, arr) 29                 } 30             } 31         } 32         return arr; 33     } 34  35     // 插入排序 36     function insert(arr) { 37         let len = arr.length; 38         let pIndex, current; // 前一个元素的索引，当前元素的值 39         for (let i = 1; i < len; i++) { 40             pIndex = i - 1; 41             current = arr[i]; 42  43             // 依次把当前元素和前面的元素进行比较 44             while (pIndex >= 0 && arr[pIndex] > current) { 45                 // 比当前的元素大，向后移一位 46                 arr[pIndex + 1] = arr[pIndex]; 47                 pIndex--; 48             } 49             // 插入当前元素到合适的位置 50             arr[pIndex + 1] = current; 51         } 52         return arr; 53     } 54  55     // 快速排序 -- 这个方法不改变原数组 56     function quick(arr) { 57         let len = arr.length; 58  59         if (len < 2) { 60             return arr; 61         } 62  63         let middleIndex = Math.floor(len / 2); // 中间元素的索引值 64         let baseValue = http://www.mamicode.com/arr.splice(middleIndex, 1); // 基准值 65  66         let left = []; // 保存小于基准值元素 67         let right = []; // 保存大于或等于基准值元素 68  69         for (let i = 0; i < arr.length; i++) { 70             if (arr[i] < baseValue) { 71                 left.push(arr[i]); 72             } else { 73                 right.push(arr[i]); 74             } 75         } 76         return quick(left).concat(baseValue, quick(right)); 77     } 78  79     // 选择排序 80     function selection(arr) { 81         let len = arr.length; 82         let minIndex = 0; // 用于保存最小值的索引 83  84         for (let i = 0; i < len - 1; i++) { 85             minIndex = i; 86             // 遍历后面的元素和当前认为的最小值进行比较 87             for (let j = i + 1; j < len; j++) { 88                 if (arr[minIndex] > arr[j]) { 89                     // 比认为的最小值小 交换索引 90                     minIndex = j; 91                 } 92             } 93             // 找到最小值和当前值交换 94             if (minIndex !== i) { 95                 swap(minIndex, i, arr); 96             } 97         } 98         return arr; 99     }100 101     // 归并排序102     function merge(arr) {103         let len = arr.length;104         if (len < 2) {105             return arr;106         }107         let middleIndex = Math.floor(len / 2); // 获取中间元素的索引108         let left = arr.slice(0, middleIndex); // 获取左半部分的元素109         let right = arr.slice(middleIndex); // 获取右半部分的元素110 111         let merges = function (left, right) {112             // 保存结果的数组113             let result = [];114 115             while (left.length && right.length) {116                 if (left[0] < right[0]) {117                     result.push(left.shift())118                 } else {119                     result.push(right.shift())120                 }121             }122 123             // 如果左半边还有元素124             while (left.length) {125                 result.push(left.shift());126             }127 128             // 如果右半边还有元素129             while (right.length) {130                 result.push(right.shift());131             }132 133             return result;134         }135 136         return merges(merge(left), merge(right));137     }138 139     // 希尔排序140     function shell(arr) {141         let len = arr.length,142             temp,143             gap = 1;144 145         while (gap < len / 3) {146             gap = gap * 3 + 1;147         }148 149         for (gap; gap > 0; gap = Math.floor(gap / 3)) {150             for (let i = gap; i < len; i++) {151                 temp = arr[i];152                 for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {153                     arr[j + gap] = arr[j];154                 }155                 arr[j + gap] = temp;156             }157         }158         return arr;159     }160 161     // 堆排序162     function heap(arr) {163         let len = arr.length;164 165         let heapify = function (166             arr // 待排序的数组167             , x // 元素的下标168             , len // 数组的长度169         ) {170             let l = 2 * x + 1;171             let r = 2 * x + 2;172             let largest = x;173 174             if (l < len && arr[l] > arr[largest]) {175                 largest = l;176             }177 178             if (r < len && arr[r] > arr[largest]) {179                 largest = r;180             }181 182             if (largest !== x) {183                 swap(x, largest, arr);184                 heapify(arr, largest, len);185             }186         }187 188         for (let i = Math.floor(len / 2); i >= 0; i--) {189             heapify(arr, i, len);190         }191 192         for (let i = len - 1; i >= 1; i--) {193             swap(0, i, arr);194             heapify(arr, 0, --len);195         }196         return arr;197     }198 199     // 基数排序200     function radix(arr) {201         const SIZE = 10;202         let len = arr.length;203         let buckets = [];204         let max = Math.max.apply(null, arr); // 数组中的最大值205         let maxLength = String(max).length; // 最大数字的长度206 207         // 进行循环将桶中的数组填充成数组208         for (let i = 0; i < SIZE; i++) {209             buckets[i] = [];210         }211 212         // 进行循环--对数据进行操作--放桶的行为213         for (let i = 0; i < maxLength; i++) {214             // 第二轮循环是将数据按照个位数进行分类215             for (let j = 0; j < len; j++) {216                 let value =http://www.mamicode.com/ String(arr[j]);217                 // 判断长度--进行分类218                 if (value.length >= i + 1) {219                     let num = Number(value[value.length - 1 - i]); // 依次的从右到左获取各个数字220                     //放入对应的桶中221                     buckets[num].push(arr[j]);222                 } else {223                     // 长度不满足的时候，就放在第一个桶中224                     buckets[0].push(arr[i]);225                 }226             }227             // 将原数组清空228             arr.length = 0;229 230             //这次循环是依次取出上面分类好的数组存放到原数组中231             for (let j = 0; j < SIZE; j++) {232                 // 获取各个桶的长度233                 let l = buckets[j].length;234                 // 循环取出数据235                 for (let k = 0; k < l; k++) {236                     arr.push(buckets[j][k]);237                 }238                 // 将对应的桶清空，方便下次存放数据239                 buckets[j] = [];240             }241         }242         return arr;243     }244 245     // 桶排序 -- 不改变原数组246     function bucket(arr, size = 5) {247         let len = arr.length;248         if (len < 2) {249             return arr;250         }251 252         // 获取最大值和最小值253         const max = Math.max.apply(null, arr);254         const min = Math.min.apply(null, arr);255 256         // 计算出桶的数量  size是截距257         const bucketCount = Math.floor((max - min) / size) + 1;258         // 根据桶的个数创建指定长度的数组259         const buckets = new Array(bucketCount);260         // 将每个桶塞到大桶里面去261         for (let i = 0; i < bucketCount; i++) {262             buckets[i] = [];263         }264         // 利用映射函数将数据分配到各个桶里面去265         for (let i = 0; i < arr.length; i++) {266             // 逢size进1267             let index = Math.floor((arr[i] - min) / size);268             buckets[index].push(arr[i]);269         }270         //对每个桶中的数据进行排序--借助于快速排序算法271         for (let i = 0; i < buckets.length; i++) {272             buckets[i] = quick(buckets[i]);273         }274 275         // flatten数组--有点不足就是会将原数组中的String改变为Number276         return buckets.join(‘,‘).split(‘,‘).filter(v => v !== ‘‘).map(Number);277     }278 279     // 计数排序280     function count(arr) {281         let index = 0;282         let len = arr.length;283         let min = Math.min.apply(null, arr); // 最小值284         let max = Math.max.apply(null, arr); // 最大值285         let result = []; // 结果数组286 287         // 向新数组中填充0288         for (let i = min; i <= max; i++) {289             result[i] = 0;290         }291         // 把各个数组中对应的元素计数加一292         for (let i = 0; i < len; i++) {293             result[arr[i]]++;294         }295         // 按照计数的元素进行排序296         for (let i = min; i <= max; i++) {297             while (result[i]-- > 0) {298                 arr[index++] = i;299             }300         }301         return arr;302     }303 304     const PAS = {};305 306     [307         bubble,308         insert,309         quick,310         selection,311         merge,312         shell,313         heap,314         radix,315         bucket,316         count317     ].forEach(function (func) {318         let name = func.name;319         //增加层外包装，判断参数是不是数组320         Object.defineProperty(PAS, name, {321             get: function () {322                 return function (args) {323                     if (!isArray(args)) {324                         throw new Error(‘the arguments of PAS.‘ + name + ‘ must be Array‘);325                     }326                     return func.call(null, args);327                 }328             },329             configurable: true330         })331 332         // 在数组的原型上添加方法333         Object.defineProperty(Array.prototype, name, {334             get: function () {335                 var vm = this;336                 return function () {337                     return func.call(vm, vm);338                 }339             },340             configurable: true341         })342     })343 344     return PAS;345 }))