天天看點
傳回

轉：List , Collection, 排序

Collections.sort()

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place. 

轉自：http://dev.csdn.net/article/31/31142.shtm

以及：http://gaojiewyh.javaeye.com/blog/405514

=================================================

Java API針對集合類型排序提供了兩種支援：

java.util.Collections.sort(java.util.List)

java.util.Collections.sort(java.util.List, java.util.Comparator)

第一個方法要求所排序的元素類必須實作java.lang.Comparable接口。

第二個方法要求實作一個java.util.Comparator接口。

java.lang.Comparable接口和 java.util.Comparator接口是Java對排序最提供最基本支援。這兩個接口不但可以用于集合元素排序，還可以用于數組排序。

如果數組或集合元素是String類型，則可以利用Java API實作的Comparator對象String.CASE_INSENSITIVE_ORDER為容器元素排序。

下面給出兩個裡測試，涵蓋集合和數組的排序，并且還示範了數組和集合的互相轉換，附件裡面是完整的排序示範代碼。

方法一：實作 Comparable接口排序package collsort.comparable; 

package com.cvicse.sort.comparable;   public class Cat implements Comparable {     private int age;     private String name;       public Cat(int age, String name) {        this.age = age;        this.name = name;     }       public int getAge() {        return age;     }       public void setAge(int age) {        this.age = age;     }     ......     public int compareTo(Cat o) {        return this.getAge() - o.getAge();     }     ......
}

       通過實作Comparable接口實作個性化排序測試。排序測試，Collection.sort(list)升序排列Collections.sort(list, Collections.reverseOrder());降序排列；Collections.reverse(list);反轉排序，先輸出清單最後一個元素

public class TestComparable {  public static void main(String args[]) {   test();   test2();  }  public static void test() {   ......   List listCat1 = new ArrayList();   Cat cat1 = new Cat(34, "hehe");   Cat cat2 = new Cat(12, "haha");   Cat cat3 = new Cat(23, "leizhimin");   Cat cat4 = new Cat(13, "lavasoft");   listCat1.add(cat1);   listCat1.add(cat2);   listCat1.add(cat3);   ......   System.out.println("調用Collections.sort(List list)listCat2升序排序：");   Collections.sort(listCat1);   System.out.println("降序排列元素:");   Collections.sort(listCat1, Collections.reverseOrder());   System.out.println("Collections.reverse 從清單中最後一個元素開始輸出:");   Collections.reverse(listCat1);   ......  }  /**   * 針對數組的排序   */  public static void test2() {   String[] strArray = new String[] { "z", "a", "C" };   System.out.println("數組轉換為清單");   List list = Arrays.asList(strArray);   System.out.println("順序排序清單");   Collections.sort(list);   System.out     .println("按String實作的Comparator對象String.CASE_INSENSITIVE_ORDER排序----");   Collections.sort(list, String.CASE_INSENSITIVE_ORDER);   System.out.println("倒序排序清單");   Collections.sort(list, Collections.reverseOrder());   ......  }
}

方法二：實作Comparator接口排序

public class Person {  private int age;  private String name;   ......  public int getAge() {   return age;  }  public void setAge(int age) {   this.age = age;  }         ......
}

   實作了Comparator接口，重寫了compare方法

import java.util.Comparator;
public class PersonComparator implements Comparator {  public int compare(Person o1, Person o2) {   return o1.getAge() - o2.getAge();  }
}

     測試方法

public class TestComparator {  public static void main(String args[]) {   test1();  }  public static void test1() {   System.out.println("升序排序測試:");   List listPerson = new ArrayList();   Person person1 = new Person(34, "lavasoft");   Person person2 = new Person(12, "lavasoft");   Person person3 = new Person(23, "leizhimin");   Person person4 = new Person(13, "sdg");   listPerson.add(person1);   listPerson.add(person2);   listPerson.add(person3);   Comparator ascComparator = new PersonComparator();   System.out.println("排序後集合為:");   // 利用Collections類靜态工具方法對集合List進行排序   Collections.sort(listPerson, ascComparator);   System.out.println("/n降序排序測試:");   // 從升序排序對象産生一個反轉(降序)的排序對象   Comparator descComparator = Collections     .reverseOrder(ascComparator);   System.out.println("利用反轉後的排序接口對象對集合List排序并輸出:");   Collections.sort(listPerson, descComparator);   outCollection(listPerson);  }
}

