java对列表进行排序需要很多时间

Question

我有以下列表要排序：

  A 0.53
  B 0.56
  C 0.56
  D 0.98
  E 0.33

请注意，我的列表可能包含1000条此类记录。我正在对列表进行排序，并将排序后的列表放入数组中，如下所示：

  String str="";
        for(String s: mylist){
            str+=s+",";
        }
        String[] sArr = str.split(",");
        String temp="";
        for(int i=0; i<sArr.length;i++) {
            for(int j= i+1; j<sArr.length;j++){
                if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){
                    temp= sArr[j];
                    sArr[j]= sArr[i];
                    sArr[i]=temp;
                }
            }
        } 

       //sArr now contains the sorted list

问题是，当我有1000条记录时，需要花费很长时间才能进行排序。 我的问题: 有没有其他方法可以在更短的时间内高效地执行相同的任务！还是我的编码方式有问题。谁能帮帮我吗

Answer 1

你的排序耗时这么长的原因是你没有使用有效的排序算法。通常，在对大量数据/记录等进行排序时，需要确定最适合现有数据的算法或解决方案

目前，您的算法的运行时间似乎为O（N^2），这通常是非常糟糕的，以下是为什么它是O（N^2）

//The outer-loop traverses through the "N" indexes of the array.
for(int i=0; i<sArr.length;i++) {

        //The inner-loop also traverses through the "N" indexes of the array
        for(int j= i+1; j<sArr.length;j++){

            //Most comparisons are able to be done in O(1)
            if(sArr[i].split("\\s")[1].compareToIgnoreCase(sArr[j].split("\\s")[1])<0){

                //Assignments are done in O(1)
                temp= sArr[j];
                sArr[j]= sArr[i];
                sArr[i]=temp;
            }
        }

所以，我们真正关心的是当N足够大时的运行时间。当N变大时，我们将得到结果：O(N) * O(N) = O(N^2)这是因为我们正在研究最坏情况最好的情况是，所有内容都已排序，我们所要做的就是查看每个元素，这将导致O(N)运行时

如果你看一个像Quicksort这样的算法（或者看Mergesort），你肯定会看到一个很大的改进，因为最坏情况和最佳情况（通常）会看到O(n log n)的运行时间，这比当前的方法要快得多

我鼓励您考虑实施更好/更高效的排序算法

我相信Java在其数组库中实现了合并排序Arrays.sort()

Answer 2

代码似乎有两个问题。首先是：

String str="";
for(String s: mylist) {
    str+=s+",";
}
String[] sArr = str.split(",");

很明显，您是在毫无理由地加入一组字符串，然后再次将其拆分为一个数组。更糟糕的是，您使用的是字符串连接（即+运算符）

在Java中，字符串是不可变的对象。这意味着每一个看起来像在更改字符串对象的操作实际上都在创建一个新的字符串对象。每次str+=s+","都会创建新对象。重复上千次是非常低效的

当您需要像这样编写String时，应该使用^{}。不过，在这种情况下，我认为根本没有必要

如果我正确理解了您的代码，那么列表mylist似乎已经包含了以下格式的记录：

["A 0.53", "B 0.56", ...]

如果是这种情况，您可以直接对mylist进行排序

从这里开始，我将假定mylist是List<String>。如果情况并非如此，而且mylist实际上是一个String[]，那么只需要使用Arrays.sort(mylist, comparator)而不是mylist.sort(comparator)

首先，您需要一种方法来从String记录中提取Double值，因为我假设您试图通过数字来比较double和String

static Double doubleFromRecord(String record) {
    return Double.valueOf(record.split("\\s")[1]);
}

所以，doubleFromRecord("A 0.53")将0.53作为Double返回

现在，您只需要直接在mylist上调用sort，通过一个Comparator来比较不同元素的数字：

mylist.sort((r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2)));

和mylist将被排序

比较国：

(r1, r2) -> doubleFromRecord(r1).compareTo(doubleFromRecord(r2))

只需从mylist中获取两个元素，并返回它们的数字部分之间的比较结果

如果可以，我建议您为记录创建一个类，例如：

class Record {
    final String label;
    final double value;

    Record(String label, double value) {
        this.label = label;
        this.value = value;
    }
 }

和List<Record>而不是List<String>一起工作。所以你可以很容易地做到：

myRecordList.sort((r1, r2) -> Double.compare(r1.value, r2.value));

Answer 3

您可能需要使用TreeSet，它从一开始就排序。我从洛贝德那里借了一小部分DataPoint课

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<DataPoint> set = new TreeSet<DataPoint>();
        String[] splitS;
        for (String s : YOUR_LIST) {
            splitS = s.split(" ");
            set.add(new DataPoint(splitS[0], Double.parseDouble(splitS[1])));
        }
        DataPoint[] sortedArray = new DataPoint[set.size()];
        set.toArray(sortedArray); //but to be honest there is no reason for using array at this point
    }
}

class DataPoint implements Comparable<DataPoint> {
    public String key;
    public double value;

    public DataPoint(String key, double value) {
        this.key = key;
        this.value = value;
    }

    public int compareTo(DataPoint p){
        return Double.compare(value, p.value);
    }
}

Answer 4

您的代码依赖于许多字符串操作。字符串在java中是不可变的。例如：如果你有字符串a和字符串b，你写a+=b；java不只是将字符串b添加到a中。它从字符串a+字符串b创建一个新的字符串实例，从而生成一个新的字符串对象。这样做一两次没什么大不了的，但你的代码确实非常依赖于此

我的方法是为您的数据创建一个新类，该类实现了Comable接口：

public class DataPoint implements Comparable<DataPoint>{
    public String key;
    public double value;

    public int compareTo(DataPoint p2){
        if(this.value < p2.value)
             return -1;
        if(this.value == p2.value)
             return 0;
        if(this.value > p2.value)
             return 1;
    }
}

然后建立这些数据点对象和调用集合的列表。排序（数据点列表）

然后，dataPointList包含按排序的值

Answer 5

有很多方法可以对元素列表进行排序。您正在使用插入排序，这是一种缓慢的排序方法。你可以使用：

Arrays.sort(sArr);

应该比插入排序快

如果您想了解有关排序算法的更多信息： wikipedia