Quicksort, heapsort and other O(nlogn) time complexity algorithms are fast, but there are actually faster sorting algorithms, and ideally, some of them can even achieve linear time complexity, such as counting sort, bucket sort, radix sort

For example, bubble sort, heap sort, and quicksort are all sorted based on comparison between elements, but in counting sort, this sorting algorithm determines the position of elements based on the subscript of the elements

First knowledge count sort

Suppose there are 20 random integers in the array, ranging from 0 to 10,

1. According to this limited range, we can create a statistical array of length 11, with subscripts ranging from 0 to 10, and all elements with initial values of 0

2. Iterate over the unordered array of random numbers, incrementing each integer by its subscript element

3. Iterate over the statistics array, whose subscript represents the element in the unordered random number group, and whose value represents the number of occurrences of the element

The code is as follows:

function countSort(arr: Array<number>):Array<number> { // 1. Let Max = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } } // 2. Let countArray = (new Array(Max + 1)).fill(0); For (let index = 0; index < arr.length; Index ++) {countArray[arr[index]]++} let sortedArray = new Array(); for (let index = 0; index <= countArray.length; index++) { for (let j = 0; j < countArray[index]; j++) { sortedArray.push(index) } } return sortedArray } function main() { let arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10]; console.log(countSort(arr)) } main()Copy the code

Optimization of 1

Problem: It is not precise to determine the length of a sequence only by the maximum value, such as the following sequence:

95, 94, 91, 98, 99, 90, 99, 93, 91, 92

The maximum value is 99, and the minimum value is 90. If you create an array of length 100, then all space positions from 0 to 89 are wasted

The minimum value of the column is used as an offset to calculate the subscript of the integer in the statistical array

The code is as follows:

function countSort(arr: Array<number>) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index < arr.length; index++) { countArray[arr[index] - min]++ } // 4. Let sortedArray = [] for (let index = 0; index < countArray.length; index++) { for (let j = 0; j < countArray[index]; j++) { sortedArray.push(index + min) } } return sortedArray } function main() { let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92]; console.log(countSort(arr)) } main()Copy the code

Optimization of 2

This is fine if you’re just sorting integers, but in real business, such as sorting students’ test scores, it’s hard to tell which is which when the same scores come in

Here’s an example:

If the scores are the same, the order of the original table will be followed. Then when we fill in the statistical array, we only know that there are two students with the same score of 95, but we don’t know which one is little red and which is little green

Solutions:

1. First, transform the statistical array as follows:

You do this by starting with the second element in the array and adding each element to the sum of the preceding elements

This is done so that the value of the element stored in the statistics array is equal to the final sequence number of the corresponding integer

2. Create a sortedArray array with the same length as the input array, and iterate through the input array from back to front.

Go through the result of the last little green, whose score is 95, and find the element with subindex 5, whose value is 4, which means that the result of little green ranks the fourth. At the same time, reduce the value of the element marked 5 in the statistical array from 4 to 3, which means that the result of 95 will rank the third next time.

Go through the second-last place in the score table, xiao Bai’s score is 94, find the element with subscript 4 in the statistical array, and the value is 2, indicating that Xiao Bai’s score is ranked second. Meanwhile, the element with subscript 4 in the statistical array is reduced by 1, from 2 to 1, indicating that the next time we meet the element with 94 score, it will be ranked first (it has actually failed to meet it).

After traversing the result table, the result of Xiaohong is the third from the bottom. The operation is the same as above, ranking the third. The value of the element with subscript 5 in the statistical array is reduced by 1

In this way, students with the same score can be sorted in the same order, which is why the optimized version of counting sort is stable

The code is as follows:

function countSort(arr: Array<number>) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index < arr.length; index++) { countArray[arr[index] - min]++ } // 4. For (let index = 1; index < countArray.length; index++) { countArray[index] += countArray[index - 1] } // 5. Let sortedArray = new Array(arr.length); for (let index = arr.length - 1; index >= 0; SortedArray [countArray[arr[index] -min] -1] = arr[index] countArray[arr[index]  - min]-- } return sortedArray } function main() { let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92]; console.log(countSort(arr)) } main()Copy the code

summary

Complexity:

If the size of the original sequence is N and the difference between the largest and smallest integers is m,

The total amount of computation is 3n + m, and the time complexity is O(n + m).

Space complexity: If the output array is not considered and only the statistics array is considered, the space complexity is O(m).

Limitations:

1. When the difference between the minimum value and the maximum value of a sequence is too large, counting sort is not suitable

2. Counting sort is also not appropriate when the sequence elements are not integers

Summary from: the journey of cartoon algorithm xiao Grey algorithm