用Java排序数组
用Java编写静态方法：
public static void sortByFour (int[] arr) 它接收一个充满非负数（零或正数）的数组作为参数，并按以下方式对数组进行排序：
-
在数组的开头，将出现所有可被4整除的数字。
-
在它们之后，将出现数组中除以4且余数为1的所有数字。
-
在它们之后，将显示数组中除以4且余数为2的所有数字。
-
在数组的末尾，将出现所有剩余数字（除以4除以3的数字）。
（每组中数字的顺序无关紧要。）
该方法必须尽可能高效。
以下是我写的，但不幸的是它不能很好地工作…… 🙁
public static void swap( int[] arr, int left, int right ) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } public static void sortByFour( int[] arr ) { int left = 0; int right = ( arr.length - 1 ); int mid = ( arr.length / 2 ); while ( left ( arr[right] % 4 ) ) { swap( arr, left, right ); right--; } if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) ) left++; else left++; } }
如何修复或重写我的代码以使其运行良好？
我会在psuedocode中为你做这个，但是在代码中这样做会给你答案，这是功课，所以你可以做自己的工作。 = P
以下是没有列表的方法。 此示例基于要求进行了限制，但一旦您编码就可以使用。
int bucketSize = (arr.length() / 4) + 1; int bucket1[bucketSize]; int bucket2[bucketSize]; int bucket3[bucketSize]; int bucket4[bucketSize]; for (int i=0; i
然后按各自的顺序连接四个桶以获得最终结果
你可以像这样攻击这个问题：
- 选择您要使用的排序算法。 看起来你正在尝试编程Quicksort ，但你也可以使用Bubble Sort 。
- 确定算法的点，其中比较输入数组中的两个值。 例如，在维基百科文章中的冒泡排序的伪代码中，唯一的比较是
if A[i] > A[i+1] then...。 - 找出一种比较两个数字的方法，以便当除以4时，余数为0的数字s被认为小于具有余数1的数字t除以4.将算法的比较操作替换为比较器计算（例如，
if myIsGreater(A[i], A[i+1]) then...）。
对于第3步，通过考虑模数运算符，您肯定在正确的轨道上。
我将重申Daniel所说的内容：您可以选择排序算法。 如果这是要求，请使用目前为止在课堂上介绍过的最有效的课程。 但是当你在算法中得到两个项目的比较点时，请比较它们的值mod 4。 因此， if A[i] > A[j] if A[i] % 4 > if A[j] % 4 。 然后你继续做任何算法指定你对该数组元素做的事情。 交换它，冒泡它，返回它，无论需要什么。
关于您发布的代码，我认为它不适合快速修复。 它应该使用哪种算法？ 什么是mid的？ 我想，一旦你知道你打算使用哪种算法，并找出包含比较的代码行，你就能够快速查看和编写解决方案。
一般而言，通过这些事情，如果您在担心效率之前专注于获得可行的解决方案，它会有所帮助。 我第一次做这样的问题时使用了选择排序。 我建议首先尝试，然后使用获得的经验进行合并排序，即O（n log n）。
线性时间解决方案
最常见的有效方法是使用桶排序 。
- 你有4个桶，每个数量为4的一致数类。
- 扫描arrays中的数字一次
- 将每个数字放在正确的桶中
- 然后构造输出数组
- 首先从桶0中放入所有数字，然后从桶1，然后桶2，然后桶3
因此，这将O(N)的数字排序，这是最佳的。 这里的关键是通过对模4的数字进行排序，基本上只有4个数字可以排序：0,1,2,3。
List的说明性解决方案
以下是使用List和for-each的上述算法（对于通用模M ）的实现，以便清楚。 忽略未经检查的强制转换警告，只需专注于理解算法即可。
import java.util.*; public class BucketModulo { public static void main(String[] args) { final int M = 4; List nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5); List [] buckets = (List []) new List[M]; for (int i = 0; i < M; i++) { buckets[i] = new ArrayList (); } for (int num : nums) { buckets[num % M].add(num); } nums = new ArrayList (); for (List bucket : buckets) { nums.addAll(bucket); } System.out.println(nums); // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]" } }
一旦你完全理解了算法，将其转换为使用数组（如果你必须）是微不足道的。
也可以看看
-
java.util.ListAPI – “有序集合”-
add(E e)– “将指定的元素追加到此列表的末尾” -
addAll(...)– “将指定集合中的所有元素追加到此列表的末尾”
-
- Java语言指南/ for-each循环 （1.5.0中引入）
关于%的特别说明
数字非负的规定很重要，因为%不是模数运算符，因为它是数学定义的; 它是余数运算符。
System.out.println(-1 % 2); // prints "-1"
参考
- JLS 15.17.3剩余运算符％
- 维基百科/ Modulo操作
阅读此页面。 http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms
从长远来看，这应该对你有所帮助。 这也很有趣！
这是一种Java-ish方式……
Arrays.sort(arr,new Comparator(){ public int compare(Integer a,Integer b) { return (a % 4) - (b % 4); } });