/**
? ? * 基數(shù)排序 O(d(n+radix))
? ? * radix 基數(shù) d為堆數(shù)
? ? *
? ? * @param {any} arr
? ? * @param {any} radix 基數(shù)
? ? * @returns
? ? *
? ? * @memberof sort
? ? */
? ? sort8(arr, radix) {
? ? ? ? let max = this.findMax(arr, radix); // 找出堆數(shù)
? ? ? ? console.log(max);
? ? ? ? for(let i = 1;i <= max;i++) {
? ? ? ? ? ? this.buildBy(arr, i, radix);
? ? ? ? }
? ? ? ? return arr;
? ? }
? ? /**
? ? * 找出堆數(shù)
? ? *
? ? * @param {any} arr
? ? * @param {any} radix 基數(shù)
? ? * @returns 堆數(shù)
? ? *
? ? * @memberof sort
? ? */
? ? findMax(arr, radix) {
? ? ? ? let max = 1;
? ? ? ? let len = arr.length;
? ? ? ? for (let i = 0; i < len;i++) {
? ? ? ? ? ? while(Math.floor(arr[i] / (radix** (max- 1))) > 1) {
? ? ? ? ? ? ? ? max++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return max;
? ? }
? ? /**
? ? * 分桶排序
? ? *
? ? * @param {any} arr
? ? * @param {any} index 當(dāng)前桶
? ? * @param {any} radix 基數(shù)
? ? *
? ? * @memberof sort
? ? */
? ? buildBy(arr, index, radix) {
? ? ? ? let bockets = new Array(radix);
? ? ? ? for (let i = 0;i < radix;i++) {
? ? ? ? ? ? bockets[i] = [];
? ? ? ? }
? ? ? ? for (let i = 0;i < arr.length;i++) {
? ? ? ? ? ? let remainder = Math.floor(arr[i] / (radix ** (index - 1))) % radix;
? ? ? ? ? ? bockets[remainder].push(arr[i]);
? ? ? ? }
? ? ? ? var temp = 0;
? ? ? ? for (let i = 0;i < bockets.length;i++) {
? ? ? ? ? ? for (let j = 0;j< bockets[i].length;j++) {
? ? ? ? ? ? ? ? arr[temp] = bockets[i][j];
? ? ? ? ? ? ? ? temp++
? ? ? ? ? ? }
? ? ? ? }
? ? }
