编程知识 cdmana.com

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.1 Overall process diagram
 

 3.2 Show the list to be sorted in columns

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 】

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 = [0]*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))

 

 

 
 

 

 

 

 

 

 

 

版权声明
本文为[Amae]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/174/202206231839325831.html

Scroll to Top