如何使用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中文網其他相關文章！