我的插入排序代码出了什么问题

Question

我正试图在我的android应用程序中实现这段代码，加油站列表应该按升序排序。我应该实现另一种排序方法吗？导入java.util.ArrayList；

public class sortTest {
/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    ArrayList<Float> arr   = new ArrayList<Float> ();
    for (int i = 0 ; i <= 12 ; i++)
    {
    arr.add(i, (float) (((Math.random() * 90) + 10)/10)); // add random values to array 
    }
    ArrayList<String> listDataHeader = new ArrayList<String>();
    listDataHeader.add("Shell distance: "+ arr.get(0));
    listDataHeader.add("Esso  Distance:" +arr.get(1));
    listDataHeader.add("Tesco Distance "+arr.get(2));
    listDataHeader.add("Asda Distance "+arr.get(3));
    listDataHeader.add("BP Distance "+arr.get(4));
    listDataHeader.add("Texaco Distance "+arr.get(5));

    String temp;
    int f = listDataHeader.size();
    for(int i=0;i<f;i++){
      for(int j=i+1;j<f;j++){
        if(arr.get(i)>arr.get(j)){
          temp = listDataHeader.get(i);
          String x = listDataHeader.get(j);
          listDataHeader.set(i,listDataHeader.get(j));
          listDataHeader.set(j,temp);
         }
      }
    }
    for(String str:listDataHeader) //this list is list<String>
      {
      System.out.println(str);
      }
   }
}

Answer 1

这是冒泡排序，而不是插入排序。另外，你知道已经有Collections.sort()方法了吗？

无论如何，它不起作用的原因是因为你有两个不同的列表。你正在对其中一个进行排序，并对另一个进行比较（你正在交换listDataHeader的元素，但你的测试在列表arr上）。

我的建议是：只保留一个列表进行交换和比较：使用arr。排序后，格式化它，添加加油站的名称，并将其传递到另一个列表：listDataHeader。

但如果你想保持原样，你可以在交换listDataHeader的同时交换arr，这会起作用。

另一个需要更多工作的解决方案：

您可以创建自己的Petrol类来实现Comparable接口。这个类可以有两个元素：一个是带有汽油名称的String，另一个是要排序的随机值float

现在您可以创建一个List并将所有的Petrol都放在那里，然后只需调用Collections.sort（）在这个清单上，它会起作用的。

有很多关于如何实现Comparable的例子，甚至在Java教程中也有一些。

好的部分：如果你这样做，你将掌握更多关于Java中的东西是如何扩展的知识。

Answer 2

您的代码进行了一些不必要的调用（String x被赋值，但根本不使用），并且也不是插入排序。这种情况下的插入排序为：

    int f = listDataHeader.size();
    for(int i=0; i<f; i++){    //first prediction: the smallest element in iteration is at "i".
        int prediction = i;
        for(int j=i+1; j<f; j++){
            if(arr.get(i) > arr.get(j)){    //found even smaller element - change prediction.
                prediction = j
            }
         }
         String temp = listDataHeader.get(i);
         listDataHeader.set(i, listDataHeader.get(prediction);
         listDataHeader.set(j, temp);
         arr.set(j, arr.get(i));            //for this to work you need to sort the array of
         arr.set(i, arr.get(prediction));   //values as well.
      }

您当前的算法正在进行冒泡排序，而不是以通常的方式（使用do-while循环）。您还可以通过检查是否预测来改进我编写的代码！=i.如果没有，则不需要交换。阅读更多关于简单排序算法的信息。