What is counting sort

Counting sort is a non-comparison sorting algorithm, which has the advantage of being faster than any comparison sorting algorithm when sorting integers in a certain range

Counting sort implementation diagram

directory

  • The first edition
  1. Train of thought
  2. Code implementation
  • The second edition
  1. Train of thought
  2. Code implementation

The first edition

Train of thought

Let’s say I have an array of five numbers that I need to sort

letArr =,6,3,8,1 [2];Copy the code

So what we think we’re going to get is definitely

let,2,3,6,8 arr = [1];Copy the code

So you have to sort it

So let me define an array that I want to sort

letArr =,6,3,8,1 [2];Copy the code

At this point, I would think, if I put all the data into an empty array index, and then output the index in turn, that would be sorted. In for a penny, in for a pound, in for a try.

letArr =,6,3,8,1 [2];let arr1 = new Array(10);
Copy the code

I’m going to define an array of length 10, and if I define an array this way, the value in the array is going to be undefined by default; Here’s what happens

//letArr =,6,3,8,1 [2]; //let arr1 = [undefined,undefined,undefined,undefined,undefined,undefined,undefined,undefined,undefined,undefined];
Copy the code

I now have 2,6,3,8,1 in the array, so I can enter a value in the corresponding index in arr1, that is, the evolution of the following

//letArr =,6,3,8,1 [2]; //letArr1 = [6,6,6, undefined undefined, 6, undefined, 6, undefined, undefined];Copy the code

Finally, I loop through the array in arr1 again, and if the array in arr1 has a value of =6, then the corresponding index is printed

Finish thinking, code implementation

    //1. Define the array to sort
    let arr = [2.6.3.8.1];
    //2. Define the array to accept the array to be sorted
    let arr1 = new Array(10);
    //3. Loop through the array to be sorted
    for (let i = 0; i < arr.length; i++) {
        //4. Loop through and insert into the new array
        arr1[arr[i]] = 6;
    }
    // console.log(arr1);
    //5. Iterate over the sorted array
    for (let i = 0; i < arr1.length; i++) {
        //6. Check whether the corresponding value in arr1 is equal to 6
        if(arr1[i] === 6) {console.log(i); / / 1,2,3,6,8}}Copy the code

Ok, it’s done, it’s done sorting, but there’s a couple of other things that are bad about doing it this way

  1. Restrict sorting only10Number. If you go beyond ten, you change the code
  2. Can only sort single data, no duplicate data (because there is only one index)

The second edition

In the second release, we want to improve the above three defects

Train of thought

  1. Restrict sorting only10Number. If you go beyond ten, you change the code
  2. Can only sort single data, no duplicate data (because there is only one index)
    / / the original
     let arr1 = new Array(10);
Copy the code

Make arr1’s array length equal to the length of the array to be sorted + 10 as the cardinality

/ / the improved
 let arr1 = new Array(arr.length + 10);
Copy the code
  1. Can only sort single data, no duplicate data (Because there’s only one index) Because of ourarr1Direct use is used6So, you index it once, you index it a second time, but it’s still the same6Well, that’s why he had to change the way he filled it out
/ / the original
for (let i = 0; i < arr.length; i++) {
       arr1[arr[i]] = 6;
}
Copy the code
/ / the improved
arr1.fill(0);           // Set all elements of the array to 0
for (let i = 0; i < arr.length; i++) {
       arr1[arr[i]] = arr1[arr[i]] + 1;
}
Copy the code

Appearance 1

let arr = [2.6.3.8.3];
// 0 12 3 4 5 6 7 8 9 10 11 12 13 14 Index number
let arr1 = [0.0.0.0.0.0.0.0.0.0.0.0.0.0.0]
Copy the code

When the cycle is over

let arr = [2.6.3.8.3];
// 0 12 3 4 5 6 7 8 9 10 11 12 13 14 Index number
let arr1 = [0.0.1.2.0.0.1.0.1.0.0.0.0.0.0]
Copy the code

And the ones that are repeated are going to be 2, so we can output according to the number

Finish thinking, code implementation

    //1. Define the array to sort
    let arr = [2.6.3.8.3];
    / / let arr =,5,8,7,2,3,5,1,7,2,3,5,7,6,8,9,2,1,3,5 [9];
    //2. Define the array to be sorted
    let arr1 = new Array(arr.length + 10);
    //3. Set arr1 to 0
    arr1.fill(0);
    //4. Loop through arR
    for (let i = 0; i < arr.length; i++) {
        + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
        arr1[arr[i]] = arr1[arr[i]] + 1;
        // 0 12 3 4 5 6 7 8 9 10 11 12 13 14 Index number
        //[0, 0, 1, 2, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
    }
    //6. Iterate over the sorted array
    //7. Define an array that accepts the return value
    let arr3 = [];
    for (let i = 0; i < arr1.length; i++) {
        //7. Iterate over the elements in the sorted array
        for (let j = 0; j < arr1[i]; j++) { arr3.push(i); }}console.log(arr3);      //[2, 3, 3, 6, 8]
Copy the code

Encapsulation method implementation:

    /** * @param arr accepts the array to be sorted * @param maxNum accepts the maximum value in the array */
    function countSort(arr, maxNum) {
        let arr1 = arr;
        let arr2 = new Array(maxNum);
        arr2.fill(0);
        for (let i = 0; i < arr1.length; i++) {
            arr2[arr1[i]]++;
        }
        let arr3 = [];
        for (let i = 0; i < arr2.length; i++) {
            for (let j = 0; j < arr2[i]; j++) { arr3.push(i); }}return arr3;
    }

    let arr = [1.5.7.2.2.5.4.9];
    let result = countSort(arr,9);
    console.log(result);    //[1, 2, 2, 4, 5, 5, 7]
Copy the code

Why don’t you check out my website?