在Java中数组排序 [英] Sorting arrays in Java

问题描述

写了一个静态方法：

public static void sortByFour (int[] arr)

，其接收作为参数的阵列完全非负数（零或正值），并进行排序以下列方式在阵列

That receives as a parameter an array full of non-negative numbers (zero or positive) and sorts the array in the following way:

• 在该阵列的所有四个整除的数字将出现的开始

• In the beginning of the array all the numbers that are divisible by four will appear.

在他们所有的阵列中，通过4余数1分号将出现。

After them all the numbers in the array that divide by 4 with a remainder of 1 will appear.

在他们所有的阵列中，通过4采用了2分剩余数量将出现。

After them all the numbers in the array that divide by 4 with a remainder of 2 will appear.

在该阵列的所有其余的数字的末尾（那些除以4的余数3）将出现

In the end of the array all the rest numbers (those which divide by 4 with the remainder 3) will appear.

（各组中的号的顺序没有关系。）

(The order of the numbers in each group doesn't matter.)

的方法，必须尽可能有效

The method must be as efficient as possible.

下面是我写的，但不幸的是它不能很好地工作...：（

The following is what I wrote, but unfortunately it doesn't work well... :(

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 < right )
    {
        if ( ( arr[left] % 4 ) > ( arr[right] % 4 ) )
        {
            swap( arr, left, right );
            right--;
        }
        if ( ( arr[left] % 4 ) == ( arr[right] % 4 ) )
            left++;
        else
            left++;
    }
}

如何修复或重写我的code，使其将工作做好？

How do I fix or rewrite my code so that it will work well?

推荐答案

最渐近有效的方法，这样做将是使用桶排序。

A linear-time solution

The most asymptotically efficient way to do this would be to use bucket sort.

• 您有4个桶，一个用于每个一致性类数的模4。


• 数组中扫描数字一次
  
  
  
  • 把每个数字在右边的桶
  
  
  
  
  • 把所有的数字从0桶，然后再全部来自桶1，则斗2，然后斗3
  
  

  因此​​，这一排序在 O（N），这是最佳的数字。这里的关键是，通过对数字模4排序，有基本上仅4号来排序：0，1，2，3

  Thus, this sorts the numbers in O(N), which is optimal. The key here is that by sorting on numbers modulo 4, there are essentially only 4 numbers to sort: 0, 1, 2, 3.

  下面是一个使用的 M ） /api/java/util/List.html相对=nofollow> 列表 并换为每清晰。忽略选中投警告，只需集中精力去理解算法。

  Here's an implementation of the above algorithm (for general modulo M) using List and for-each for clarity. Ignore the unchecked cast warning, just concentrate on understanding the algorithm.

  import java.util.*;
  
  public class BucketModulo {
      public static void main(String[] args) {
          final int M = 4;
          List<Integer> nums = Arrays.asList(13,7,42,1,6,8,1,4,9,12,11,5);
          List<Integer>[] buckets = (List<Integer>[]) new List[M];
          for (int i = 0; i < M; i++) {
              buckets[i] = new ArrayList<Integer>();
          }
          for (int num : nums) {
              buckets[num % M].add(num);
          }
          nums = new ArrayList<Integer>();
          for (List<Integer> bucket : buckets) {
              nums.addAll(bucket);
          }
          System.out.println(nums);
          // prints "[8, 4, 12, 13, 1, 1, 9, 5, 42, 6, 7, 11]"
      }
  }
  

  在你完全明白的算法，这种转换使用数组（如果必须）是微不足道的。

  Once you fully understand the algorithm, translating this to use arrays (if you must) is trivial.

  
  
  • java.util中。清单＆LT; E＆GT; API - 有序的collection
    
    
    
    • 添加（E E） - 将指定元素添加到此列表的末尾
    
    
    • 的addAll（...） - 所有指定集合中的元素追加到此列表的末尾
    
    
    • java.util.List<E> API - "An ordered collection"
      • add(E e) - "Appends the specified element to the end of this list"
      • addAll(...) - "Appends all of the elements in the specified collection to the end of this list"

      的规定，即数字都是非负为显著，因为％不是的模的运营商，因为它的数学定义;它的的剩余的运营商。

      The stipulation that numbers are non-negative is significant, because % is NOT the modulo operator as it's mathematically defined; it's the remainder operator.

      System.out.println(-1 % 2); // prints "-1"
      

      参考

      
      
      • JLS 15.17.3余操作符％
      
      
      • 维基/模操作
      
      

      References

      • JLS 15.17.3 Remainder Operator %
      • Wikipedia/Modulo operation

      这篇关于在Java中数组排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！