使用compareTo()方法按字母顺序对列表进行排序

Question

我正在用Java编写电话簿程序，需要按照字母顺序列出人名。为此，我需要为Java中的列表编写一个排序算法，且仅使用compareTo()方法。请问有谁能帮助我完成这个任务吗？

public void listAlpha()
 {
     Node tempNode = head;

     for(int i = 0; i <= size; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                int comparison = ((tempNode.getNext().getElement().getName()).compareTo(tempNode.getElement().getName()));
                if(comparison < 0)
                {
                    Person tempPerson =  tempNode.getElement();

                    tempNode.setElement(tempNode.getNext().getElement());
                    tempNode.getNext().setElement(tempPerson);
                    tempNode = tempNode.getNext();
                }
            }


        }

顺便说一下，这是一个作业，我使用了自己的数据结构。

这是上面我写的方法所属的类：

import java.util.*;

/** Singly linked list implementation .*/
public class SLinkedList<E> implements LinkedList<E>, Iterable<E> {
  protected Node<E> head;       // head node of the list
  protected Node<E> tail;       // tail node of the list
  protected int size;       // number of nodes in the list

    public Iterator<E> iterator()
    {
        return new LinkedListIterator(head);
    }

  /** Default constructor that creates an empty list */
  public SLinkedList() {
    head = null;
    tail = null;
    size = 0;
  }

