Skip to content

Commit ccbf1ec

Browse files
NinaWanNinaWan
committed
Add counting sort
1 parent 6a94a1b commit ccbf1ec

4 files changed

Lines changed: 136 additions & 14 deletions

File tree

‎src/main/java/sort/counting/CountingSort.java‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package sort.counting;
2+
3+
public class CountingSort {
4+
public void sort(int[] nums) {
5+
int min = nums[0], max = nums[0];
6+
for (int num : nums) {
7+
max = Math.max(max, num);
8+
min = Math.min(min, num);
9+
}
10+
11+
int[] count = new int[max - min + 1];
12+
for (int num : nums) {
13+
count[num - min]++;
14+
}
15+
16+
// // Unstable version
17+
// for (int i = 0, j = 0; j < count.length; j++) {
18+
// while (count[j] > 0) {
19+
// nums[i++] = j + min;
20+
// count[j]--;
21+
// }
22+
// }
23+
24+
// Stable version
25+
for (int i = 1; i < count.length; i++) {
26+
count[i] += count[i - 1];
27+
}
28+
29+
int n = nums.length;
30+
int[] sorted = new int[n];
31+
for (int i = n - 1; i >= 0; i--) {
32+
sorted[--count[nums[i] - min]] = nums[i];
33+
}
34+
35+
System.arraycopy(sorted, 0, nums, 0, n);
36+
}
37+
}

‎src/main/java/sort/counting/counting_sort.md‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# Counting Sort 计数排序
2+
3+
## 算法思想
4+
5+
计数排序算法是不基于比较的排序算法，是一种用空间换时间的算法。
6+
7+
主要思想是把待排序数据的数值转化为计数数组的下标，统计每个数值出现的次数，根据累加计数得出原数组中每个元素在排好序的数组中的位置。
8+
9+
计数排序算法需要额外的数组空间，且其大小与数据数值的范围大小k(i.e. max-min)有关。k的大小要在合理的范围内，否则会导致空间复杂度过大。
10+
11+
## 实现方法
12+
13+
1. 遍历待排序数组，找到最大值和最小值，确定计数数组的大小。
14+
2. 遍历待排序数组，统计每个数值出现的次数，记录在计数数组里。
15+
3. 遍历计数数组，计算累加计数。
16+
4. 根据累加计数，反向填充数组。
17+
18+
## 复杂度分析
19+
20+
### 假设
21+
22+
* 数组长度为n，数值范围为k
23+
24+
### 时间复杂度
25+
26+
由实现方法可知，计数排序算法的时间复杂度主要由四部分组成：
27+
28+
1. 遍历待排序数据寻找最大值和最小值的时间，为n
29+
2. 遍历待排序数组统计次数的时间，为n
30+
3. 遍历计数数组计算累加计数的时间，为k
31+
4. 根据累加计数反向填充数组的时间，为n
32+
33+
所以，算法的最终时间复杂度为O(n+k)
34+
35+
**最优时间复杂度**：O(n+k)
36+
37+
**最差时间复杂度**：O(n+k)
38+
39+
**平均时间复杂度**：O(n+k)
40+
41+
### 空间复杂度
42+
43+
需要额外的计数数组，空间复杂度为O(k)
44+
45+
需要额外的临时数组来进行反向填充，空间复杂度为O(n)
46+
47+
所以，算法的最终空间复杂度为O(n+k)
48+
49+
## 稳定性分析
50+
51+
计数排序算法是稳定的排序算法，反向填充保证了算法的稳定性，使得重复元素在排序前后的相对位置可以保持不变。但是也有不稳定的实现方式。
52+
53+
## 扩展/优化

‎src/main/java/sort/sort.md‎

Lines changed: 22 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,24 @@
1-
| | 算法 | 最优时间复杂度 | 最差时间复杂度 | 平均时间复杂度 | 稳定性 | 空间复杂度 |
2-
|----------------|---------|:------------------:|:------------------:|:--------------------:|:-----:|:----------------:|
3-
| Selection Sort | 选择排序 | O(n<sup>2</sup>) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 不稳定 | O(1) |
4-
| Bubble Sort | 冒泡排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 稳定 | O(1) |
5-
| Insertion Sort | 插入排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 稳定 | O(1) |
6-
| Shell Sort | 希尔排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>1.3</sup>) | 不稳定 | O(1) |
7-
| Merge Sort | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | O(n) |
8-
| Quick Sort | 快速排序 | O(nlogn) | O(n<sup>2</sup>) | O(nlogn) | 不稳定 | 最优O(logn)，最差O(n) |
9-
| Heap Sort | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | 不稳定 | O(1) |
10-
| Radix Sort | 基数排序 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | 稳定 | O(rd+n) |
11-
| Bucket Sort | 桶排序 | | | O(n+k) | | O(n+k) |
12-
| TimSort | TimSort | | | | | |
1+
## 排序算法比较表
132

14-
Note: 基数排序的时间复杂度中，r代表关键字的基数，d代表位数，n代表关键字的个数，也就是说基数排序不受待排序数组规模的影响。
3+
| | 算法 | 最优时间复杂度 | 最差时间复杂度 | 平均时间复杂度 | 稳定性 | 空间复杂度 |
4+
|----------------|---------|:----------------:|:----------------:|:------------------:|:---:|:----------------:|
5+
| Bubble Sort | 冒泡排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 稳定 | O(1) |
6+
| Counting Sort | 计数排序 | O(n+k) | O(n+k) | O(n+k) | | O(n+k) |
7+
| Heap Sort | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | 不稳定 | O(1) |
8+
| Insertion Sort | 插入排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 稳定 | O(1) |
9+
| Merge Sort | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | O(n) |
10+
| Quick Sort | 快速排序 | O(nlogn) | O(n<sup>2</sup>) | O(nlogn) | 不稳定 | 最优O(logn)，最差O(n) |
11+
| Selection Sort | 选择排序 | O(n<sup>2</sup>) | O(n<sup>2</sup>) | O(n<sup>2</sup>) | 不稳定 | O(1) |
12+
| Shell Sort | 希尔排序 | O(n) | O(n<sup>2</sup>) | O(n<sup>1.3</sup>) | 不稳定 | O(1) |
13+
| Radix Sort | 基数排序 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | 稳定 | O(rd+n) |
14+
| Bucket Sort | 桶排序 | | | O(n+k) | | O(n+k) |
15+
| TimSort | TimSort | | | | | |
1516

16-
稳定性：重复元素在排序前后，相对位置是否改变。
17+
Note:
18+
19+
1. 计数排序的时间复杂度中，k代表待排序数据的数值范围。
20+
2. 基数排序的时间复杂度中，r代表关键字的基数，d代表位数，n代表关键字的个数，也就是说基数排序不受待排序数组规模的影响。
21+
22+
稳定性：重复元素在排序前后，相对位置是否改变。
23+
24+
## 排序算法分类

‎src/test/java/sort/counting/CountingSortTest.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package sort.counting;
2+
3+
import org.junit.jupiter.api.BeforeEach;
4+
import org.junit.jupiter.api.Test;
5+
import sort.SortTest;
6+
7+
import java.util.Arrays;
8+
9+
import static org.junit.jupiter.api.Assertions.*;
10+
11+
class CountingSortTest extends SortTest {
12+
private CountingSort tested;
13+
14+
@BeforeEach
15+
void setUp() {
16+
tested = new CountingSort();
17+
}
18+
19+
@Test
20+
void testSort() {
21+
tested.sort(testData);
22+
assertArrayEquals(expected, testData);
23+
}
24+
}

0 commit comments

Comments
 (0)