Prints the sorted array using counting sort, from smallest to largest, for the given array

Count sort: Count sort is a non-comparison based oneSorting algorithm. Its advantage is that it has the complexity of n+k (where K is the range of integers) when sorting integers in a certain range, which is faster than any comparison sorting algorithm. Of course, this is a way of sacrificing space for time, and when O(k)>O(n)Log (n)) is less efficient than comparison-based sorting (the theoretical lower bound of comparison-based sorting is O(n)Log (n)), such as merge sort, heap sort)

Technical sort is very similar to bucket sort. Its main implementation is to traverse the elements in the original array, take the elements in the original array as the index of the count array, and take the occurrence times of the elements in the original array as the element value of the count array. After traversal, the count array is traversed to find the element whose element value is greater than 0, and its corresponding index is filled into the result array as the element value. Each time, the value of the element in count is reduced by 1 until the element value is not greater than 0, and the remaining elements in count are processed in turn

Analysis:

Suppose we have a given array s = [3,2,6,4,5,3,7]

Each element in the array can be viewed as a ball. If the largest element in the array is 7, set 7 buckets. (If the largest element is 100, set 100 buckets.

7 buckets can be abstracted in code as an array of buckets, that is, an array of length 7. The number of balls in each bucket is the value of the elements in each array. The initial model would be: counstList = [0,0,0,0,0,0]

The ball is traversed and placed into the bucket with the corresponding index according to the number on the ball, for example: S [0] = 3, then the first ball is put into the third bucket. S [1] = 2, into the second bucket

Having done this, you may find that there are some problems with thinking this way:

  • Assuming s = [91,90,100] and the maximum is 100, we need to place 100 buckets
  • If s contains a negative number, for example s[0] = -1, which bucket should it put in? The first bucket?

A little further reflection shows that, assuming s = [91, 90, 100], we are really only sorting numbers > 90 and < 100. Buckets before 90 are not used at all, and no balls will be put in (because no data < 90). So the best way is that the first bucket should correspond to the smallest number in the array, that is, the first bucket should put 90, then we can get:

The first bucket should be 90

The second bucket should go into 91

The third bucket should be 92

The NTH bucket should be 90 + n-1.

The data that should be put into the NTH bucket = min + n-1

It can be concluded that N = the data put in -min + 1

If s = [-1, 3,5], s[0] = -1, then it should put [-1 – (-1) + 1], That is, in the first bucket, S [1] = 3, put into [3 – (-1) + 1], that is, the fifth bucket. And so on

Conclusion:

Assume that the minimum value in the array is min, the maximum value is Max, and the value of the individual elements of the array traversed is val

  • The length of the bucket should be max-min + 1
  • The number on the ball (val) should be put into the first val-min + 1 bucket

Thus, according to the array to be arranged, the following figure can be obtained:

Process:

  1. Min = 2, Max = 7 Set max-min + 1 = 7-2 + 1 = 6 buckets

2. Based on N = data, -min + 1

  • S [0] = 3, N = 3-2 + 1, put in the second bucket

  • S [1] = 2, N = 2-2 + 1, put in the first bucket

  • S [2] = 6, N = 6-2 + 1, into the fifth bucket

  • S [3] = 4, N = 4-2 + 1, put in the third bucket

  • S [4] = 5, N = 5-2 + 1, into the fourth bucket

  • S [5] = 3, N = 3-2 + 1, into the second bucket

  • S [6] = 7, N = 7-2 + 1, into the sixth bucket

The final result is:

Finally take out the data in the bucket in turn, the array is the sorted array

Code implementation:

Const f = () => {let min = s[0] let Max = s[0] i < s.length; i++) { let num = s[i] min = min > num ? num : min max = max < num ? num : max } console.log({ min, Const countList = new Array(max-min + 1).fill(0) s.foreach (num => {countList[num -) min] = countList[num - min] + 1 }) console.log(countList) const res = [] countList.forEach((val, index) => { while (val > 0) { res.push(index + min) val-- } }) console.log(res) } const s = [3, 2, 6, 4, 5, 3, 7] f(s)Copy the code

Output results: [2, 3, 3, 4, 5, 6, 7]