  public int size() { 
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public void addFirst(E newElement) {
    Node<E> newNode = new Node(newElement,null);
    if(size == 0) //if list is empty
        tail = newNode;

    newNode.setNext(head);
    head = newNode;
    size++;
  }

  public void addLast(E newElement) {
    Node<E> newNode = new Node(newElement,null);

    if(size == 0) //if list is empty
        head = newNode;

    if (size != 0) //if list is not empty
        tail.setNext(newNode);

    tail = newNode;
    size++;
  }

  public E removeFirst() {
    Node<E> tempNode = null;
    if (size != 0) {
        if(size == 1)
            tail = null;

        tempNode = head;
        head = head.getNext();
        tempNode.setNext(null);
        size--;
    }

    //if list is empty then return null
    return tempNode.getElement(); 

  }

  public E removeLast() {
    Node<E> tempNode = head;

    if(size == 0)
        return null;

    if(size == 1) {
        head = null;
        tail = null;
        size--;
        return tempNode.getElement();
    }

    //size is greater than 1
    for(int i=1; i<=size-2; i++) {
        tempNode = tempNode.getNext(); //go to element that before the tail
    }

    Node<E> tempNode2 = tail;
    tail = tempNode;
    tail.setNext(null);
    size--;
    return tempNode2.getElement();

  }

  public void remove(E element){
    int index = 0;
    boolean found = false;
    Node<E> temp = head;
    for(int i=1; i<=size; i++) {//find the node with element
        index++;
        if(temp.getElement().equals(element)){
            found = true;
            break;
        }
        temp = temp.getNext(); 
    }

    if(found){
        if(index == 1) 
            removeFirst();

        else if(index == size)
            removeLast();

        else{   
            //find the previous node
            Node<E> prev = head;
            for(int i=1; i<index-1; i++) {
                prev = prev.getNext(); 
            }

            prev.setNext(temp.getNext());
            temp.setNext(null);
            size--;
        }
    }
  }

  public int searchList(E searchKey) {
    if(size == 0)
        return -1;

    Node tempNode = head;
    for(int i=1; i<=size; i++) {
        if(tempNode.getElement().equals(searchKey))
            return i; //return index of the node
        tempNode = tempNode.getNext();
    }

    return -1; //not found
  }

  public void printList() {
    Node tempNode = head;
    for(int i=1; i<=size; i++) {
        System.out.print(tempNode.getElement());
        if(i!=size) //if it is not last element
            System.out.print(" - ");
        tempNode = tempNode.getNext();
    }
    System.out.println();

  }

人员类：

public class Person
{
    private String name;
    private String surname;
    private String address;
    private PhoneNumber phone1;
    private PhoneNumber phone2;
    private PhoneNumber phone3;

    public Person()
    {
        name = null;
        surname = null;
        address = null;
        phone1.setPhone(0);
        phone1.setType("");
        phone2.setPhone(0);
        phone2.setType("");
        phone3.setPhone(0);
        phone3.setType("");
    }

    public Person(String n, String s, String a,PhoneNumber p1, PhoneNumber p2, PhoneNumber p3)
    {
        name = n;
        surname = s;
        address = a;
        phone1 = p1;
        phone2 = p2;
        phone3 = p3;

    }

    public String getName()
    {
        return name;
    }

    public void setName(String n)
    {
        name = n;
    }
    public String getSur()
    {
        return surname;
    }

    public void setSur(String s)
    {
        surname = s;
    }

    public void insertPhone(PhoneNumber phone)
    {
        if(phone2 == null)
            phone2 = phone;
        else if(phone3 == null)
            phone3 = phone;
    }

    public PhoneNumber getPhone1()
    {
        return phone1;
    }

    public PhoneNumber getPhone2()
    {
        return phone2;
    }

    public PhoneNumber getPhone3()
    {
        return phone3;
    }

    public String getAdd()
    {
        return address;
    }

    public void setAdd(String a)
    {
        address = a;
    }

- Master Noxob

---

你可能认为这很简短，但实际上这取决于如果姓氏或名字在任一对象中为空时比较操作应该执行什么。 - Powerlord

由于您需要编写自己的排序代码，而不能使用内置函数，因此这里提供了一份排序算法列表供您尝试使用。 - nem035

Answer 1

你可以让你的Person类实现Comparable接口，并定义以下方法：

    public class Person implements Comparable<Person> {

       // Your previous code

       public int compareTo(Person other) {
          if (other == null) {
             // throw exception for example
          }
          return this.name.toLowerCase().compareTo(other.name.toLowerCase());
       }
    }

- kamino

Answer 2

正如其他人提到的那样，compareTo 是 Comparable 接口的一部分。

你实现它的方式取决于你想先按姓氏还是名字排序，并且是否希望它们按升序排序。

例如，如果你要按姓氏首先以升序排序：

public class Person implements Comparable<Person> {
    // the parts of Person you already have would go here
    public int compareTo(Person person) {
        if (person == null) {
            return -1;
        }

        if (surname != null && person.getSur() == null) {
            return -1;
        } else if (surname == null && person.getSur() != null) {
            return 1;
        } else if (surname != null && person.getSur() != null) {
            int compare = surname.compareToIgnoreCase(person.getSur());
            if (compare != 0) {
                return compare;
            }
        }
        // Note that we did nothing if both surnames were null or equal

        if (name == null && person.getName() == null) {
            return 0;
        } else if (name != null && person.getName() == null) {
            return -1;
        } else if (name == null && person.getName() != null) {
            return 1;
        } else {
            return name.compareToIgnoreCase(person.getName());
        }
    }
}

（我实际上没有测试过这段代码）

这依赖于String对compareToIgnoreCase的实现。

请注意，这也会将所有空对象和具有空名称和姓氏的对象移动到列表的末尾。

话虽如此，如果您实现了Comparable接口，您可以使用sort让集合API为您完成工作。

如果您发现需要针对一个对象使用多种不同的排序方法，则可以创建一组Comparator对象来进行排序。

- Powerlord

Answer 3

在你的Person类中实现“Comparable”接口。

然后你的compareTo()方法会是这样的：

public int compareTo(Person other) {
    return name.compareTo(other.getName())
}

然后使用 Collections.sort(你的 Person 列表);

- starf

Answer 4

Person类的签名应该像这样：

public class Person implements Comparable<Person>

在Person类中添加compareTo方法，并使用starf建议的Collections.sort(personList)。

- helppo