Java 中的计数排序

2025年5月12日 | 阅读 5 分钟

计数排序是 Java 中最常用的排序技术之一，它基于给定范围内的键进行排序。计数排序不通过比较元素来排序，而是通过计算具有不同键值的对象的数量来实现排序，类似于哈希。之后，它会执行一些算术运算来计算每个对象在输出序列中的索引位置。计数排序算法不被用作通用排序算法。

假设我们有一个输入数组 a{4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5}，其值在范围 [0, 5] 内。

我们计算数组中每个元素的出现次数，并将计数表示为数组 countArray。countArray[i] 表示数字 i 在数组 a 中的出现次数。

因此，数字 0 和 1 各出现一次，2、3 和 4 各出现两次，5 出现三次。

现在，借助 countArray，我们确定数组 a 中有多少个元素小于或等于 countArray 的每个元素。我们将小于或等于 countArray[i] 的所有元素相加。

在数组 a 中，

只有一个元素，即 0，小于或等于零，这等于 countArray[0]。
有两个元素小于或等于 1，即 0 和 1，这等于 countArray[0] + countArray[1]。
有 4 个值小于或等于 2，即 0、1、2 和 2，这等于 countArray[0]+ countArray[1]+ countArray[2]。
有 6 个值小于或等于 3，即 0、1、2、2、3、3，这等于 countArray[0]+ countArray[1]+ countArray[2] ]+ countArray[3]。
有 6 个值小于或等于 3，即 0、1、2、2、3、3，这等于 countArray[0]+ countArray[1]+ countArray[2] ]+ countArray[3]。
有 6 个值小于或等于 4，即 0、1、2、2、3、3、4、4，这等于 countArray[0]+ countArray[1]+ countArray[2] ]+ countArray[3] + countArray[4]。
有 6 个值小于或等于 5，即 0、1、2、2、3、3、4、4、5、5、5，这等于 countArray[0]+ countArray[1]+ countArray[2] ]+ countArray[3] + countArray[4] + countArray[5]。

算法

在获得辅助数组，即 countArray 后，我们进行排序以对数组 a 进行排序。以下是排序数组 a 元素的步骤。

以反向形式遍历输入数组 'a'。
对于输入数组中的每个元素 'i'，C[i] 定义了数字 i 在排序数组中的位置，因为有 countArray[i] 个元素小于或等于 i。
在每轮结束时，我们将 countArray[i] 减一。

因此，为了对输入数组 a 进行排序，我们反向遍历它，并从数字 5 开始。在 countArray 的索引 5 处，值为 11，这意味着数组 'a' 包含 11 个小于或等于数字 5 的元素。这意味着 5 将是排序数组中的最后一个元素。

在将数字 5 移动到排序数组后，我们将 countArray[5] 的值减一。现在，反向顺序中的下一个数字是 2，在索引 2 处，值为 4，这意味着数组 'a' 包含四个小于或等于 2 的元素。因此，该数字将在排序数组中的第 4 个位置。

输入数组 'a' 中的下一个数字是 0，countArray 中索引 0 的值为 1，这意味着输入数组 'a' 中只有一个元素等于 0。因此，0 将是排序数组中的第一个元素。

我们对输入数组 'a' 的其余元素执行相同的操作。

对于元素 1

对于元素 5

对于元素 3

对于元素 4

对于元素 5

对于元素 2

对于元素 3

对于元素 4

排序数组

让我们使用上面讨论的算法在 Java 中实现计数排序的逻辑。

CountingSortExample.java

// import required classes and packages
package javaTpoint.MicrosoftJava;

import java.util.Scanner;

// create class CountingSortExample to sort an array of elements using counting sort
class CountingSortExample {
	
	// create sortArray() method that sort the given array using counting sort mechanism
	public static void sortArray(int inputArr[])
	{
		// calculate size of the array
		int size = inputArr.length;

		// create another array having same length of inputArr that will store elements in sorted way
		int sortedArr[] = new int[size];

		// Create countArr that will store count of occurrence of each number and initialize it with 0
		int countArr[] = new int[256];
		for (int i = 0; i < 256; ++i) {
			countArr[i] = 0;
		}

		// use for loop to store the count of each number in the countArr
		for (int i = 0; i < size; ++i)
			++countArr[inputArr[i]];

		// modify the value of countArr[i] so that countArr[i] now contains actual position of the current number in the sortedArr
		for (int i = 1; i <= 255; ++i)
			countArr[i] += countArr[i - 1];

		// iterate the inputArr in reverse order to perform counting sort.
		for (int i = size - 1; i >= 0; i--) {
			sortedArr[countArr[inputArr[i]] - 1] = inputArr[i];
			--countArr[inputArr[i]];
		}
		// Copy the sortedArr to inputArr, so that inputArr now contains sorted elements
		for (int i = 0; i < size; ++i)
			inputArr[i] = sortedArr[i];
		
		// print sorted array elements
		System.out.print("Sorted numbers in the array is:");
		for (int i = 0; i < inputArr.length; ++i)
			System.out.print(inputArr[i]);
	}
	// main() method start
	public static void main(String args[])
	{
		
		int size;  
		
		Scanner sc = new Scanner(System.in);  
		System.out.print("Enter the number of elements you want to store in the array: ");  
		
		//reading the number of elements from the that we want to enter  
		size = sc.nextInt();  
		
		//creates an array of the user input size  
		int[] inputArr = new int[size];  
		System.out.println("Enter the elements in the array: ");  
		for(int i=0; i<size; i++)  
		{  
			//reading array elements from the user   
			inputArr[i] = sc.nextInt();  
		}  
		// close scanner class object
		sc.close();
		sortArray(inputArr);
		
	}
}

输出

下一主题Position-of-rightmost-different-bit-in-java

Java 中的计数排序

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的计数排序

算法

相关帖子

How to Call a Method in Java

Stern-Brocot Sequence in Java

Java 中的字符串处理

Java 中使用多线程进行快速排序

Java 中的先决条件

Java 中的数字补码问题

Pell Number in Java

Java 中按对角线打印矩阵

Max Product of Tree in Java

Form Minimum Number from Given Sequence in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器