# andyRon/swift-algorithm-club-cn

Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.

# 计数排序(Counting Sort)

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key values, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

## 例子

### 第一步：

``````Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1
``````

```  let maxElement = array.max() ?? 0

var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
for element in array {
countArray[element] += 1
}```

### 第二步：

``````Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 2 3 3 3 3 5 6 7 8
``````

```  for index in 1 ..< countArray.count {
let sum = countArray[index] + countArray[index - 1]
countArray[index] = sum
}```

### 第三步

``````Index  0 1 2 3 4 5 6 7
Output 1 2 3 7 7 8 9 10
``````

```  var sortedArray = [Int](repeating: 0, count: array.count)
for element in array {
countArray[element] -= 1
sortedArray[countArray[element]] = element
}
return sortedArray```

# 翻译后补充

## 参考

https://www.jianshu.com/p/ff1797625d66