数据结构——排序算法——计数排序_计数排序时间复杂度

计数排序就是一种时间复杂度为 O(n) 的排序算法，该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时，它的复杂度为 O(n+k)（其中 k 是整数的范围大小）。

伪计数排序

我们需要对一列数组排序，这个数组中每个元素都是 [1,9] 区间内的整数。那么我们可以构建一个长度为 9 的数组用于计数，计数数组的下标分别对应区间内的 9 个整数。然后遍历待排序的数组，将区间内每个整数出现的次数统计到计数数组中对应下标的位置。最后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数。

void countingSort9(std::vector<int>& arr) {
	// Create an array of length 9, where indices 0-8 correspond to numbers 1-9
	//建立长度为 9 的数组，下标 0~8 对应数字 1~9
	std::vector<int> counting(9, 0);
	// Iterate through each element in the input array
	//建立长度为 9 的数组，下标 0~8 对应数字 1~9
	for (int element : arr) {
		// Count the occurrences of each integer and store them in the counting array
		//建立长度为 9 的数组，下标 0~8 对应数字 1~9
		counting[element - 1]++;
	}
	int index = 0;
	// Iterate through the counting array and output each element
	//遍历计数数组，将每个元素输出
	for (int i = 0; i < 9; i++) {
		// Output each element as many times as it appears in the input
		//遍历计数数组，将每个元素输出
		while (counting[i] != 0) {
			arr[index++] = i + 1;
			counting[i]--;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

算法非常简单，但这里的排序算法 并不是 真正的计数排序。因为现在的实现有一个非常大的弊端：排序完成后，arr 中记录的元素已经不再是最开始的那个元素了，他们只是值相等，但却不是同一个对象。

在纯数字排序中，这个弊端或许看起来无伤大雅，但在实际工作中，这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。

伪计数排序 2.0

对于这个问题，我们很容易想到一种解决方案：在统计元素出现的次数时，同时把真实的元素保存到列表中，输出时，从列表中取真实的元素。

void countingSort9(std::vector<int>& arr) {
	// Create an array of length 9, where indices 0-8 correspond to numbers 1-9
	// 建立长度为 9 的数组，下标 0~8 对应数字 1~9
	std::vector<int> counting(9, 0);
	// Record the actual elements at each index, using a queue to maintain stability
	//记录每个下标中包含的真实元素，使用队列可以保证排序的稳定性
	std::unordered_map<int, std::queue<int>> records;
	// Iterate through each element in the input array
	//遍历 arr 中的每个元素
	for (int element : arr) {
		// Count the occurrences of each integer and store them in the counting array
		// 将每个整数出现的次数统计到计数数组中对应下标的位置
		counting[element - 1]++;
		// Initialize a queue for each unique element if it doesn't exist
		//初始化每个唯一元素的队列（如果不纯在）
		if (records.find(element - 1) == records.end()) {
			records[element - 1] = std::queue<int>();
		}
		// Add the element to the corresponding queue
		//将元素添加到相应的队列
		records[element - 1].push(element);
	}
	int index = 0;
	// Iterate through the counting array and output each element
	// 遍历计数数组，将每个元素输出
	for (int i = 0; i < 9; i++) {
		// Output the element as many times as it appears in the input
		//输出的次数就是对应位置记录的次数
		while (counting[i] != 0) {
			// Output the actual element from the queue
			//输出的次数就是对应位置记录的次数
			arr[index++] = records[i].front();
			records[i].pop();
			counting[i]--;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

在这份代码中，我们通过队列来保存真实的元素，计数完成后，将队列中真实的元素赋到 arr 列表中，这就解决了信息丢失的问题，并且使用队列还可以保证排序算法的稳定性。

但是，这也不是 真正的计数排序，计数排序中使用了一种更巧妙的方法解决这个问题

真正的计数排序

举个例子，班上有
10 名同学：他们的考试成绩分别是：7,8,9,7,6,7,6,8,6,6，他们需要按照成绩从低到高坐到 0～9 共 10 个位置上。
用计数排序完成这一过程需要以下几步：
1.第一步仍然是计数，统计出: 4名同学考了 6 分，3名同学考了 7分，2名同学考了 8 分，1名同学考了9分;
2.然后从头遍历数组: 第一名同学考了7分，共有 4个人比他分数低，所以第一名同学坐在 4 号位置(也就是第5个位置)
3.第二名同学考了 8 分，共有 7 个人 (4 + 3) 比他分数低，所以第二名同学坐在 7 号位置;
4.第三名同学考了 9分，共有 9 个人 (4 + 3 + 2)比他分数低，所以第三名同学坐在 9 号位置；
5.第四名同学考了7分，共有 4 个人比他分数低，并且之前已经有一名考了 7分的同学坐在了 4 号位置，所以第四名同学坐在5号位置。
6…依次完成整个排序

区别就在于计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置

void countingSort(std::vector<int>& arr) {
	// Check for empty or single-element array
	//判空及防止数组越界
	if (arr.empty() || arr.size() <= 1) return;

	// Find the maximum and minimum values in the array
	//找到最大值，最小值
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > max) max = arr[i];
		else if (arr[i] < min) min = arr[i];
	}

	// Determine the counting array size
	//确定计数范围
	int range = max - min + 1;

	// Create a counting array of length 'range'
	//建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
	std::vector<int> counting(range, 0);

	// Iterate through the input array and count the occurrences of each element
	//遍历 arr 中的每个元素
	for (int element : arr) {
		// 将每个整数出现的次数统计到计数数组中对应下标的位置，这里需要将每个元素减去 min，才能映射到 0～range-1 范围内
		counting[element - min]++;
	}

	
	// Calculate the cumulative counts
	//记录前面比自己小的数字的总数
	int preCounts = 0;
	for (int i = 0; i < range; i++) {
		// 当前的数字比下一个数字小，累计到 preCounts 中
		preCounts += counting[i];
		// 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
		counting[i] = preCounts - counting[i];
	}

	// Create a result array
	std::vector<int> result(arr.size());

	// Place elements in the result array according to their counts
	for (int element : arr) {
		// counting[element - min] 表示此元素在结果数组中的下标
		result[counting[element - min]] = element;
		// 更新 counting[element - min]，指向此元素的下一个下标
		counting[element - min]++;
	}

	// Copy the sorted result back to the original array
	//将结果赋值返回arr
	for (int i = 0; i < arr.size(); i++) {
		arr[i] = result[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

倒序遍历的计数排序

void countingSort(std::vector<int>& arr) {
	// Check for empty or single-element array
	//判空及防止数组越界
	if (arr.empty() || arr.size() <= 1) return;

	// Find the maximum and minimum values in the array
	//找到最大值，最小值
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < arr.size(); i++) {
		if (arr[i] > max) max = arr[i];
		else if (arr[i] < min) min = arr[i];
	}

	// Determine the counting array size
	//确定计数范围
	int range = max - min + 1;

	// Create a counting array of length 'range'
	//建立长度为 range 的数组，下标 0~range-1 对应数字 min~max
	std::vector<int> counting(range, 0);

	// Iterate through the input array and count the occurrences of each element
	//遍历 arr 中的每个元素
	for (int element : arr) {
		// 将每个整数出现的次数统计到计数数组中对应下标的位置，这里需要将每个元素减去 min，才能映射到 0～range-1 范围内
		counting[element - min]++;
	}


	//每个元素在结果数组中的最后一个下标位置 = 前面比自己小的数字的总数 + 自己的数量 - 1。我们将 counting[0] 先减去 1，后续 counting 直接累加即可

	//记录前面比自己小的数字的总数
	counting[0]--;
	for (int i = 1; i < range; i++) {
		// 将 counting 计算成当前数字在结果中的最后一个下标位置。位置 = 前面比自己小的数字的总数 + 自己的数量 - 1
        // 由于 counting[0] 已经减了 1，所以后续的减 1 可以省略。
		counting[i] +=  counting[i-1];
	}

	// Create a result array
	std::vector<int> result(arr.size());


	// 从后往前遍历数组，通过 counting 中记录的下标位置，将 arr 中的元素放到 result 数组中
	for (int i = arr.size() - 1; i >= 0; i--) {
		// counting[arr[i] - min] 表示此元素在结果数组中的下标
		result[counting[arr[i] - min]] = arr[i];
		// 更新 counting[arr[i] - min]，指向此元素的前一个下标
		counting[arr[i] - min]--;
	}



	// Copy the sorted result back to the original array
	//将结果赋值返回arr
	for (int i = 0; i < arr.size(); i++) {
		arr[i] = result[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60