计数排序算法原理及应用

# 1. 引言

- 简介
- 目的

# 2. 计数排序算法概述

- **算法原理**
- **算法复杂度分析**

# 3. **计数排序算法实现**

计数排序算法的实现可以分为以下几个步骤：

### 3.1 伪代码解释

下面是计数排序算法的简单伪代码：

counting_sort(array, size)
  max = find_max(array, size)
  count_array = new Array[max+1]
  sorted_array = new Array[size]
  for i from 0 to max
    count_array[i] = 0
  for i from 0 to size
    count_array[array[i]] += 1
  for i from 1 to max
    count_array[i] += count_array[i-1]
  for i from size-1 down to 0
    sorted_array[count_array[array[i]]-1] = array[i]
    count_array[array[i]] -= 1
  return sorted_array

### 3.2 实际代码示例

下面是使用Python实现的计数排序算法的示例代码：

def counting_sort(arr):
    max_val = max(arr)
    count_array = [0] * (max_val + 1)
    sorted_array = [0] * len(arr)
    for num in arr:
        count_array[num] += 1
    for i in range(1, max_val + 1):
        count_array[i] += count_array[i - 1]
    for num in reversed(arr):
        sorted_array[count_array[num] - 1] = num
        count_array[num] -= 1
    return sorted_array

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)