前言

lab13 实现了 counting sort 和 radix sort。

counting sort

目标：寻求一种使得 counting sort 能够处理负数的方法

[9, -1, 3, 5, -1, -2, 1]

思路：创建两个counts数组，一个统计正数的出现次数，记为countPos；一个统计负数的出现次数，记为countNe。然后根据这两个count数组，再创建两个starts数组，一个存储正数的位置，一个存储负数的位置。之后根据两个starts数组填充sorted数组即可。

一些注意事项：

  • startsPos 存储正数位置时要加上一个等于负数个数的偏移量
  • 注意处理负数时要加绝对值

下方是示例代码：

public static int[] betterCountingSort(int[] arr) {
        // TODO make counting sort work with arrays containing negative numbers.
        // find max
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = max > i ? max : i;
        }

        // find min
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            min = min < i ? min : i;
        }

        int neNum = 0;
        int[] countPos = new int[max + 1];
        int[] countNe = new int[Math.abs(min) + 1];

        for (int i : arr) {
            if (i >= 0) {
                countPos[i]++;
            } else {
                countNe[Math.abs(i)]++;
                neNum++;
            }
        }

        int[] startsPos = new int[max + 1];
        int[] startsNe = new int[Math.abs(min) + 1];
        int pos = 0;
        for (int i = 0; i < startsPos.length; i += 1) {
            startsPos[i] = pos + neNum;
            pos += countPos[i];
        }

        pos = 0;
        for (int i = startsNe.length - 1; i >= 0; i -= 1) {
            startsNe[i] = pos;
            pos += countNe[i];
        }

        int size = arr.length;
        int[] sorted = new int[size];
        for (int i = 0; i < size; i += 1) {
            int item = arr[i];
            int place;
            if (item >= 0) {
                place = startsPos[item];
                startsPos[item] += 1;
            } else {
                int absItem = Math.abs(item);
                place = startsNe[absItem];
                startsNe[absItem] += 1;
            }
            sorted[place] = item;
        }
        return sorted;
    }

radix sort

目标：基于 LSD radix sort 算法按照字典序排序一个 ASCII 字符串数组，注意排序数字和字符串的区别（字符串长度不同时右边填充占位符）

字典序就是基于字符的ASCII值决定顺序。

50 48 97 98

48 50 97 98

0 2 a b

0 2 a b

50 49 97 98

引用