如何使用java实现计数排序算法

如何使用Java实现计数排序算法

计数排序是一种非比较排序算法，其主要思想是通过统计每个元素在数组中出现的次数，然后根据元素出现的次数将其放置到正确的位置上。计数排序的时间复杂度为O(n+k)，其中n是待排序序列的长度，k是待排序序列中最大元素的范围。

在Java中，我们可以使用以下代码示例来实现计数排序算法：

public class CountingSort {
    public static void countingSort(int[] array) {
        int n = array.length;
        
        // 找到待排序序列中的最大值
        int max = array[0];
        for (int i = 1; i < n; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 创建一个计数数组，并初始化为0
        int[] count = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            count[i] = 0;
        }
        
        // 统计每个元素在待排序序列中出现的次数
        for (int i = 0; i < n; i++) {
            count[array[i]]++;
        }
        
        // 根据计数数组构建有序序列
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                array[index] = i;
                index++;
                count[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] array = {9, 1, 5, 3, 7, 3, 8, 2, 6};
        
        System.out.println("排序前：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        countingSort(array);
        
        System.out.println("排序后：");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

以上代码中，我们首先找到待排序序列中的最大值，然后创建一个计数数组，并将每个元素的出现次数统计在计数数组中。接着，我们根据计数数组构建有序序列，具体操作是将计数数组中的元素按照出现次数依次放置到待排序序列中。最后，通过调用countingSort方法并打印有序序列，我们就可以看到计数排序的结果。

需要注意的是，计数排序对于待排序序列中的元素范围有一定的限制，只适用于非负整数序列。如果待排序序列中存在负数或其他数据类型的元素，需要进行适当的处理才能使用计数排序算法。

以上是如何使用java实现计数排序算法的详细内容。更多信息请关注PHP中文网其他相关文章！