使用插入和选择排序对对象数组进行排序

Question

我需要创建一个方法来对对象数组进行排序。我从来没有这样做过，但我必须为我的课程修改它。在实施排序方法时，我完全迷路了。我需要使用 插入排序 和 选择排序 进行排序。

这是我目前使用的代码。我所要做的就是在用户希望时调用 sort()。

package citylisttest;

public class CityList {
    private City[] city;
    private Integer numberOfCities;

    public CityList (Integer cityListSize){
        this.city=new City[cityListSize];
        this.numberOfCities=0;
    }

    public void addCity(String city){
        this.city[this.numberOfCities]=new City(city);
        this.numberOfCities++;
    }

    public String toString(){
        String cityDetails=new String();
        if (this.numberOfCities!=0){
            cityDetails+=String.format("%-15s\n","CITY");
            for(Integer i=0;i<this.numberOfCities;i++) {
                cityDetails+=this.city[i]+"\n"; }
        }
        else
            cityDetails+="City list is empty";
            return cityDetails;
        }

     public void sort(){

    }
}

Answer 1

首先，我建议将变量 city 重命名为 cities，因为它是一个数组，并且包含多个城市。此外，还可以考虑通过将实例变量标记为私有并分别创建 getter 和 setter 来封装数据。

假设您要按城市数升序对它们进行排序，那么您的排序方法应该是：

for (int i = 0; i < city.length - 1; i++) {
    for (int j = i + 1; j < city.length; j++) {
        if (city[i].getNumberOfCities() > city[j].getNumberOfCities()) {
            City temp_city = city[i];
            city[i] = city[j];
            city[j] = temp_city;
        }
    }
}

希望这对您有所帮助，但您可以实现 Comparable 接口或在 this tutorial.

之后创建 Comparator class

编辑：如果您想使用 compareto，按升序对城市名称进行排序：

for (int i = 0; i < city.length - 1; i++) {
    for (int j = i + 1; j < city.length; j++) {
        if (city[i].getName().compareTo(city[j].getName()) > 1) {
            City temp_city = city[i];
            city[i] = city[j];
            city[j] = temp_city;
        }
    }
}

假设 x 和 y 是字符串，x.compareTo(y) 得到：

正数如果 x > y

如果 x 等于 y 则为零

负数如果 x

Answer 2

关于这个主题的文档在 Internet 上很常见，但是 "let me google that for you"。

我建议了解你想做什么。所以我建议你先看看什么是排序算法：

https://en.wikipedia.org/wiki/Sorting_algorithm

然后，特别是插入排序算法：

https://en.wikipedia.org/wiki/Insertion_sort

或选择排序：

https://en.wikipedia.org/wiki/Selection_sort

这里有人可以给你答案，但如果你不努力解决这个问题，你就不会了解它，你很快就会忘记它。

希望对您有所帮助:)

Answer 3

这看起来很像一道作业题，因为通常的做法是不创建自己的排序算法。

与 copy/pasting 您在此处找到的任何答案相比，通过尝试设计自己的解决方案，即使它是幼稚的，您也会走得更远。

如果您真的想探索各种可能的解决方案（使用 java 源代码），您可以遵循此小程序和教程：

https://thomas.baudel.name/Visualisation/VisuTri/

Answer 4

这是代码。但在去那里之前，我认为你应该观看这两个视频：

插入排序：https://www.youtube.com/watch?v=DFG-XuyPYUQ&t=142s

选择排序：https://www.youtube.com/watch?v=f8hXR_Hvybo

public static void insertionSort(Object[] data) {
// i denotes where the partition is
for (int i = 1; i < data.length; i++) {
// the key is to the right of the partition
Object key = data[i];
int j = i - 1; // use j to scan left to insert key
while (j >= 0 && ((Comparable) key).compareTo(data[j]) < 0) {
// shift item right to make room
data[j + 1] = data[j];
j--;
}
// Found the position where key can be inserted
data[j + 1] = key;
}
}

public static void selectionSort(Object[] data) {
for (int i = 0; i < data.length - 1; i++) {
// Find the index of the minimum item, starting at `i'.
int minIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (((Comparable) data[j]).compareTo(data[minIndex]) < 0)
minIndex = j;
// Exchange with the first item (at `i'), but only if different
if (i != minIndex) {
Object tmp = data[i];
data[i] = data[minIndex];
data[minIndex] = tmp;
}
}
}

使用插入和选择排序对对象数组进行排序

Sorting an object array using Insert and Selection sorts

java

arrays

sorting

object

insertion-sort