计数排序

系统管理员 2022-06-09 01:36 307阅读 0赞

对于一个int数组，请编写一个计数排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

# 测试样例：
    [1,2,3,5,2,3],6
    [1,2,2,3,3,5]

我的提交

# -*- coding:utf-8 -*-
    
    class CountingSort:
        def countingSort(self, A, n):
            # write code here
            seta = set(A)
            minnum = min(seta)
            maxnum = max(seta)
            buckets = {}
            for i in range(minnum, maxnum+1):
                buckets[i] = 0
    
            for num in range(n):
                buckets[A[num]] = buckets[A[num]] + 1
    
            B = []
            for j in range(minnum, maxnum+1):
                B.extend([j] * buckets[j])
            return B
    
    if __name__ == '__main__':
        c = CountingSort()
        print(c.countingSort([54,35,48,36,27,12,44,44,8,14,26,17,28],13))

调整一下，减少空间消耗

# -*- coding:utf-8 -*-
    
    class CountingSort:
        def countingSort(self, A, n):
            # write code here
            seta = set(A)
            minnum = min(seta)
            maxnum = max(seta)
            buckets = {}
            for i in range(minnum, maxnum+1):
                buckets[i] = 0
    
            for num in range(n):
                buckets[A[num]] = buckets[A[num]] + 1
    
            i = 0
            for j in range(minnum, maxnum+1):
                for _ in range(buckets[j]):
                    A[i] = j
                    i += 1
            return A
    
    if __name__ == '__main__':
        c = CountingSort()
        print(c.countingSort([54,35,48,36,27,12,44,44,8,14,26,17,28],13))

**参考答案**

public class CountSort { 
    
        public static void countSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            int min = arr[0];
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) {
                min = Math.min(arr[i], min);
                max = Math.max(arr[i], max);
            }
            int[] countArr = new int[max - min + 1];
            for (int i = 0; i < arr.length; i++) {
                countArr[arr[i] - min]++;
            }
            int index = 0;
            for (int i = 0; i < countArr.length; i++) {
                while (countArr[i]-- > 0) {
                    arr[index++] = i + min;
                }
            }
        }
    
        public static void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
    
        public static int[] generateArray(int len, int range) {
            if (len < 1) {
                return null;
            }
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) {
                arr[i] = (int) (Math.random() * range);
            }
            return arr;
        }
    
        public static void printArray(int[] arr) {
            if (arr == null || arr.length == 0) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        public static boolean isSorted(int[] arr) {
            if (arr == null || arr.length < 2) {
                return true;
            }
            for (int i = 1; i < arr.length; i++) {
                if (arr[i - 1] > arr[i]) {
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
            int len = 10;
            int range = 10;
            int testTimes = 50000;
            for (int i = 0; i < testTimes; i++) {
                int[] arr = generateArray(len, range);
                countSort(arr);
                if (!isSorted(arr)) {
                    System.out.println("Wrong Case:");
                    printArray(arr);
                    break;
                }
            }
    
            int len2 = 13;
            int range2 = 10;
            int testTimes2 = 50000;
            for (int i = 0; i < testTimes2; i++) {
                int[] arr = generateArray(len2, range2);
                countSort(arr);
                if (!isSorted(arr)) {
                    System.out.println("Wrong Case:");
                    printArray(arr);
                    break;
                }
            }
        }
    }