基数排序

分手后的思念是犯贱 2022-06-09 01:36 199阅读 0赞

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

给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。

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

> 参考文档：[http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html][http_www.cnblogs.com_Braveliu_archive_2013_01_21_2870201.html]

我的提交

# -*- coding:utf-8 -*-
    
    class RadixSort:
        def radixSort(self, A, n):
            # write code here
            buckets = {}
            for i in range(10):
                buckets[i] = []
    
            bases = [1, 10, 100, 1000]
    
            for base in bases:
                for num in A:
                    number = (num // base) % 10
                    buckets[number].append(num)
    
                k = 0
                for i in range(10):
                    for num in buckets[i]:
                        A[k] = num
                        k += 1
                        buckets[i] = []
    
            return A
    
    if __name__ == '__main__':
        r = RadixSort()
        print(r.radixSort([1,2,3,5,2,3],6))

**参考答案**

import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class RadixSort {
        // ˝◊Èø…∞¸∫¨’˝ ˝°¢∏∫ ˝°¢0µƒª˘ ˝≈≈–Ú
        public static void radixSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            int negNum = 0; // arr÷–∏∫ ˝µƒ∏ˆ ˝
            for (int i = 0; i < arr.length; i++) {
                negNum += arr[i] < 0 ? 1 : 0;
            }
            int[] negArr = new int[negNum];
            int[] posArr = new int[arr.length - negNum];
            int negi = 0;
            int posi = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] < 0) {
                    negArr[negi++] = -arr[i];
                } else {
                    posArr[posi++] = arr[i];
                }
            }
            radixSortForPositive(negArr);
            radixSortForPositive(posArr);
            int index = 0;
            for (int i = negArr.length - 1; i >= 0; i--) {
                arr[index++] = -negArr[i];
            }
            for (int i = 0; i < posArr.length; i++) {
                arr[index++] = posArr[i];
            }
        }
    
        // ÷ªƒ‹Ω‚æˆ’˝’˚ ˝ ˝◊Èµƒª˘ ˝≈≈–Ú
        public static void radixSortForPositive(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            ArrayList> qArr1 = new ArrayList>();
            ArrayList> qArr2 = new ArrayList>();
            for (int i = 0; i < 10; i++) {
                qArr1.add(new LinkedList());
                qArr2.add(new LinkedList());
            }
            for (int i = 0; i < arr.length; i++) {
                qArr1.get(arr[i] % 10).offer(arr[i]);
            }
            long base = 10;
            while (base <= Integer.MAX_VALUE) {
                for (int i = 0; i < 10; i++) {
                    LinkedList queue = qArr1.get(i);
                    while (!queue.isEmpty()) {
                        int value = queue.poll();
                        qArr2.get((int) (value / base) % 10).offer(value);
                    }
                }
                ArrayList> tmp = qArr1;
                qArr1 = qArr2;
                qArr2 = tmp;
                base *= 10;
            }
            int index = 0;
            for (int i = 0; i < 10; i++) {
                LinkedList queue = qArr1.get(i);
                while (!queue.isEmpty()) {
                    arr[index++] = queue.poll();
                }
            }
        }
    
        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) - 500000000;
            }
            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 = Integer.MAX_VALUE;
            int testTimes = 50000;
            for (int i = 0; i < testTimes; i++) {
                int[] arr = generateArray(len, range);
                radixSort(arr);
                if (!isSorted(arr)) {
                    System.out.println("Wrong Case:");
                    printArray(arr);
                    break;
                }
            }
        }
    }

[http_www.cnblogs.com_Braveliu_archive_2013_01_21_2870201.html]: http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html