# Algorithm: count sort

Catalog

One 、 sketch

Two 、 Algorithm ideas

3、 ... and 、 Graphic example

3.1 Overall process diagram ​ edit

3.2 Show the list to be sorted in columns ​ edit

3.3 Find the largest number in the list to be sorted , Construct a new array ： Cumulative count array , The contents of the array are all 0 【 The blue part 】, The length is ： The maximum value of the array to be sorted +1

3.4 On the count array , Count the array to be sorted , The number of times an element appears in 【 The blue part 】​ edit

3.5  Change the count array to the cumulative array 【 Determine its position in the sorted list 】

3.6 Sort the final results

Four , Code implementation

# One 、 sketch

Counting sort is not a sort algorithm based on comparison , Its core is to convert the input data value into a key and store it in the extra open array space . Sort as a linear time complexity , Counting sort requires that the data entered must be an integer with a defined range .

# Two 、 Algorithm ideas

• Find the largest and smallest elements in the array to be sorted ;
• Each value in the statistics array is i The number of times an element of , Save to array C Of the i term ;
• Add up all the counts （ from C The first element in begins , Add each item to the previous one ）;
• Reverse fill target array ： Put each element i Put it in the first... Of the new array C(i) term , Every time an element is placed, it will C(i) subtract 1

# 3、 ... and 、 Graphic example

### 3.3 Find the largest number in the list to be sorted , Construct a new array ： Cumulative count array , The contents of the array are all 0 【 The blue part 】, The length is ： The maximum value of the array to be sorted +1 ### 3.5  Change the count array to the cumulative array 【 Determine its position in the sorted list 】

The calculation method of the green part = Count array 1.2 The last number in the middle blue box + Cumulative array 2.1 The previous array in the middle green box

Such as ：6【 Cumulative array 2.1 The number in the green box in 】 = 2 【 Count array 1.2 The numbers in the blue box in the 】 +4 【 Cumulative figures 1.2 The number in the previous green box in the 】 ### 3.6 Sort the final results

1. Sort the original array , Take out the first one ：4  2. In the cumulative array 2.2 in ,4 Corresponding coordinate position 8, Its position in the final result list 7【 Because there is 0, need -1】
At the same time, the cumulative array corresponds to 4 The above reference count also requires -1, Updated to 7 3. Sort the original array , Take out the first one ：9,
In the cumulative array 2.2 in ,9 Corresponding coordinate position 14, Its position in the final result list 13【 Because there is 0, need -1】
At the same time, the cumulative array corresponds to 9 The above reference count also requires -1, Updated to 13 4. Repeat the above 3 The operation of , The termination can be sorted out # Four , Code implementation

``````listJ = [4, 48, 3, 50, 4, 47, 5, 48, 15, 46, 4, 47, 27, 36, 48]

def countimgSort(arr):
maxValue = max(arr)      # Find the maximum value of the table to be arranged
bucketLen = maxValue+1   # Find the number of lists in the count array
bucket = *bucketLen
arrLen=len(arr)
sortedIndex = 0

# Build cumulative array
for i in range(arrLen):
if not bucket[arr[i]]:  # Determine the subscript in the count array , The number in the corresponding original array does not exist , There is a reference count auto increment +1,
bucket[arr[i]] =0  # Not existing in the original number , Set as 0
bucket[arr[i]]+=1  # There is a reference count auto increment

# bucket = [0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 1]
# Write the final result
for j in range(bucketLen):
while bucket[j] >0:   # Accumulate in the array one by one , Traverse
arr[sortedIndex]=j  # In exchange for arr Middle number
sortedIndex+=1
bucket[j]-=1
print(arr)
return arr

print(countimgSort(listJ))
``````

https://cdmana.com/2022/174/202206231839325831.html

Scroll to Top