Tag: 基数 排序

什么构成算法上下文中的“数组访问”？

下面是一个用Java编写的LSD Radix排序实现，用于对一个字符串数组进行排序，其中每个字符串都包含正好的W字符。 我想计算运行时的数组访问次数。 我已经读过LSD排序应该要求n * c数组访问，其中n是字符串数， c是每个字符串中的字符数。 但是，下面的算法会多次访问多个数组。 如果我在每个中增加一个计数器，我最终会得到一个重要因素nc 。 那么究竟什么构成了算法上下文中的“数组访问”？ 是否只有一个数组访问实例被认为是更重要的，我应该在这里计算，或者这个例子实际上是一个低效的实现，它使用了比必要更多的数组访问？ public int lsdSort(String[] array, int W) { int access = 0; // Sort a[] on leading W characters. int N = array.length; String[] aux = new String[N]; for (int d = W-1; d >= 0; d–) { // Sort by key-indexed counting on […]