     以上的例子中使用是對int類型的屬性排序，對String屬性排序可以用以下的方法

public int compareTo(Cat o) {return this.getName().compareTo(o.getName());}

comparetTo()函數的使用說明： 

如果

結果

<0

a

==0

a==b

>=0

a>b

Java如何通過所實作接口的方法進行排序是API内部的事情，Java這樣處理排序目的就是對容器元素排序有一個統一的方式，以簡化程式設計。

=============================================================

在Java Collection Framework中定義的List實作有Vector，ArrayList和LinkedList。這些集合提供了對對象組的索引通路。他們提供了元素的添加與删除支援。然而，它們并沒有内置的元素排序支援.

你能夠使用 java.util.Collections類中的sort()方法對List元素進行排序。你既可以給方法傳遞一個List對象，也可以傳遞一個 List和一個Comparator。如果清單中的元素全都是相同類型的類，并且這個類實作了Comparable接口，你可以簡單的調用 Collections.sort()。如果這個類沒有實作Comparator，你也可以傳遞一個Comparator到方法sort()中，進行排序。如果你不想使用預設的分類順序進行排序，你同樣可以傳遞一個Comparator到方法sort()中來進行排序。如果清單中的元素并不都是相同類型的類，你在進行排序的時候就不是這樣幸運了。除非你編寫一個專用的跨類的Comparator。

排序的順序怎麼樣呢？如果元素是String對象，卻省的排序順序是按照字元編碼進行的，基本上是每個字元的 ASCII/Unicode值。如果嚴格的限制在處理英文，卻省的排序順序通常是足夠的，因為它首先排A-Z，然後是小寫字母a-z。然而如果你處理非英文字，或者你隻是想使用不同的排序順序，這樣Collections.sort()就出現了第二種變化。例如，你想使用字元串的反序進行排序。為了實作這個功能，你可以在Collections類中通過reverseOrder()來擷取一個反序Comparator。然後，你将反序Comparator 傳遞給sort()方法。換句話說，你作如下工作：

List list = ...;

Comparator comp = Collections.reverseOrder();

Collections.sort(list, comp);

如果清單包含項目：Man, man, Woman, 和woman，排序好的清單将是Man, Woman, man, woman。這裡沒有什麼複雜的。需要注意的非常重要的一點是Collections.sort()是進行原位排序。如果你需要保留原序，需要先對原集合進行複制，在排序，就像這樣：

List list = ...;

List copyOfList = new ArrayList(list);

Collections.sort(copyOfList);

這裡，排好序的清單是：Man, Woman, man, woman，但是原始清單（Man, man, Woman, woman）被保留了。

到目前為止，排序是區分大小寫的。你如何進行不去分大小寫的排序呢？一種實作方式是象這樣實作 Comparator:

public static class CaseInsensitiveComparator

implements Comparator {

public int compare(Object element1,

Object element2) {

String lower1 =

element1.toString().toLowerCase();

String lower2 =

element2.toString().toLowerCase();

return lower1.compareTo(lower2);

}

}

你确實不需要手工的建立這個類。而是，你可以是用以存在的 Comparator，CASE_INSENSIVTIVE_ORDER，它是在String類中定義的。

這種實作方式有一點小小的問題。Sort()算法提供穩定的排序，并保持與原有序列相同的元素。這意味着一個包含兩個元素”woman”和”Woman”的清單将有不同的排序，而這種不同是根據兩個元素在清單中出現的先後次序決定的。

語言的不同又會怎麼樣呢？java.text包提供了Collector和CollectionKey類來進行區分語言的排序。這裡是例子:

注意，如果你的文本是本地語言，而不是預設語言，你需要傳遞一個本地語種給getInstance()方法，就象:

public static class CollatorComparator

implements Comparator {

Collator collator = Collator.getInstance();

public int compare(Object element1,

Object element2) {

CollationKey key1 = collator.getCollationKey(

element1.toString());

CollationKey key2 = collator.getCollationKey(

element2.toString());

return key1.compareTo(key2);

}

}

你是在對集合關鍵字進行排序，而不是實際的字元串。這不僅提供固定的不區分大小寫的排序，而且它是跨語種的排序。換句話說，如果你對西班牙文和非西班牙文的混合詞進行排序，詞ma?ana (tomorrow)将排在mantra的前面。如果你不使用Collector，ma?ana将排在mantra的後面。

下面這個程式對一個清單進行不同類型的排序（預設的、區分大小寫的、區分語種的）：

import java.awt.BorderLayout;

import java.awt.Container;

import java.io.*;

import java.text.*;

import java.util.*;

import javax.swing.*;

public class SortIt {

public static class CollatorComparator

implements Comparator {

Collator collator = Collator.getInstance();

public int compare(Object element1,

Object element2) {

CollationKey key1 = collator.getCollationKey(

element1.toString());

CollationKey key2 = collator.getCollationKey(

element2.toString());

return key1.compareTo(key2);

}

}

public static class CaseInsensitiveComparator

implements Comparator {

public int compare(Object element1,

Object element2) {

String lower1 = element1.toString().

toLowerCase();

String lower2 = element2.toString().

toLowerCase();

return lower1.compareTo(lower2);

}

}

public static void main(String args[]) {

String words[] =

{"man", "Man", "Woman", "woman",

"Manana", "manana", "ma?ana", "Ma?ana",

"Mantra", "mantra", "mantel", "Mantel"

};

// Create frame to display sortings

JFrame frame = new JFrame("Sorting");

frame.setDefaultCloseOperation(

JFrame.EXIT_ON_CLOSE);

Container contentPane = frame.getContentPane();

JTextArea textArea = new JTextArea();

JScrollPane pane = new JScrollPane(textArea);

contentPane.add(pane, BorderLayout.CENTER);

// Create buffer for output

StringWriter buffer = new StringWriter();

PrintWriter out = new PrintWriter(buffer);

// Create initial list to sort

List list = new ArrayList(Arrays.asList(words));

out.println("Original list:");

out.println(list);

out.println();

// Perform default sort

Collections.sort(list);

out.println("Default sorting:");

out.println(list);

out.println();

// Reset list

list = new ArrayList(Arrays.asList(words));

// Perform case insensitive sort

Comparator comp = new CaseInsensitiveComparator();

Collections.sort(list, comp);

out.println("Case insensitive sorting:");

out.println(list);

out.println();

// Reset list

list = new ArrayList(Arrays.asList(words));

// Perform collation sort

comp = new CollatorComparator();

Collections.sort(list, comp);

out.println("Collator sorting:");

out.println(list);

out.println();

// Fill text area and display

textArea.setText(buffer.toString());

frame.pack();

frame.show();

}

}

如果你的主要問題是順序通路，可能清單不是你的好的資料結構選擇。隻要你的集合沒有重複，你可以在樹（TreeSet）中儲存你的元素（提供或不提供Comparator）。這樣，元素将總是排序形式的。

Computer Science list string sorting collections object import
上一篇: JVM記憶體分代模型（用于分代垃圾回收算法）
下一篇: python module： collection 的 Counter() 1.collections子產品 2.Counter類3.常用操作

繼續閱讀