在 Java 中使用插入排序方法对链表进行排序
Sorting a linked list using insert sort method in Java
我的 class 有一项任务是对我们之前使用插入排序方法创建的 LinkedList 进行排序。我们通过读取 excel 文件创建了列表，其中列出了 5 个贡献者。我意识到这听起来像是一个重复的问题……但是，我能找到的所有样本都与整数或数组有关，我找不到任何与字符串或像我正在使用的 LinkedList 一样的样本。另一个问题，我确实发现处理的不仅仅是整数的例子假设你使用 Head 和 Node 和类似的东西制作了列表 "from scratch"......正如你在我的代码中看到的那样，我没有制作我从头开始，我只是使用内置 Java 实用程序来制作我的。无论如何，我的代码可能不是非常高效，但到目前为止我在每项作业中都得到了 100 分，所以我想这对学校来说已经足够了，但也欢迎任何让它变得更好的建议。我是编程初学者，我只有以前的经验 classes。所以，这是我的代码：
import java.io.*;
import java.util.*;
public class ChrisJohnson_Unit3_IP {
static class Contributor{ //create class to store contributor information
//declare variables
private String firstName;
private String lastName;
private String country;
private String phone;
private double contribution;
private int id;
//methods for setting variable values
public String getFirstName(){
return firstName;
}
public void setFirstName(String firstName){
this.firstName = firstName;
}
public String getLastName(){
return lastName;
}
public void setLastName(String lastName){
this.lastName = lastName;
}
public String getCountry(){
return country;
}
public void setCountry(String country){
this.country = country;
}
public String getPhone() {
return phone;
}
public void setPhone(String phone){
this.phone = phone;
}
public double getContribution(){
return contribution;
}
public void setContribution(double contribution){
this.contribution = contribution;
}
public int getId(){
return id;
}
public void setId(int id){
this.id = id;
}
public void Print(){//method to print class objects
System.out.printf("%-10s %-10s %-8s %-15s %s %-15s %d %n", firstName, lastName, country,
phone, "$", contribution, id);
}
}//end Contributor class
static LinkedList contributorList = new LinkedList(); //create new Contributor Linked List
static Hashtable<String, Contributor> memberID = new Hashtable<>();//create new Hash Table
public static void main(String[] arg) throws Exception {
String response;
String ID;
Contributor contributorData = null;
Scanner in = new Scanner(System.in);
//print Welcome message and describe program to user
System.out.println("Welcome! This program will read your contributors.csv file "
+ "and store it into a list. \nTThe program will then sort the list and"
+ "print it for you to view/n");
System.out.println("Press enter to read the currently saved contributors.csv file...");
in.nextLine();
BufferedReader File =
new BufferedReader(new FileReader("contributors.csv"));
String dataRow = File.readLine(); // Read first line.
// The while checks to see if the data is null. If
// it is, end of file has been reached. If not,
// data will be processed.
while (dataRow != null){//While to read contributors.csv file and store in Contributor object
String[] data = dataRow.split(",");
contributorData = new Contributor(); //create new Contributor object
//store data into Contributor object
contributorData.setFirstName(data[0]);
contributorData.setLastName(data[1]);
contributorData.setCountry(data[2]);
contributorData.setPhone(data[3]);
contributorData.setContribution(Double.parseDouble(data[4]));
contributorData.setId(Integer.parseInt(data[5]));
ID = Integer.toString(contributorData.getId());
contributorList.push(contributorData);//add object to top of contributorList
memberID.put(ID,contributorData);//add contributor ID to key element of Hash Table
dataRow = File.readLine(); // Read next line of data.
}//end While to read contributors.csv file
File.close();//close CSV file
System.out.println("Here is your unsorted contributor list:\n");
//call Print method to print the list
System.out.printf("%-10s %-10s %-8s %-15s %-17s %s %n", "First", "Last",
"Country", "Phone #", "Contribution", "ID");
Iterator<Contributor> iter = contributorList.iterator();
while(iter.hasNext()){
iter.next().Print();
}//end while
System.out.println("Thank you for using this program!");
} //main()
}//end ChrisJohnson_Unit3_IP class
同样，必须使用插入排序方法按名称对列表进行排序。我理解排序方法的基本概念，但老实说不知道如何在这里实现它。我不是在找人帮我做功课，只是在正确的方向上推动我。任何帮助将不胜感激，如果您需要更多信息，请告诉我。这项作业将于周一到期，因此希望届时有人能够帮助我。是的，我已经写信给我的教练寻求帮助，我整个星期都不在城里，所以我一直在努力追赶。感谢您花时间阅读我的问题
首先，我要说对链表做插入排序是完全没有意义的。其次，如果您添加一个连接贡献者名字和姓氏的 getName 方法，您可以执行类似以下操作（您可以在排序时连接，但您的代码会更混乱）。
for( int i = 1; i < contributorList.size(); i++)
{
int j = i;
Contributor tmp;
while( j > 0 && contributorList.get(j-1).getName().compareTo( contributorList.get(j).getName()) > 0)
{
tmp = contributorList.remove( j);
contributorList.add( j-1, tmp);
j = j - 1;
}
}
首先更改您的 contributorList 以使用其包含的对象的通用类型。即LinkedList<Contributor>;。其次更改对象以实现 Comparable。即 class Contributor implements Comparable<Contributor> 并实现方法 public int compareTo(Contributor other)。第三，选择一种排序方法并使用compareTo实现它来比较对象进行排序。
使用ListIterator找到插入元素的正确点并进行插入。这使您可以比使用 "standard approach" 更有效地进行插入排序，后者将 运行 in O(n³)，因为 get 和 set 运行 s 在 O(i) 中用于索引 i。 （内部循环将 运行 in O(i²)，因为 O(1+2+...+i) = O(i²) 和 O(1²+2²+...+n²) = O(n³)）。
注意using a Iterator足以在O(n)中找到插入点并实现O(n²)运行ning时间，但使用ListIterator可以让你查找和插入元素以及为外循环迭代的下一次迭代删除元素只有一个迭代器，如果使用巧妙的话。
使用 Comparator 按指定标准比较对象还允许您指定要排序的标准：
return value of comparator.compare(a, b) | meaning
-----------------------------------------------------------
0 | a == b
> 0 | a > b
< 0 | a < b
在 java 8 中，您可以轻松地创建一个 Comparator 给定方法引用给定一个对象返回排序标准的方法：
Comparator<Contributor> comparator = Comparator.comparing(Contributor::getLastName);
在不使用方法引用的情况下，这可以使用实现 Comparable 接口的对象的 compareTo 来完成，例如 String:
Comparator<Contributor> comparator = new Comparator<Contributor>() {
@Override
public int compare(Contributor o1, Contributor o2) {
return o1.getLastName().compareTo(o2.getLastName());
}
};
这样你就可以使用the Strategy Pattern for the ordering relation allowing you to use different sortings by passing different Comparators. And it's also the way the Collections class allows you to sort Lists with arbitrary contents, see Collections.sort(List, Comparator).
我的 class 有一项任务是对我们之前使用插入排序方法创建的 LinkedList 进行排序。我们通过读取 excel 文件创建了列表，其中列出了 5 个贡献者。我意识到这听起来像是一个重复的问题……但是，我能找到的所有样本都与整数或数组有关，我找不到任何与字符串或像我正在使用的 LinkedList 一样的样本。另一个问题，我确实发现处理的不仅仅是整数的例子假设你使用 Head 和 Node 和类似的东西制作了列表 "from scratch"......正如你在我的代码中看到的那样，我没有制作我从头开始，我只是使用内置 Java 实用程序来制作我的。无论如何，我的代码可能不是非常高效，但到目前为止我在每项作业中都得到了 100 分，所以我想这对学校来说已经足够了，但也欢迎任何让它变得更好的建议。我是编程初学者，我只有以前的经验 classes。所以，这是我的代码：
import java.io.*;
import java.util.*;
public class ChrisJohnson_Unit3_IP {
static class Contributor{ //create class to store contributor information
//declare variables
private String firstName;
private String lastName;
private String country;
private String phone;
private double contribution;
private int id;
//methods for setting variable values
public String getFirstName(){
return firstName;
}
public void setFirstName(String firstName){
this.firstName = firstName;
}
public String getLastName(){
return lastName;
}
public void setLastName(String lastName){
this.lastName = lastName;
}
public String getCountry(){
return country;
}
public void setCountry(String country){
this.country = country;
}
public String getPhone() {
return phone;
}
public void setPhone(String phone){
this.phone = phone;
}
public double getContribution(){
return contribution;
}
public void setContribution(double contribution){
this.contribution = contribution;
}
public int getId(){
return id;
}
public void setId(int id){
this.id = id;
}
public void Print(){//method to print class objects
System.out.printf("%-10s %-10s %-8s %-15s %s %-15s %d %n", firstName, lastName, country,
phone, "$", contribution, id);
}
}//end Contributor class
static LinkedList contributorList = new LinkedList(); //create new Contributor Linked List
static Hashtable<String, Contributor> memberID = new Hashtable<>();//create new Hash Table
public static void main(String[] arg) throws Exception {
String response;
String ID;
Contributor contributorData = null;
Scanner in = new Scanner(System.in);
//print Welcome message and describe program to user
System.out.println("Welcome! This program will read your contributors.csv file "
+ "and store it into a list. \nTThe program will then sort the list and"
+ "print it for you to view/n");
System.out.println("Press enter to read the currently saved contributors.csv file...");
in.nextLine();
BufferedReader File =
new BufferedReader(new FileReader("contributors.csv"));
String dataRow = File.readLine(); // Read first line.
// The while checks to see if the data is null. If
// it is, end of file has been reached. If not,
// data will be processed.
while (dataRow != null){//While to read contributors.csv file and store in Contributor object
String[] data = dataRow.split(",");
contributorData = new Contributor(); //create new Contributor object
//store data into Contributor object
contributorData.setFirstName(data[0]);
contributorData.setLastName(data[1]);
contributorData.setCountry(data[2]);
contributorData.setPhone(data[3]);
contributorData.setContribution(Double.parseDouble(data[4]));
contributorData.setId(Integer.parseInt(data[5]));
ID = Integer.toString(contributorData.getId());
contributorList.push(contributorData);//add object to top of contributorList
memberID.put(ID,contributorData);//add contributor ID to key element of Hash Table
dataRow = File.readLine(); // Read next line of data.
}//end While to read contributors.csv file
File.close();//close CSV file
System.out.println("Here is your unsorted contributor list:\n");
//call Print method to print the list
System.out.printf("%-10s %-10s %-8s %-15s %-17s %s %n", "First", "Last",
"Country", "Phone #", "Contribution", "ID");
Iterator<Contributor> iter = contributorList.iterator();
while(iter.hasNext()){
iter.next().Print();
}//end while
System.out.println("Thank you for using this program!");
} //main()
}//end ChrisJohnson_Unit3_IP class
同样，必须使用插入排序方法按名称对列表进行排序。我理解排序方法的基本概念，但老实说不知道如何在这里实现它。我不是在找人帮我做功课，只是在正确的方向上推动我。任何帮助将不胜感激，如果您需要更多信息，请告诉我。这项作业将于周一到期，因此希望届时有人能够帮助我。是的，我已经写信给我的教练寻求帮助，我整个星期都不在城里，所以我一直在努力追赶。感谢您花时间阅读我的问题
首先，我要说对链表做插入排序是完全没有意义的。其次，如果您添加一个连接贡献者名字和姓氏的 getName 方法，您可以执行类似以下操作（您可以在排序时连接，但您的代码会更混乱）。
for( int i = 1; i < contributorList.size(); i++)
{
int j = i;
Contributor tmp;
while( j > 0 && contributorList.get(j-1).getName().compareTo( contributorList.get(j).getName()) > 0)
{
tmp = contributorList.remove( j);
contributorList.add( j-1, tmp);
j = j - 1;
}
}
首先更改您的 contributorList 以使用其包含的对象的通用类型。即LinkedList<Contributor>;。其次更改对象以实现 Comparable。即 class Contributor implements Comparable<Contributor> 并实现方法 public int compareTo(Contributor other)。第三，选择一种排序方法并使用compareTo实现它来比较对象进行排序。
使用ListIterator找到插入元素的正确点并进行插入。这使您可以比使用 "standard approach" 更有效地进行插入排序，后者将 运行 in O(n³)，因为 get 和 set 运行 s 在 O(i) 中用于索引 i。 （内部循环将 运行 in O(i²)，因为 O(1+2+...+i) = O(i²) 和 O(1²+2²+...+n²) = O(n³)）。
注意using a Iterator足以在O(n)中找到插入点并实现O(n²)运行ning时间，但使用ListIterator可以让你查找和插入元素以及为外循环迭代的下一次迭代删除元素只有一个迭代器，如果使用巧妙的话。
使用 Comparator 按指定标准比较对象还允许您指定要排序的标准：
return value of comparator.compare(a, b) | meaning
-----------------------------------------------------------
0 | a == b
> 0 | a > b
< 0 | a < b
在 java 8 中，您可以轻松地创建一个 Comparator 给定方法引用给定一个对象返回排序标准的方法：
Comparator<Contributor> comparator = Comparator.comparing(Contributor::getLastName);
在不使用方法引用的情况下，这可以使用实现 Comparable 接口的对象的 compareTo 来完成，例如 String:
Comparator<Contributor> comparator = new Comparator<Contributor>() {
@Override
public int compare(Contributor o1, Contributor o2) {
return o1.getLastName().compareTo(o2.getLastName());
}
};
这样你就可以使用the Strategy Pattern for the ordering relation allowing you to use different sortings by passing different Comparators. And it's also the way the Collections class allows you to sort Lists with arbitrary contents, see Collections.sort(List, Comparator).