How to implement counting sort algorithm using Python?

How to implement counting sorting algorithm using Python?

Counting sort is a linear time complexity sorting algorithm that can be used to sort integers or arrays with a certain value range. Its basic idea is to count the number of times each element appears and place the element in the correct position based on the number of times. The following will introduce how to use Python to implement the counting sorting algorithm and give specific code examples.

First of all, we need to clarify the core idea of ​​counting sorting. The execution steps of counting sorting are as follows:

1. Find the largest number in the array to be sorted, and create an auxiliary array count with a length of the maximum number plus 1 to store the number of occurrences of each element;
2. Traverse the array to be sorted, count the number of occurrences of each element, and store it in the count array;
3. Perform an accumulation operation on the count array to obtain the correct position index of each element;
4. Create a result array result with the same length as the array to be sorted;
5. Traverse the array to be sorted, and place the elements in the correct position according to the index of the element value in the count array;
6. Return the result array result, which is the sorted array.

The following is a code example for implementing the counting sort algorithm using Python:

def counting_sort(arr):
    # 找出最大值
    max_val = max(arr)
    # 创建辅助数组count，并初始化为0
    count = [0] * (max_val + 1)

    # 统计每个元素出现的次数
    for num in arr:
        count[num] += 1

    # 对count数组进行累加操作
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 创建结果数组result
    result = [0] * len(arr)

    # 将元素放置到正确的位置上
    for num in arr:
        index = count[num] - 1
        result[index] = num
        count[num] -= 1

    # 返回结果数组
    return result

Next, we can test the counting sort algorithm by:

arr = [4, 2, 3, 4, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Run the above Code, the output result is: [1, 2, 3, 4, 4].

Through the above code examples, we can see that the implementation steps of the counting sort algorithm are relatively simple. It is a very efficient sorting algorithm for arrays with a certain value range. I hope this article helps you understand and use the counting sort algorithm!

The above is the detailed content of How to implement counting sort algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!