O (n) 의 정렬 알고리즘 - (계수 정렬, 통 정렬 및 js 구현)

function countSort(nums) {
    if (nums.length <= 1) return;

    let max = nums[0];
    let min = nums[0];
    for (let i = 1; i < nums.length; i++) {
        max = nums[i] <= max ? max : nums[i];
        min = nums[i] >= min ? min : nums[i];
    }

    //      
    let offset = 0 - min;

    //        
    let count = new Array(max - min + 1);
    for (let i = 0; i < count.length; i++) count[i] = 0;

    //   ：         
    for (let i = 0; i < nums.length; i++) {
        count[nums[i] + offset]++;
    }

    //       
    let index = 0;
    for (let i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            nums[index] = i - offset;
            index++;
            count[i]--;
        }
    }
}

                ，       getBucketIndex  ，                 ；
       ，            ，                  
          ，      ，             ，        ，          
         ，         ，      ，           ，             

//     ，         
function ListNode(val) {
    this.val = val;
    this.next = null;
}

// nums    ，     ，     [0,10]   
// len：    
function bucketSort(nums, len) {
    console.log(nums, len);
    if (nums.length <= 1) return;

    let bucket = [];
    for (let i = 0; i < len; i++) {
        bucket[i] = new ListNode(0);
    }

    //       
    for (const num of nums) {
        //            
        let idx = getBucketIndex(num);
        let insertNode = new ListNode(num);
        if (bucket[idx].next == null) {
            //    ，    
            bucket[idx].next = insertNode;
        } else {
            //    ，        
            let pre = bucket[idx];
            let cur = pre.next;
            while (cur != null && cur.val <= num) {
                pre = cur;
                cur = cur.next;
            }

            insertNode.next = cur;
            pre.next = insertNode;
        }
    }

    //       
    let index = 0;
    for (let i = 0; i < len; i++) {
        let node = bucket[i].next;
        if (node == null) continue;
        while (node != null) {
            nums[index] = node.val;
            index++;
            node = node.next;
        }
    }
}


//         
//      ，        ，       ，             
function getBucketIndex(num) {
    return parseInt(num);
}

let array = [2.18, 0.18, 0.16, 2.12, 3.66, 7.88, 7.99, 8.12, 9.66, 5.1, 4.12, 5.28];
bucketSort(array, 11);
console.log(array);