logo标签列表

如何对ArrayList进行排序

java
3

我需要最简单的方法来对ArrayList进行排序，但不使用Java内置的排序器。目前，我将ArrayList更改为Array并使用线性排序代码，但后来需要调用一些元素，而ArrayList更容易实现这一点。

7
“内置Java排序器”是什么意思？为什么你不想使用它？"内置Java排序器"指的是Java编程语言中已经实现好的排序算法。可能有些人不想使用它是因为他们希望自己实现一个不同的排序算法，或者因为他们认为自己的实现比内置的算法更有效率。 - Ted Hopp
1
我不能使用它，因为我打算自己编写代码。我的意思是collections.sort，它已经内置在我里面了。XD - Thomas Donaldson
1
想自己编码吗？如果这是作业，请标记为 [homework]。 - Louis Wasserman
（添加作业标签...） - Stephen C
1
（为了删除所有剩余的11k +标签，已删除作业标签，以便可以将其列入黑名单。 :-) - corsiKa
9个回答
5
您可以使用匿名排序。
Collections.sort(<ArrayList name>, Comparator<T>() {

    public int compare(T o1, T o2) {
    .....
    ....
    }      
});

如果您想对类型进行排序（例如String，Objects），只需根据自己的需要实现Comparator接口即可。

3
他特别提到他不能使用内置的排序器。 - Jake Greene
3
假设有一个 ArrayList<String> a...
最简单的方法（但我猜想这是您说不能使用的方法）：
Collections.sort(a);

下一个最简单的方法（但是浪费）：
a = new ArrayList<String>(new TreeSet<String>(a));
TreeSet将会消除任何重复的字符串。 - Gilbert Le Blanc
3
假设“内置排序”指的是Collections.sort()，并且您已经完成了所需的排序算法，您可以将排序后的数组转换为一个ArrayList。
ArrayList list = new ArrayList(Arrays.asList(sortedArray));

或者，您可以通过使用 get(int index) 和 set(int index, E element) 方法，将您的排序算法重写以与List（如ArrayList）一起使用，而不是数组。

1
如果必要的话，OP可以先将ArrayList转换为数组（使用ArrayList的toArray(T[] a)方法），然后创建一个新的ArrayList，如此所示，或者清空并重新填充原始数组（使用addAll(Arrays.asList(sortedArray))）。+1是对第一个响应OP约束条件的答案的奖励。 - Ted Hopp
2

不使用Arrays.sort对通过命令提示传递的参数进行排序

public class Sort {

    public static void main(String args[]) 
    {
        for(int j = 0; j < args.length; j++) 
        {
            for(int i = j + 1; i < args.length; i++) 
            {
                if(args[i].compareTo(args[j]) < 0) 
                {
                    String t = args[j];
                    args[j] = args[i];
                    args[i] = t;
                }
            }
            System.out.println(args[j]);
        }
    }
}

通过使用Array.sort函数
import java.util.*;
public class IntegerArray {

    public static void main(String args[])
    {
        int[] num=new int[]{10, 15, 20, 25, 12, 14};
    Arrays.sort(num);
        System.out.println("Ascending order: ");
        for (int i=0; i<num.length; i++)
            System.out.print(num[i] + " ");
        }
}
0
1
他要求不使用内置的Java排序器。我猜这就是他不想要的。 - La bla bla
他特别提到他不能使用内置的排序器。 - Jake Greene
0

在Java中检查Comparator。您可以使用它来实现自己的排序，并使用Collections.sort(..)使用您自己的Comparator对数组列表进行排序。

Comparator 本身并不实际进行任何排序，它只定义了排序规则。他仍然需要调用一个使用 Comparator（或 Comparable 接口）来确定如何排序的排序函数。 - Jon Newmuis
是的，同意。这就是为什么我建议检查Collections类的原因。 - raddykrish
他特别提到他不能使用内置的排序器。 - Jake Greene
我不知道为什么会被投反对票...现在这是一份作业，我想我的线索应该足够好开始了。 - raddykrish
你的回答建议使用Collections.sort（...），这是Java内置排序器最接近的东西。请解释如何在创建自己的排序时使用比较器接口，我会撤回我的负投票。 - Jake Greene
@JakeGreene 对不起，我的错，我以另一种方式忽略了这个问题。接受你的反对票。 - raddykrish
0

如果我没记错的话，当你从一个 arrayList 中取出一个元素时，它会自动将剩余的元素向下移动。如果你做一个循环来查找最小值并将其取出，然后将其放在 arrayList 的末尾，则每次循环中索引都会减少 1。因此，在一个包含 10 个元素的列表中，您将查看所有的 10 个元素，获取最小值并将其附加到末尾。接下来，您将查看前九个元素，并将其中的最小值取出并附加到末尾。然后是前八个元素等等，直到列表被排序。

1
请注意，这是最坏情况下的“O(n!)”，时间效率非常低。有许多排序算法可以更好地执行。 - Jon Newmuis
是的，但他确实要求最简单的方法来做到这一点。我猜尽管这被标记为Java，但它也是作业，他只需要一种方法来对其进行排序。有更好的方法，但如果他在这里提问，那么他可能不知道如何使用那些方法。只是假设，这就是我阅读/解释问题的方式。 - aaron burns
0

如果你需要自己对数组进行排序，那么最简单的算法之一就是冒泡排序。它通过多次遍历数组，比较相邻的元素，并在左侧元素大于右侧元素时交换它们来工作。

由于这是作业，我会让你自己去解决剩下的问题。首先要想象你的算法，然后考虑你的算法需要进行多少次遍历，以及每次遍历需要从哪里开始。然后编写代码。

你还需要理解并解决如何比较一对数组元素的问题：

  • 如果元素是基本类型的实例，你只需使用关系运算符。
  • 如果元素是引用类型的实例，则需要使用Comparable或Comparator接口。在javadoc中查找它们。（查找它们也是你的作业的一部分...）
0
这是一个“简单”的快速排序实现：
public Comparable<Object>[] quickSort(Comparable<Object>[] array) {
    if (array.length <= 1) {
        return array;
    }

    List<Comparable<Object>> less = new ArrayList<Comparable<Object>>();
    List<Comparable<Object>> greater = new ArrayList<Comparable<Object>>();
    Comparable<Object> pivot = array[array.length / 2];

    for (int i = 0;i < array.length;i++) {
        if (array[i].equals(pivot)) {
            continue;
        }
        if (array[i].compareTo(pivot) <= 0) {
            less.add(array[i]);
        } else {
            greater.add(array[i]);
        }
    }

    List<Comparable<Object>> result = new ArrayList<Comparable<Object>>(array.length);
    result.addAll(Arrays.asList(quickSort(less.toArray(new Comparable<Object>[less.size()]))));
    result.add(pivot);
    result.addAll(Arrays.asList(quickSort(greater.toArray(new Comparable<Object>[greater.size()]))));
    return result.toArray(new Comparable<Object>[result.size()]);
}

使用System.arraycopy可以提高使用数组和列表构建结果的最后操作。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接